Archive for June, 2009
Recently I stumbled upon a question on stackoverflow.com, where someone wanted to know about the quickest way to iterate over an Array. In response, someone else pulled out a benchmark for .NET, which showed, for loops would be faster. But i was quite sure, this is not at all the case for AVM2. So I did a little research and expanded my quest to examine iteration as such, on any native AVM2 objects, that are suitable for collections. Apart from Array, Object and Dictionary, this includes Vector, which is only available for Flash Player 10. Both iteration methods provide key and value. Although it does not really make sense to use Object and Dictionary, if they contain dense numerical keys. In the end, it looks like so:
//for loop for (key = 0; key < size; key++) value = iterable[key]; //for each loop key = 0; for each (value in iterable) key++;
You can grab the whole source >here<
I found, that for each loops are more than two times faster, sometimes even significantly. I also found, that speed depends on the type of the variable the collection is stored into. So here some numbers (tested on Debug FlashPlayer 10.0 r22 for Windows XP, on a Core2Duo with 2Ghz):
testing Vector as Vector.<int> 200 repetitions with collections of size 500000 > for loops needed 48.595 msecs > for each loops needed 19.11 msecs > factor: 2.5429094714809 testing Vector as * 200 repetitions with collections of size 500000 > for loops needed 54.65 msecs > for each loops needed 16.125 msecs > factor: 3.3891472868217054 testing Vector as Object 200 repetitions with collections of size 500000 > for loops needed 54.44 msecs > for each loops needed 16.335 msecs > factor: 3.332721150902969 testing Array as Array 200 repetitions with collections of size 500000 > for loops needed 50.335 msecs > for each loops needed 15.46 msecs > factor: 3.2558214747736094 testing Array as * 200 repetitions with collections of size 500000 > for loops needed 54.19 msecs > for each loops needed 15.455 msecs > factor: 3.506308637981236 testing Array as Object 200 repetitions with collections of size 500000 > for loops needed 54.315 msecs > for each loops needed 15.335 msecs > factor: 3.5418976198239323 testing Dictionary as Dictionary 200 repetitions with collections of size 500000 > for loops needed 61.17 msecs > for each loops needed 24.16 msecs > factor: 2.5318708609271523 testing Dictionary as * 200 repetitions with collections of size 500000 > for loops needed 62.395 msecs > for each loops needed 24.205 msecs > factor: 2.577773187357984 testing Dictionary as Object 200 repetitions with collections of size 500000 > for loops needed 62.155 msecs > for each loops needed 23.91 msecs > factor: 2.599539941447093 testing Object as * 200 repetitions with collections of size 500000 > for loops needed 64.125 msecs > for each loops needed 26.35 msecs > factor: 2.433586337760911 testing Object as Object 200 repetitions with collections of size 500000 > for loops needed 64.09 msecs > for each loops needed 26.245 msecs > factor: 2.4419889502762433
now some explenations, where this comes from:
- to people not from the ECMA-world: Objects, i.e. instances of the class Object, are simply hashes, if you will. someObject.someProperty and someObject[“someProperty”] are equivalent … thus array access and property access are the same.There is not a lot of difference between Arrays and Objects. Except that Arrays handle numerical keys a little differently, that is, they maintain an order, and expose a length, as well as Array manipulation functions, and now new in AS3, iteration functions. Array do have a sweet spot, performancewise, when they are dense and numerical. Then, they are faster than Objects, when it comes to array access.
- consider a for each loop. this is some runtime internal magic, written C or C++, which runs considerably fast and retrieves the value, while you calculate the key with a simple incrementation. for the for loop in turn, you need the incrementation, which is not costy, and you need to evaluate the condition, which is AVM2 bytecode, but still ok, and to retrieve the key, you need an array access, which also consist of executing the opcodes, and the implementation of the array access itself. The Array in ActionScript is not just a block of references in memory. It’s some weird multipurpose collection, with complicated access routines, that are all encapsuleted in the array access. now for each iteration does not necessarily preserve order, only for Vectors, and Arrays, but it does not rely on the ambiguous array access, since it comes from the runtime.
it seemed a little suprising to me, that there is a performance difference between * and Object. This seemed really strange. Also, since there is no rule for that. Accessing through the exact type is faster, as you can see. This is, because there are 5 different array accesses in flash. For Object, Dictionary, Array, Vector and Proxy. If the variable is typed, the compiler probably uses this information to hardwire the right array acces, instead of looking it up at runtime. Just a guess, though. One last note: if you create collections, subclassing Proxy, then simple for loops are much faster, since the require only one call to the proxy per step.