5x Faster For-In Loops
I’ve recently been notified of a way to dramatically speed up for-in
loops. I’ve tested this method out and indeed there is a 5x speedup. Employing the technique is also really easy. Unfortunately, the speedup is sometimes an illusion. Read on to learn a little more about for-in
loops and how you could potentially speed yours up by 5x.
The optimization in question today is a simple one. A for-in
loop iterates over an object’s keys. The idea is to simply use an untyped (*
) iterator rather than a String
:
// Slow for (var str:String in obj) { } // Fast for (var key:* in obj) { }
As usual, I put together a simple performance test:
package { import flash.display.*; import flash.utils.*; import flash.text.*; public class ForInTest extends Sprite { private var logger:TextField = new TextField(); private function row(...cols): void { logger.appendText(cols.join(",") + "\n"); } public function ForInTest() { stage.align = StageAlign.TOP_LEFT; stage.scaleMode = StageScaleMode.NO_SCALE; logger.autoSize = TextFieldAutoSize.LEFT; addChild(logger); init(); } private function init(): void { const SIZE:int = 1000000; var i:int; var str:String; var untyped:*; var beforeTime:int; var afterTime:int; var obj:Object = {}; for (i = 0; i < SIZE; ++i) { obj[i] = i; } row("Operation", "Time"); beforeTime = getTimer(); for (str in obj) { } afterTime = getTimer(); row("Empty Loop (String)", (afterTime-beforeTime)); beforeTime = getTimer(); for (untyped in obj) { } afterTime = getTimer(); row("Empty Loop (Untyped)", (afterTime-beforeTime)); } } }
I ran this test in the following environment:
- Release version of Flash Player 12.0.0.70
- 2.3 Ghz Intel Core i7-3615QM
- Mac OS X 10.9.1
- Google Chrome 33.0.1750.117
- ASC 2.0.0 build 354071 (
-debug=false -verbose-stacktraces=false -inline -optimize=true
)
And here are the results I got:
Operation | Time |
---|---|
Empty Loop (String) | 257 |
Empty Loop (Untyped) | 49 |
That’s a 5x speedup! How could this be? To investigate, I built a pair of example functions:
public static function forInString(obj:Object): void { for (var k:String in obj) { } } public static function forInUntyped(obj:Object): void { for (var k:* in obj) { } }
And decompiled them with the AIR SDK’s swfdump
tool:
public static function forInString(Object):void { // derivedName forInString // method_info 3 // max_stack 2 // max_regs 5 // scope_depth 0 // max_scope 1 // code_length 27 bb0 succs=[bb2] 0 getlocal0 1 pushscope 2 pushbyte 0 3 setlocal 4 4 getlocal1 5 setlocal3 6 jump bb2 bb1 succs=[bb2] 7 label 8 getlocal3 9 getlocal 4 10 nextname 11 coerce_s 12 setlocal2 bb2 succs=[bb1,bb3] 13 hasnext2 14 iftrue bb1 bb3 succs=[] 15 returnvoid } public static function forInUntyped(Object):void { // derivedName forInUntyped // method_info 4 // max_stack 2 // max_regs 5 // scope_depth 0 // max_scope 1 // code_length 26 bb0 succs=[bb2] 0 getlocal0 1 pushscope 2 pushbyte 0 3 setlocal 4 4 getlocal1 5 setlocal3 6 jump bb2 bb1 succs=[bb2] 7 label 8 getlocal3 9 getlocal 4 10 nextname 11 setlocal2 bb2 succs=[bb3,bb1] 12 hasnext2 13 iftrue bb1 bb3 succs=[] 14 returnvoid }
The only difference is this line:
11 coerce_s
That is converting the iterator from an untyped (*
) variable to a String
. That simple conversion is enough to make the untyped version 5x faster.
But then I thought “what can I do with an untyped variable?” I could insert it into an Object
, use it as a key or value of a Dictionary
, or add it as an element of an Array
or Vector.<*>
. If that’s what you plan to do with the iterators, you’ve just found an easy way to speed up your for-in
loops by 5x!
If, however, you’d like to do something with the keys of an Object
that requires them to actually be a String
, which is the normal case, the optimization disappears as soon as you treat them as a String
. To test this, I added two more loops to the above test app:
package { import flash.display.*; import flash.utils.*; import flash.text.*; public class ForInTest extends Sprite { private var logger:TextField = new TextField(); private function row(...cols): void { logger.appendText(cols.join(",") + "\n"); } public function ForInTest() { stage.align = StageAlign.TOP_LEFT; stage.scaleMode = StageScaleMode.NO_SCALE; logger.autoSize = TextFieldAutoSize.LEFT; addChild(logger); init(); } private function init(): void { const SIZE:int = 1000000; var i:int; var str:String; var untyped:*; var msg:String; var beforeTime:int; var afterTime:int; var obj:Object = {}; for (i = 0; i < SIZE; ++i) { obj[i] = i; } row("Operation", "Time"); beforeTime = getTimer(); for (str in obj) { } afterTime = getTimer(); row("Empty Loop (String)", (afterTime-beforeTime)); beforeTime = getTimer(); for (untyped in obj) { } afterTime = getTimer(); row("Empty Loop (Untyped)", (afterTime-beforeTime)); msg = ""; beforeTime = getTimer(); for (str in obj) { msg += str + ","; } afterTime = getTimer(); row("Concatenate Names (String)", (afterTime-beforeTime)); msg = ""; beforeTime = getTimer(); for (untyped in obj) { msg += untyped + ","; } afterTime = getTimer(); row("Concatenate Names (Untyped)", (afterTime-beforeTime)); } } }
This simply builds a String
out of the iterators. Here are the results:
Operation | Time |
---|---|
Empty Loop (String) | 257 |
Empty Loop (Untyped) | 49 |
Concatenate Names (String) | 458 |
Concatenate Names (Untyped) | 489 |
Now the untyped (*
) version is actually slower! Let’s look at the bytecode for these new loops:
String: 147 getlocal 15 148 getlocal 16 149 nextname 150 setlocal 7 151 getlocal 6 152 getlocal 7 153 pushstring "," 154 add 155 add 156 coerce_s 157 setlocal 6 Untyped: 108 getlocal 13 109 getlocal 14 110 nextname 111 coerce_s 112 setlocal2 113 getlocal 6 114 getlocal2 115 pushstring "," 116 add 117 add 118 coerce_s 119 setlocal 6
The only difference is this line in the untyped version:
111 coerce_s
This is included because the untyped variable must be converted to a String
to be concatenated into the msg
string. That is, it’s required to be a String
in order to be used in any operation that requires a String
and not just a *
. Since the coerce_s
is back, the optimization disappears.
In conclusion, if you don’t need your iterators to be a String
you can get a 5x speedup in your for-in
loops by simply not typing the iterator as a String
and using the untyped (*
) type instead. If, however, you do need them to be a String
, you’re out of luck.
Spot a bug? Have a question or suggestion? Post a comment!
#1 by alebianco on February 24th, 2014 ·
in the last bytecode comparison, are the labels inverted?
it doesn’t make sense to me that the “String:” version has the coerce_s instruction twice while the “Untyped:” one doesn’t have it.
also, what’s the difference between getlocal n and getlocal2? i guess it must be some kind of shortcut, but is it faster?
#2 by jackson on February 24th, 2014 ·
Thanks for catching this. I’ve corrected it in the article.
#3 by alebianco on February 24th, 2014 ·
just found this http://jacksondunstan.com/articles/699 that answers my question … cheers
#4 by 4as on February 24th, 2014 ·
Hey, great to see that this speed-up turned out to be legit.
The most practical use and the reason I found about it, is that the untyped keys are actually stored as numbers whenever possible, as in:
So when you need to do some calculations with a number, key:String will have to be converted, while key:* will just be casted.
At least that is what I am getting in my tests.
#5 by jackson on February 24th, 2014 ·
This is an interesting find and there turns out to be a lot more to it. I’ll do a followup article exploring the mysteries of the
Object
class’ keys. Thanks for the tip!#6 by 4as on February 25th, 2014 ·
Glad I could help!
#7 by reversiblean on February 24th, 2014 ·
That was really helpful! Gonna tweak my project now : )
#8 by reversiblean on February 24th, 2014 ·
I could find no significant difference in my tests.
for each(var obj:XML in xmlList)
{
function(obj.@x, obj.@y);
}
Is that because attributes values of XML are in the type String?
#9 by Vjekoslav Ratkajec on February 24th, 2014 ·
Example from Jackson was concentrating on for in, not for each loop. ;-)