Optimized loops


Optimized loopsEvery one should write code that performs well. Do you use loops in your code? This is a simple trick everyone could apply to his loops.

How you write a loop

Mostly when people are writing loops, it looks like this:

for(var i:int = 0; i < list.length; i++) { var item:MyItem = list[i]; item.doSomething(); item.doAnotherThing(); } [/as] Now this loops works, but there are some small things that could be improved. If you use lots of loops it should be needed to improve your loops, but I hope this is just nice to know anyway.

The optimized version

Take a look at the improved loop:

var item:MyItem;
var total:uint = list.length;
for(var i:uint; i < total; i++) { item = list[i] as MyItem; item.doSomething(); item.doAnotherThing(); } [/as] What is improved in this loop? If you take a close look in both loops you will see I access the list-item once using list[i], and assign it to a variable called item. I don’t what it is, but for me it looks like most people who write javascript always use list[i] instead of creating a var of it, is that right? It is important to know you don’t need to create the var inside the loop, but create it once outside the loop, and (re-)use it while looping. I forget this most of the times, but it is a good practice to check if all the variables you are using inside a loop. Most of the times variables could be defined outside the loop, which could increase performance big time.

The second thing is to define a variable called total, which pre-calculates the length of the loop as a local variable. If you don’t define it, the FlashPlayer checks the length of the Array every time in the loop, now it is like a constant. Note, when you are removing items from the list, you should ajust the total-variable too, since the total does not equal the length of the list anymore ofcourse. 😉

Another thing you probably noticed is that I used the ‘as’ keyword to give the FlashPlayer a direct hint of the type of variable. This another way of casting, and slightly faster than MyItem(list[i]).

Update: Take a look at this great article about the performance of this casting method. http://jacksondunstan.com/articles/1305

Some other small things are to use uints for i and total in loops if you are using positive numbers. Another small thing is that you don’t have to define i = 0, only when you are using nested loops or re-using the i or j in the same function/scope.

Want a more freaky way to define the same optimized loop?

for(var i:uint, item:MyItem, total:uint = list.length; i < total; i++) { item = list[i] as MyItem; item.doSomething(); item.doAnotherThing(); } [/as] Are you using FlashDevelop? You could this for-loop snippet (scroll down).

Most of the loop-optimisation tips also applies to javascript.

12 responses to “Optimized loops”

  1. Tha Narie says:

    I love optimizing code, so here are a few remarks:

    1. In bytecode, all variables in a method are only declared once, at the top of the method. So it doesn’t matter where (even if it’s inside a loop) you declare them.

    2. If the total var doesn’t change, it could be faster to use a const:
    const total:uint = list.length;

    3. There was a time where ++i was faster than i++, and –i was even faster. Don’t know how they compare at the moment, but writing ++i there doesn’t hurt 🙂

    4. I think there is 1 ‘var’ too much in your last code example 😉

  2. Mark Knol says:

    @Tha Narie: 1. I didnt know that!? How do you know/benchmark that?
    3. Yes, it makes also a slight difference, check out http://jacksondunstan.com/articles/1258 (great website btw)
    4. Thanks, I have edited the last code example.

  3. Good stuff. I wince every time I see a loop where the “length” getter is called every iteration. Function calls are expensive and should be eradicated from virtually every loop. That said, I have a couple thoughts to add to Tha’s list:

    1. It’s true that all variables are “hoisted” to the function level. See Adobe’s documentation for me. I also wrote an article about variable hoisting.

    2. It’s also true that “const” is only for compile-time checking. When compiled, it’s just like “var”. See my in-depth article for more.

    3. The article (of mine) that you linked shows identical performance for “++uint” as with “uint++”. Also, thanks for the kind words about my site. 🙂

    PS: The red glow around your form input fields is awesome!

  4. Mark Knol says:

    @Jackson, thanks! I think all flashdevelopers should read your site 🙂 I did not know about hoisting (strange word btw), so that is good to know!

    Oh and the glow is done with CSS (box-shadow), have added it a while ago. When I have time, it needs some css-animation, I think it would be cool if the glow slowly appears.. Love to see html finally is evolving.

  5. Rackdoll says:

    even faster:

    var i:int = -1;
    var item:MyItem;
    var total:uint = list.length;

    for(i; i < total; ++i)
    item = list[i]; //where list is a typed vector

    ofc linked lists are best, fastest and most optimized.

  6. dx0ne says:

    and this should be slightly better:

    for each(var item:MyItem in list)

  7. Rackdoll says:

    actually a for each loop should be slower
    as it calls the length every cicle

  8. dx0ne says:

    Quick test showed that foreach is slightly* faster. Could be dependent on machine/operations in class.function or even flash player version.
    I use it because it looks cleaner 🙂

    * anyway slightly is really slightly as in fractions of second for big loops

  9. skyboy says:

    For each doesn’t actually use the AS3 getter (It is a getter, right? No native code trickery?) because it has a special “hasnext” opcode that acts as a native code iterator for all types, loading each of the properties (stored in a way similar to Vector) into a register. I recall that a regular for loop was slightly faster though, but this may have changed in recent versions.

    And LinkedList is not always the faster for iteration, because its nodes can’t be prefetch by the processor because the location of the element after the next element isn’t known until the next element is loaded into the cache. Meaning in a worst-case scenario, more time is spent waiting on RAM than is spent doing actual work. If you link a node to itself and then iterate over that, it will be around 10x faster than iterating over a Vector because there is never a wait. However, in more complex structures, or in very large structures, cache misses are going to happen, and completely remove any speed advantage that may be offered, and bring it down to 3x slower. http://wonderfl.net/c/mabh
    Times were taking from my machine’s results on that test.

    Vector doesn’t suffer this problem because it’s all in one contiguous block of memory, and k elements after the nth element can easily be prefetched by the processor such that all elements are in the processor cache and virtually no time is spent waiting on cache lines to be filled.

    Both get advantages from larger L1, L2 and L3 caches, but RAM remains much slower than all of these, but I don’t see RAM improving to a point of being as fast as L3, 4, 5 or 6 cache any time soon. (I doubt any processors have that many caches, but technology is very rapidly improving, so we’ll see if it gets to that point.)

    I learned most of this just recently myself.

    As for being on topic, I’ll take a peak into the tamarin source tomorrow to see if I can find where this optimization is being made and what it does. As I said in my last comment on Jackson’s blog this may be some artifact of dead code elimination. (Perhaps coercion is really slow compared to as and it’s removed?)

    * Most of this typed from memory. There needs to be some warning that without javascript enabled I’ll completely lose what I typed and be unable to recover it by simply pressing back, like normal. My post was better written before hand, though had less in it.

  10. Mark says:

    @dx0ne @Rackdoll Thanks for the additions. There are several types of loops. Linked lists have profits, this post was mainly targetted on ‘normal loops’. BTW I really like the for-each code style too since it is very clean.

    @skyboy Thanks for sharing this advanced indepth details. I think it is *always* important to test your code/loops, and look what works. Ofcourse the ‘quick wins’ like mentioned in this post could help.
    BTW. Sorry that the blog does not work correctly without Javascript. Why is it turned off? Is that is a wordpress bug?

  11. skyboy says:

    Mark – I just browse with NoScript and don’t allow JavaScript to run unless it needs to; Not only more secure, but it also stops a lot of the poorly written JS out there from bogging down my machine. It may be that returning a 403 stopped FireFox from saving the form data for recovery. Not necessarily a bug on either side.

    Also, per a comment on Jackson’s blog, it looks like the results aren’t what they seem. https://bugzilla.mozilla.org/show_bug.cgi?id=672490
    I’m not sure what to make of this.

  12. Love articles on optimisation, and the comments here were almost just as useful! Thanks 🙂

Say something interesting

Please link to code from an external resource, like gist.github.com.