Some time ago I wrote a post about an idea, how StringMap could be implemented (for js target) to have ability to iterate fast. I continued to work in this direction, and finally idea evolved into nearly final implementation.
- Tests were added;
- Special iterators implementation for case when there is no data in the map;
- Benchmark code instantiate a specific class now (instead of using creator function), to give Haxe ability to optimize map usage and inline functions;
- Haxe 3.2 (from development branch) was used to compile benchmark;
- Another idea was tested (CachingKeysStringMap);
- Constant time complexity.
Test were added
The most important thing that has been done – is is a simple tests, to ensure that the Map is working properly.
Shame on me – there were several bugs in initial implementation, but due to tests all of them (I hope 🙂 ) was fixed.
Special iterators implementation for case when there is no data in the map
In discussion thread on google groups, Sven Bergström said: “In my cases I found that shielding map iterator with a simple length check gave me a huge bump in performance on c++ target”.
In my point of view, this makes sense on js also, and currently FastIteratingStringMap will return special static emptyIterator in that case, so no memory will be allocated when there is no data in the map.
Benchmark code instantiate a specific class now
Initially, I use single benchmark function, which accepts Map.IMap<String, Int>, and several creator functions, which returns new map object. However, this approach didn’t allow Haxe to use it powerful optimization techniques.
Currently benchmark was generated via benchmark generator (macro would be more haxeish, but generator is simplier). Every benchmark function has it own variant for each Map realization, and now Haxe can inline various functions, especially for NewStringMap (StringMap from Haxe 3.2).
Haxe 3.2 was used to compile benchmark
Along with specific class instantiation, this give more performance boost for NewStringMap.
Also I added “inline” modifier to get / set / exists functions of OldStringMap, to allow old map code to use improved Haxe 3.2 optimization techniques.
Another idea was tested
Doubly linked map was not the only one idea of implementation. Another idea is to use NewStringMap code as base, and additionally keep array of keys.
Although idea was promising, it turned out that removing from map is terribly slow in all browsers except Chrome.
Benchmark results
(click on image to enlarge. benchmark code)
As you can see, FastIteratingStringMap has pretty good performance, it even somehow beat OldStringMap and CachingKeysStringMap in “Without iteration” benchmark on Chrome (JIT is magic 🙂 ).
Constant time complexity
The most exciting fact about FastIteratingStringMap is that every operation takes constant time. I really like that fact 🙂
| OldStringMap / NewStringMap | CachingKeysStringMap | FastIteratingStringMap | |
| set | O(1) | O(1) | O(1) |
| get | O(1) | O(1) | O(1) |
| exists | O(1) | O(1) | O(1) |
| remove | O(1) | O(n) where n is keys count | O(1) |
| keys | O(n) where n is keys count | O(1) | O(1) |
| iterator | O(n) where n is keys count | O(1) | O(1) |
P. S.
You can notice that FastIteratingStringMap implementation looks similar to java.util.LinkedHashMap (except that it use native javascript objects as hash instead of implementing it own).
It’s just a coincidence. Although I did not have the goal to have a guaranteed iteration order, it turned out that this is the most efficient way to have fast iterators.
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