Everybody! This is important. In a few days, these forums will be moving over to using the totally sweet Discourse platform. To ensure this migration happens smoothly with no loss of content, these forums are currently in a read-only mode. I do apologize for the inconvenience.

There is never a good time to turn the forums off for an extended period of time, but I promise the new forums will be a billion times better. I'm pretty sure of it.

See you all on the other side in a few days, and if you have any (non-technical) questions, please e-mail me at kirupa@kirupa.com. For technical questions, try to find a tutorial that corresponds to what you are looking for and post in the comments section of that page.

Cheers,
Kirupa

Page 1 of 2 12 LastLast
Results 1 to 15 of 19

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

  1. #1

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

    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:

    Code:
    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.

    Code:
    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

  2. #2
    The first version.

  3. #3
    Quote Originally Posted by Krilnon View Post
    The first version.
    Thank you.

  4. #4
    in fact, the first version is much faster.

    Code:
    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:

    Code:
    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.

  5. #5
    Quote Originally Posted by marnix View Post
    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

  6. #6
    Quote Originally Posted by KomodoDave
    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 (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.

  7. #7
    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.

  8. #8
    Quote Originally Posted by rumblesushi View Post
    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
    Last edited by Valaran; February 5th, 2010 at 07:28 PM.

  9. #9
    Quote Originally Posted by Krilnon View Post
    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

    Quote Originally Posted by Krilnon View Post
    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:

    Code:
    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:

    Code:
    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

    Quote Originally Posted by rumblesushi View Post
    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

    Quote Originally Posted by rumblesushi View Post
    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:

    Quote Originally Posted by Valaran View Post
    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!
    Last edited by KomodoDave; February 5th, 2010 at 08:30 PM.

  10. #10
    Quote Originally Posted by KomodoDave View Post
    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!
    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..
    Last edited by Valaran; February 5th, 2010 at 10:12 PM.

  11. #11
    this has become a really interesting topic.

  12. #12
    Quote Originally Posted by Valaran View Post
    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:

    Code:
    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):

    Code:
    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.
    Last edited by KomodoDave; February 5th, 2010 at 11:16 PM.

  13. #13
    Thank you KomodoDave for that explanation!

  14. #14
    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

  15. #15
    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.
    Last edited by rumblesushi; February 6th, 2010 at 07:14 AM.

Page 1 of 2 12 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012