As I have previously reported, lots of Java programmers are adopting Flex. One question that Java programmers always ask is "where are my beloved collections classes?"

First, the good news: this blog will point you to some excellent collection classes, and give you some information on what makes for a fast program. The bad news: ActionScript 3 does not support generics. Back to Java 1.4 land :(

I wrote a quick benchmark for a Flex version of HashMap, based on dynamic objects.  When I ran it in debug mode I found:
50,000 reads: 0.062 second
50,000 writes: 4.953 seconds

Obviously dynamic objects perform reasonably well for reads, but writes are horribly slow! Source code for this class and others, written for ActionScript using dynamic classes is available from http://code.google.com/p/j2as3. The benchmark programs mentioned in this blog are also available from the same Google Code project.

as3ds is an excellent data structures project for ActionScript, and it supports the following interfaces and classes:

Michael Baczynski, the author of as3ds, has a good writeup on the above data structures on his web site.

As3ds uses the Flash Dictionary class to implement HashMap, and the implementation is fairly faithful to the original Java class. Because get is a reserved word in ActionScript, the as3ds version of HashMap uses insert and find instead of put and get. I did not think that the names of the two methods were appropriate; to me, 'insert' connotes the unconditional creation of a new entry, and 'find' should return a reference, not a value.  I renamed the methods to getItem and put, and then created an svn patch so future versions could be similarly modified without fussing about:

Index: src/de/polygonal/ds/HashMap.as
===================================================================
--- src/de/polygonal/ds/HashMap.as	(revision 120)
+++ src/de/polygonal/ds/HashMap.as	(working copy)
@@ -74,7 +74,7 @@
 		 * @param key The key.
 		 * @param obj The data associated with the key.
 		 */
-		public function insert(key:*, obj:*):Boolean
+		public function put(key:*, obj:*):Boolean
 		{
 			if (key == null)  return false;
 			if (obj == null)  return false;
@@ -112,7 +112,7 @@
 		 * @return The data associated with the key or null if no matching
 		 *         entry was found.
 		 */
-		public function find(key:*):*
+		public function getItem(key:*):*
 		{
 			var pair:PairNode = _keyMap[key];
 			if (pair) return pair.obj;

I modified the benchmark to test the as3ds version of HashMap.  When I ran it in debug mode I found:
50,000 reads: 0.051 seconds
50,000 writes: 0.063 seconds

This shows that Dictionary is about the same speed as dynamic classes for reads, but about two orders of magnitude faster for writes.

After I disabled debug mode off by passing -debug=false to the compiler; performance increased about 300%, and was about 300x faster than the version using dynamic classes, running in debug mode:

50,000 reads: 0.016 seconds
50,000 writes: 0.015 seconds

50,000 reads: 0.016 seconds
50,000 writes: 0.015 seconds

Like as3ds, the Java implementation of HashMap does not show a significant performance difference between reads and writes, but it ran at the same speed as the ActionScript equivalent.

ActionScript Benchmark

<?xml version="1.0" encoding="utf-8"?>
<mx:Application 
    creationComplete="benchmark()"
    xmlns:mx="http://www.adobe.com/2006/mxml">

    <mx:Script>
        <![CDATA[
            import j2as3.util.StopWatch;
            import de.polygonal.ds.HashMap;
            import mx.formatters.NumberFormatter;	  

            private var stopWatch:StopWatch = new StopWatch();
            private var hashMap:HashMap = new HashMap();
            private var numberFormatter:NumberFormatter = new NumberFormatter();

			  
            /** Might be a better test if it read six to ten values */
            private function reads(readCount:int):void {
                hashMap.insert("key", "value");
                stopWatch.startTimer();
                for (var i:int=0; i<readCount; i++)
                    hashMap.find("key");
                stopWatch.reportElapsedTime(numberFormatter.format(readCount) + " reads");
            }
            /** Might be a better test if it wrote six to ten values */
            private function writes(writeCount:int):void {
                stopWatch.startTimer();
                for (var i:int=0; i<writeCount; i++)
                    hashMap.insert("key", i);
                stopWatch.reportElapsedTime(numberFormatter.format(writeCount) + " writes");
            }
            private function benchmark():void {
                msg.text = reads(50000) + "; ";
                msg.text += writes(50000);
            }

        ]]>
    &lt;/mx:Script>
    &lt;mx:Label id="msg" />

&lt;/mx:Application>

StopWatch.as

package j2as3.util {
    import flash.utils.getTimer;    
    import mx.formatters.NumberBaseRoundType;
    import mx.formatters.NumberFormatter;


    /** Measures and reports elapsed time. */
	public class StopWatch {
        public var millis:uint = 0;
        private static var tenthsSecondFormatter:NumberFormatter = new NumberFormatter();

        public function StopWatch() {
            tenthsSecondFormatter.precision = 3;
            tenthsSecondFormatter.rounding = NumberBaseRoundType.NEAREST;
        }
        public function reportElapsedTime(msg:String):Number {
            var now:uint = getTimer();
            var elapsedSeconds:Number = (now - millis) / 1000.0;
            var reportMsg:String = msg + ": " + tenthsSecondFormatter.format(elapsedSeconds) + " seconds";
            trace(reportMsg);
            millis = now;
            return reportMsg;
        }
        
        public function startTimer():void { millis = getTimer(); }
    }
}

Java Benchmark

import j2as3.utility.*;
import java.text.NumberFormat;
import java.util.HashMap;
/** Test of Java 1.4 style collection performance.
 * Meant to mirror the ActionScript benchmark, not to be terribly useful. */
public class HashMapBenchmark {
    private StopWatch stopWatch = new StopWatch();
    private HashMap hashMap = new HashMap();
    private NumberFormat numberFormat = NumberFormat.getNumberInstance();
    /** Might be a better test if it read six to ten values */
    public void reads(int readCount) {
        hashMap.put("key", "value");
        stopWatch.startTimer();
        for (int i=0; i<readCount; i++)
            hashMap.get("key");
        stopWatch.reportElapsedTime(numberFormat.format(readCount) + " reads");
    }
    /** Might be a better test if it wrote six to ten values */
    public void writes(int writeCount) {
        stopWatch.startTimer();
        for (int i=0; i<writeCount; i++) 
            hashMap.put("key", new Integer(i).toString());
        stopWatch.reportElapsedTime(numberFormat.format(writeCount) + " writes");
    }
    public static void main(String[] args) {
    	HashMapBenchmark benchmark = new HashMapBenchmark();
    	benchmark.reads(50000);
    	benchmark.writes(50000);
    }
}

StopWatch.java

package j2as3.utility;

import java.text.DecimalFormat;

public class StopWatch {
    public long millis = 0L;
    private static DecimalFormat tenthsSecondFormatter = new DecimalFormat(); 
    public void startTimer() { millis = System.currentTimeMillis(); }
    public double reportElapsedTime(String msg) {
        long now = System.currentTimeMillis();
        double elapsedSeconds = (now - millis) / 1000.0;
        System.out.println(msg + ": " + tenthsSecondFormatter.format(elapsedSeconds) + " seconds");
        millis = now;
        return elapsedSeconds;
    }
}

_______________________________

Mike Slinn
Independent full-service software contractor and author
http://slinnbooks.com
http://mslinn.com

Read more from Mike Slinn.