N iterations of K function calls, or K function calls of N iterations?

[KomodoDave]

Hi guys,

I wish to implement a constraints solver in a physical simulation, and wish to model each constraint as a Function object.

I'm wondering whether it's best to have each constraint operate on a full set of data, thus code will be in the form:



public function constraint1(dataset:Vector.<T>)
{
for (var i:int = 0; i < dataset.length; ++i)
; // do stuff
}

public function constraint2(dataset:Vector.<T>)
{
for (var i:int = 0; i < dataset.length; ++i)
; // do stuff
}

public function satisfyConstraints(dataset:Vector.<T>)
{
constraint1(dataset);
constraint2(dataset);
}
..or else to have each constraint operate on a lone dataset member, i.e.




public function constraint1(data_i:T)
{
// do stuff
}

public function constraint2(data_i:T)
{
// do stuff
}

public function satisfyConstraints(dataset:Vector.<T>)
{
for (var i:int = 0; i < dataset.length; ++i)
{
constraint1(dataset[i]);
constraint2(dataset[i]);
}
}
Assume there are K constraints (thus there are K constraint Function objects instantiated), with a dataset of size N.

In the first version there will be K function calls, with KN iterations in total.

In the second version there will be KN function calls, with N iterations in total.

Which will perform best, judging from your experience?

Many thanks,

David

[Krilnon]

The first version.

[KomodoDave]

The first version.

Thank you.

[marnix]

in fact, the first version is much faster.



package {

import flash.display.*;
import flash.utils.getTimer;

public class Script extends MovieClip {

private var testVector:Vector.<uint> = new Vector.<uint>();

public function Script(){
for(var i:uint = 0; i < 1000000; i++){
testVector.push(5);
}
example1();
example2();
}

private function example1(){
var timeBefore:uint = getTimer();
satisfyConstraintsA(testVector);
trace("example 1 - total time: " + (getTimer() - timeBefore) + "ms.");
}

private function example2(){
var timeBefore:uint = getTimer();
satisfyConstraintsB(testVector);
trace("example 2 - total time: " + (getTimer() - timeBefore) + "ms.");
}

/*
functions for example 1:
*/

public function constraint1a(dataset:Vector.<uint>){
for(var i:int = 0; i < dataset.length; ++i){
dataset[i]++;
}
}

public function constraint2a(dataset:Vector.<uint>){
for(var i:int = 0; i < dataset.length; ++i){
dataset[i]++;
}
}

public function satisfyConstraintsA(dataset:Vector.<uint>){
constraint1a(dataset);
constraint2a(dataset);
}

/*
functions for example 2:
*/

public function constraint1b(i:uint){
i++;
}

public function constraint2b(i:uint){
i++;
}

public function satisfyConstraintsB(dataset:Vector.<uint>){
for(var i:int = 0; i < dataset.length; i++){
constraint1b(dataset[i]);
constraint2b(dataset[i]);
}
}
}
}

output:
example 1 - total time: 538ms.
example 2 - total time: 656ms.

if you want to speedup your code a little more use the following code for iteration:



public function constraint1a(dataset:Vector.<uint>){
var i:uint = 0;
var arraylength:uint = dataset.length;
for(i; i < arraylength; ++i){
dataset[i]++;
}
}

output:

example 1 - total time: 146ms.
example 2 - total time: 434ms.

[KomodoDave]

in fact, the first version is much faster.

Thanks for the benchmark, marnix :) Just so you know - I wasn't being lazy by not coding my own, I was just attempting to stimulate some interesting analyses by others in the forums! Much appreciated that you made the effort to post the benchmark :thumb:

[Krilnon]

I was just attempting to stimulate some interesting analyses by others in the forums!

Haha, sorry if my post didn't have enough analysis in it. It just seems straightforward that an iteration construct like a for loop would have less overhead than a function call, at least in ActionScript.

There's a really well-known paper (http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf) (one of the Lambda Papers) from the '70s that argues that function/procedure calls don't have to be expensive, but that it is "largely a result of poorly designed language implementations."

Anyway, although people probably have somewhat different expectations of what a function call entails these days, I think that function calls in virtual machines like AVMPlus still generate quite a large amount of overhead versus loops (well, in AS, they definitely have more overhead than the languages of the '70s)… so it makes sense that iterating would be faster.

[rumblesushi]

Yeah, what Krilnon said, obviously whatever option that has less function calls is better.

As I mentioned in the other thread Komodo, there are almost always ways of running code recursively over the same object with a loop rather than a recursive function call.

You'll start to notice a difference after saving on a few thousand function calls.

And as Marnix pointed out, precalculating array lengths is a given for performance programming, and for me, so is object pooling.

But remember, with object pooling, DON'T use a function call to fetch the next object in the pool. I've seen people set up objects pools like that, with a function call. It's utterly pointless. The function call can be more expensive than creating a new object.

[Valaran]

Yeah, what Krilnon said, obviously whatever option that has less function calls is better.

As I mentioned in the other thread Komodo, there are almost always ways of running code recursively over the same object with a loop rather than a recursive function call.

You'll start to notice a difference after saving on a few thousand function calls.

And as Marnix pointed out, precalculating array lengths is a given for performance programming, and for me, so is object pooling.

But remember, with object pooling, DON'T use a function call to fetch the next object in the pool. I've seen people set up objects pools like that, with a function call. It's utterly pointless. The function call can be more expensive than creating a new object.

Edit: Sorry for hijacking the thread.

As the almighty failure on these forums, I have to ask out of curiousity, how would you approach object pooling, without function calls? Thanks for any explanation :)

[KomodoDave]

Haha, sorry if my post didn't have enough analysis in it. It just seems straightforward that an iteration construct like a for loop would have less overhead than a function call, at least in ActionScript.

You're right, it is kind of obvious.. I'll punish myself later :hugegrin:


Anyway, although people probably have somewhat different expectations of what a function call entails these days, I think that function calls in virtual machines like AVMPlus still generate quite a large amount of overhead versus loops (well, in AS, they definitely have more overhead than the languages of the '70s)… so it makes sense that iterating would be faster.

Thanks for the paper link. What amazes me is that we still have to do tricks like those you showed in your 'speedup' version; why doesn't someone build a compiler that does these things for you?

I've spent all day reading up on haXe after you guys mentioned it in my other thread, and I am.. umm.. warily interested. There are some design decisions in the language which I find odd. For example, the ability to typedef a class with a private function which exposes that function as public. Also, the fact that standard 'getter' and 'setter' functions seem to partially overlap with the standard visibility modifiers 'private' and 'public', in the sense that you can define 'null' and 'never' getter/setters. It's a little odd, in my mind.. personally I am happy to say:



class MyClass
{
private var x:int;

public function getX():int { return x; }
private function setX(x:int):void { this.x = x; }
}
..whereas in haXe it seems you would say:



class MyClass
{
private var x (getX, null):int;

public function getX():int { return x; }
private function setX(x:int):void { this.x = x; }
}
..but what's the point in having '_private_ function setX' when in fact the property (getter, setter) specified determines the setX function visibilty? It makes little sense to me.

Don't get me wrong, I'm happy to start coding in haXe tonight (in fact I have started!); I'm just a little concerned by some of the language design; perhaps someone who's used haXe a lot can reassure me?;( I'm interested in using it primarily for true generics support, stronger typing than the flex compiler, and faster compilation and execution times. Features like type inference don't appeal to me; it's a neat feature, but in my opinion it's far wiser to spend the extra few minutes required each day to explicitly specify parameter types than to have the compiler infer them. Type inference has the knock-on consequence of requiring any other humans updating that code in the future having to spend the same amount of time - gained by the original outhor while writing the code - on working out the parameter types. I don't see the sense of it, unless you have serious time constraints and a few minutes a day matters that much! I'm not ranting here, just calmly expressing my opinion :emb:


As I mentioned in the other thread Komodo, there are almost always ways of running code recursively over the same object with a loop rather than a recursive function call.

I appreciate the advice, but wonder where I've mentioned using recursion? I never recurse, I always use the so-called 'trampoline' method, i.e. iterating over a queue of returned values, as I think you're suggesting ;)


But remember, with object pooling, DON'T use a function call to fetch the next object in the pool. I've seen people set up objects pools like that, with a function call. It's utterly pointless. The function call can be more expensive than creating a new object.

So what is the solution you suggest, to fetch the next object? I mean, personally I usually _would_ have an ObjectPool.New() function which returned the next recycled object... How would you do it, rumblesushi? I'm intrigued..

EDIT:


Edit: Sorry for hijacking the thread.

As the almighty failure on these forums, I have to ask out of curiousity, how would you approach object pooling, without function calls? Thanks for any explanation :)

LOL! You're no failure, Valaran, I too am puzzled.. The only explanation I can think of is that by an 'object pool' rumblesushi is referring to a set of pre-built objects that you simply increment your way through, as a new object is needed. To my mind, 'object pooling' is recycling of objects, and I can't see how you could retrieve the next object without a function call, except in the object pool class itself! :crying:

[Valaran]

LOL! You're no failure, Valaran, I too am puzzled.. The only explanation I can think of is that by an 'object pool' rumblesushi is referring to a set of pre-built objects that you simply increment your way through, as a new object is needed. To my mind, 'object pooling' is recycling of objects, and I can't see how you could retrieve the next object without a function call, except in the object pool class itself! :crying:

I guess you could implement the object pool in the same class you're 'already' working on, and instead of calling a method to retrieve a new object, everything (that the Pool.get() or whatever) method does is put directly into corresponding section. This easily gets troublesome and tiresome if you need to use the pool in many places, Im still curious to see if Rumblesushi had any other particular solution in mind :)

Edit: Im also interested in this 'trampoline'-method, could you elaborate further? :) And sorry for hijacking, again..

[marnix]

this has become a really interesting topic.

[KomodoDave]

Edit: Im also interested in this 'trampoline'-method, could you elaborate further? :) And sorry for hijacking, again..

Sure, Valaran. It's actually very simple.

Say you have a simplistic factorial function:



function f(a:int, b:int):int
{
return a * b;
}

function factorial(x:int):int
{
if (x == 1)
return 1;
// else
return f(x, factorial(x-1));
}
The trampolined form simply uses iteration and passes back the value from each function call, meaning you never go more than one call deep (i.e. you don't recurse):



function trampolined_factorial(x:int):int
{
int value = 1;
for (; x > 1; --x)
value = f(x, value);
return value;
}
You see? You can do this with any recursive function. You simply need to identify how the recursive function value (here 'x') changes with each successive call of that function, and stick that in the FOR loop inside the trampolined function. Here that change is just a decrement of course, so we have '--x'.

P.S. Note that the 'x > 1' in the trampolined function is simply another way of saying of the 'if (x == 1) return 1' in the recursive function, since of course x * 1 = x, i.e. there is no more change when we get to that point.

[Shaedo]

Thank you KomodoDave for that explanation!

[Valaran]

Ah I see, thanks a lot KomodoDave, guess I should had been able to work that one out myself :) Now only to see if Rumblesushi gets around :D

[rumblesushi]

Komodo, ah I thought you insinuated in the other thread that you needed recursive relaxation. I just looked, you said interation without too many function calls, I sort of interpreted that as you having a recursive function in mind to iterate over the constraints but wanted to make sure there weren't too many recursions - my mistake ;)

But yeah, I would do it essentially the same way, a loop iteration, only mine would look different.

Komodo - yep, using ObjectPool.new() is how most people do it. And you know what? It's utterly pointless, object pools are meant to improve performance, and doing it with a function call would only serve to possibly save some RAM, but on average it's going to perform slightly worse than just creating a new object.

And as long you as you know what's referencing said object, when it's nullified, it'll be garbage collected anyway.

Valaran - you guessed it really. If you know the objects you're recycling are only going to be used by one class for sure - you could have a class level pool. But if the objects are needed by multiple classes, just create a pool class and use it like this.

Here's an example of how I create a dynamic Vertex or UV coordinate in my frustum clipping class, for dynamically clipped/split polygons.

Essentially, it's the same as inlining any other function. The code that's here is what would be in the function pool.fetchVertex() etc, that would return a recycled Vertex.

ActionScript Code:

var v1:Vertex;
if (pool.vCount >= pool.poolNum) {
pool.vCount = 0;
}
v1 = pool.vPool[pool.vCount++];




Same thing for a new UV coord...

ActionScript Code:

var uv1:UV;
if (pool.uvCount >= pool.poolNum) {
pool.uvCount = 0;
}
uv1 = pool.uvPool[pool.uvCount++];




So that now performs far, far better than either creating a new object or using a function call to recycle an object, and it's what, an extra couple of lines of code?

In a pool class that's used globally, you just have to make sure all the variables are static.

Obviously if we're talking about deferring a few hundred object creations or function calls, you're not going to notice any difference. But if you've got something with a lot going on, once you start getting into saving thousands of function calls/object creations etc, it's going to pay off, and you'll start to notice a performance increase. Such as a game or particle engine or physics engine etc.

But this is just one part of performance programming. Syntax level optimisation like precalculated arrays, typed variables, even object pools, are just one factor. By doing that, your app is not going to magically run twice as fast, but it all adds up.

I've said this before but the most important thing is writing clever code, deferred calculations, deferred rendering etc - that is far, far more significant than syntax level optimisation.

[KomodoDave]

Komodo - yep, using ObjectPool.new() is how most people do it. And you know what? It's utterly pointless, object pools are meant to improve performance

...

Here's an example of how I create a dynamic Vertex or UV coordinate in my frustum clipping class, for dynamically clipped/split polygons.

...

Essentially, it's the same as inlining any other function.

...

ActionScript Code:

var v1:Vertex;
if (pool.vCount >= pool.poolNum) {
pool.vCount = 0;
}
v1 = pool.vPool[pool.vCount++];



Thanks for sharing, rumblesushi :goatee: For pure AS3, this is a cute option. Now I'm using haXe (since yesterday!), I can take advantage of the 'inline' keyword and simply use that instead. Nicolas Cannasse, I salute you :mountie:

[rumblesushi]

Yep, to be sure to be sure. HaXe looks appealing for that alone, a compiler that supports inlining.

I'm going to stick to AS3 with my current project though, as it's almost complete, and all the optimisation is done, porting it to haXe would be more trouble than it's worth, and I wouldn't get any added performance (apart from possibly the alchemy esque opcodes class/faster memory access?).

It is incredible that just one guy developed haXe, and built a better compiler than Adobe's :D

[Valaran]

I always enjoy reading your very informative thread/replies Rumblesushi, thank you once again!

[rumblesushi]

Thanks Valaran, you're welcome ;)