FAST iterators for StringMap

StringMap is probably most used class in Haxe (I think only Array is used more often). Probably you never use it directly, rather you use Map<String, SomeType>, which use haxe.ds.StringMap under the hood.

Since it is used very often, it must be very fast. At least it should be… So let’s go a little deeper and look how haxe.ds.StringMap is implemented for javascript target.

Important note: haxe team rejected my proposal (and I agree with them), so it is now called LinkedMap, super optimized for js target with default fallback for all other targets. Link.

public function set( key : String, value : T ) : Void {
    untyped h["$"+key] = value;
}

public function get( key : String ) : Null<T> {
    return untyped h["$"+key];
}

public function exists( key : String ) : Bool {
    return untyped h.hasOwnProperty("$"+key);
}

Looks pretty good. Moreover, there is new haxe.ds.StringMap implementation in Haxe repo:

inline function isReserved(key:String) : Bool {
    return untyped __js__("__map_reserved")[key] != null;
}

public inline function set( key : String, value : T ) : Void {
    if( isReserved(key) )
        setReserved(key, value);
    else
        h[cast key] = value;
}

public inline function get( key : String ) : Null<T> {
    if( isReserved(key) )
        return getReserved(key);
    return h[cast key];
}

public inline function exists( key : String ) : Bool {
    if( isReserved(key) )
        return existsReserved(key);
    return h.hasOwnProperty(key);
}

Looks even more good – no more string concatenation for most cases.

But…

What about iteration?

public function keys() : Iterator<String> {
    var a = [];
    untyped {
        __js__("for( var key in this.h ) {");
            if( h.hasOwnProperty(key) )
                a.push(key.substr(1));
        __js__("}");
    }
    return a.iterator();
}

public function iterator() : Iterator<T> {
    return untyped {
        ref : h,
        it : keys(),
        hasNext : function() { return __this__.it.hasNext(); },
        next : function() { var i = __this__.it.next(); return __this__.ref["$"+i]; }
    };
}

WAT? Each time you want to iterate (over keys or values), it create a new array, push all the keys into it and return an iterator over this array (new implementation use similar approach).

It is slow!

I was curious, what benefits can be obtained by making the implementation with fast iteration. The idea was to combine hashmap and doubly linked list:

 

 

On the one hand hashmap allows to get value by key fast, on the other hand doubly linked list allows to iterate fast. It is almost oblivious that iteration will be super fast, but what about set / get?

public function set(key:String, value:T):Void {
    var _key:String = (untyped __js__("__z_map_reserved")[key] == null ? key : "$" + key);

    if (untyped data.hasOwnProperty(_key)) {
        untyped data[_key].value = value;
    } else {
        untyped data[_key] = {
            prev: tail,
            key: key,
            value: value,
            next: null
        };

        if (tail != null) {
            untyped data[tail].next = _key;
        }

        tail = _key;

        if (head == null) {
            head = _key;
        }
    }
}

public function get(key:String):Null<T> {
    if (untyped __js__("__z_map_reserved")[key] != null) {
        key = "$" + key;
    }

    if (untyped data.hasOwnProperty(key)) {
        return untyped data[key].value;
    } else {
        return null;
    }
}

Huh, quite a lot of code. We need a benchmark!

(click on image to enlarge)

As expected, iteration is super fast! 144% boost in worst case (1000 entries on Firefox), 4313% boost in best case (100000 entries on Chrome). However it is not a realistic situation, usually you would use at least some set, many get and/or exists.

Combined benchmark tests iteration along with get,  set and exists. FastIteratingStringMap it still better than standard on Chrome and Safari. But strange thing happens on Firefox – old StringMap implementation is better than FastIteratingStringMap in most cases, moreover it is better than new StringMap in all cases! Probably memory allocation in Firefox is optimized a way better than in Chrome and Safari, but JIT in Firefox is optimized worse. (also note that firefox beats safari by absolute values in some cases, I like firefox 🙂 )

And what about case, when you don’t any iteration? FastIteratingStringMap is better than new StringMap on Firefox in most cases, and not-so-worse than old StringMap on Chrome / Safari.

Conclusion: it is worth to try FastIteratingStringMap.

When is possible to get a benefit?

Basically:

var map:Map<String, TypedValue>;

...

public function apply(view:View) {
    for (key in map.keys()) {
        if (!view.inflate(key, map[key])) {
            throw new Error("Apply error: unsupported attribute " + key);
        }
    }
}

– Yes, because the is an iteration and the method is called often.

var map:Map<String, Xml> = new Map<String, Xml>();

for (node in root.elements()) {
    map[node.nodeName] = node;
}

var ps = new ParticleSystem();

ps.emitterType = parseIntNode(map["emitterType"]);
ps.maxParticles = parseIntNode(map["maxParticles"]);
ps.positionType = 0;
ps.duration = parseFloatNode(map["duration"]);
ps.gravity = parseVectorNode(map["gravity"]);

...

– No, because the is no iteartion at all.

How to use?

Currently it is included into zame-haxe-miscutils library.

To install it:

haxelib git zame-miscutils https://github.com/restorer/zame-haxe-miscutils.git