— Forest and the Trees

For Each Is Fastest

I was doing some coding where optimization really mattered and made a little loop test. The ‘for each’ loop is the fastest – even when you need an index.

Also of note, the debug player has ‘incrementing while’ as faster than the ‘do while.’ And both as faster than ‘for each with counter.’ There is a huge difference between the performance of the debug and the release player in Flex. (Using the Flex Beta 3 Release 3 here.) Check out my friend James’ test for more info on the diffs. He has a lot of benchmarking around typing vars here. Those posts completely refute some earlier, widely read, posts that suggested you should never use int. Lesson here is, make sure you test performance with a version published for release. Unfortunately, that means you can’t trust trace statements for your benchmarking. You need to put your time displays in a text field.

Also, I did some tests, and it appears that ‘for each’ preserves order – which is obviously very important to know. If you have found different, please post a comment. Example here. View source enabled.

8 comments
  1. Tom Carden says: January 13, 200811:26 am

    It’s an interesting set of tests, but I don’t get the same result. When I click loop, here’s what I get back:

    for each: 29
    for each var in loop: 28
    for each w/ counter: 30
    incrementing while: 15
    decrementing while: 15
    incrementing do while: 14
    deccrementing do while: 13
    for loop: 14
    for loop decrementing: 13
    for in loop: 5441

    This implies decrementing for/while loops may be faster for me?

    Before drawing major conclusions I think it would be better practice to use a new array for each loop, and to repeat the tests several times and report min/max and average.

    I’m sure ‘for each’ always preserves order looping over an Array, but I don’t think order is guaranteed if you iterate over Objects or Dictionaries. Not sure for XML.
    http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/statements.html#for_each..in

    (I’m using Firefox 2.0.0.11 and Flash 9,0,115,0 on Mac OS 10.5)

  2. Doug says: January 13, 20082:14 pm

    Thanks for the comment Tom. I also ran across these tests which seem to be more in line w/ your numbers. Maybe it’s Mac vs. Win – I’m using both XP Pro and Vista and for each was fastest for both. I’ll post numbers from different machines over the next few days.

  3. Doug says: January 14, 200811:19 am

    for each: 33

    for each var in loop: 31

    for each w/ counter: 32

    incrementing while: 69

    decrementing while: 67

    incrementing do while: 85

    deccrementing do while: 69

    for loop: 72

    for loop decrementing: 67

    for in loop: 2894

    Vista Business 9,0,115,0 Firefox 2.0.0.1.1

  4. josh says: January 28, 200812:51 pm

    Interesting. I’m surprised there’s a difference here, and especially surprised that it’s a factor of two. Thanks for finding this.

    System info: winXP, ff 2.whatever, FP 9.0.115.0 debug.

    ***************************
    for each: 44

    for each var in loop: 43

    for each w/ counter: 46

    incrementing while: 96

    decrementing while: 97

    incrementing do while: 95

    deccrementing do while: 99

    for loop: 98

    for loop decrementing: 92

    for in loop: 7272

  5. Daniel R. says: February 7, 20089:31 am

    In looking at these results I was trying to figure out why the for..in loop was drastically slower. My speculation is that because a for..in returns each name as a String, behind the scenes an int to String conversion is occurring in order to return the index as a String. When the returned name is used to lookup the index in the Array, a String to int conversion is happening. As a result, to iterate over the Array with for..in, 2*Array.length type conversion operations are being done, which has got to be slow.

  6. Doug says: February 7, 200812:16 pm

    Updated the test – now the array is created before each loop and you can turn off the typing and the addition. When you turn that off, for in is still slowest, but for each is second slowest. However, when you do that, you’re not accessing properties of the array in the loop making the loop a lot less useful.

  7. Daniel R. says: February 7, 200810:25 pm

    It looks like whatever technique Array uses internally to recognize that the array access argument is a String is significantly slower than manually doing it. For example:

    for (p in a) {
    if (addTypeValues) {
    t += int(a[int(p)]);
    }
    }

    runs about 5 times faster than not casting p before passing it in. This is probably related to the fact that Array is dynamic and that means the String may represent a runtime added attribute. This stems far from finding the fastest way to loop over and sum an Array’s elements, I was trying to determine why for..in was dramatically slower :)

  8. jlGauthier says: February 9, 200811:05 am

    Daniel >>
    Yea I’ve thought a lot about why its so much slower, in the end i came up with..

    The fastest way to look into an array is a uint, this is natural since arrays have a max index of uint.MAX_VALUE.

    read / write to an array with an int, and you may be negative, in which case you write to the object not the array.The negative number would be converted to a string for an id.

    With a Number requires Number –> uint. this a slow opperation because Number is structurally more like int than uint. Number–>int–>uint would be the fastest path but the compiler must allow that you might be retarded. And that you may have wanted to write a negative number to the dynamic object. or that you may have wanted to access object.NaN on your array. so it has to go wicked slow, checking for nans and infinitys before allowing a coercion to uint which would discard those states.

    just remember this :
    var a : Array = [];
    var x : Number;
    a[x] = 5;
    var poo : String = x.toString();
    trace(a[poo]); // 5
    trace(a.length); // 0

    Thats why array access with numbers is about 5 times slow than access with uints.

Submit comment