JacksonDunstan.com

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));
		}
	}
}

Run the test

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

For-In Performance Graph

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:

var obj:Object = new Object();
obj[3] = "three"; // typeof() for this key returns 'number'
obj["20"] = "twenty"; // typeof() for this key also returns 'number'!
obj[obj] = "test"; // typeof() returns a string

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. ;-)

5x Faster For-In Loops

Comments