Fast hash tables

The Dictionary class – a dead end for other targets

Recently I started to adjust my code with the C++ and JavaScript haXe target in mind. I have to say it’s really amazing to see your code running on different platforms. This offers an incredible amount of flexibility! While almost everything worked out of the box, the biggest hurdle was to find a replacement for the flash.utils.Dictionary class, which I was using extensively in my library.
Although the haXe API already offers a Hash and IntHash class (both using the Dictionary for the flash target), I’ve decided to implement my own hash tables so they blend in nicely into my ds library.

What are hash tables?

A hash table is a very important and fundamental data structure in computer science. It offers rapid insertion, access and deletion of sparse data. This is achieved by distributing the data amongst a fixed number of slots using a hash function.

There are many ways of implementing hash tables, but from my experience (and from reading dozens of papers) the easiest solution is something called a ‘standard-chain hash table’, which simply uses linked lists as a collision resolution scheme. When linked lists are replaced with dynamic arrays, the result is called an ‘array hash table’, which offers a smaller memory footprint because it eliminates nodes and pointers all together and is more cache friendly.

Other implementations include ‘bucketized cuckoo hash tables’ or ‘open-address hash tables’ using techniques like linear probing or double hashing for collision resolution. Those are interesting if you are into computer science, but from the point of view of a game programmer, they don’t offer any advantages, but have drawbacks of some kind (problems with high load factor, difficult to implement, complex hashing and so on).

The hash table implementation which I’ve included in the ds library is somewhere in between a standard-chain hash table and an array hash table – the data is stored in an array while still offering basic advantages of a linked list, namely removal in constant time and move-front-on-access by pointer manipulation.

So the procedure for searching a key in my code is:

  1. Hash the key to acquire a slot.
  2. Check if the slot is empty. If it’s empty, the key does not exist and the search fails.
  3. Otherwise scan the array a key at a time until a match is found or until the array is exhausted (search fails).
  4. If the key was found, move it to the front of the list by pointer manipulation. This way further queries to the same key take less time (optional).

Implementation overview

The latest version of my ds library now contains a bunch of additional interfaces and classes:
Classes implementing de.polygonal.ds.Map:

  • IntIntHashTable – A hash table using 32-bit integers for both keys and values.
  • IntHashTable<T> – A generic hash table using 32-bit integer keys.
  • HashTable<K, T> – A generic hash table. Keys have to implement Hashable.
  • HashMap – The existing wrapper for the Dictionary class, which was updated so it now implements Mapinstead of Collection. Flash only!

Classes implementing de.polygonal.ds.Set:

  • IntHashSet – Similar to IntIntHashTable, this is a set for integer values.
  • HashSet<T> – A generic set. Values have to implement Hashable.
  • ListSet<T> – A simple set backed up by a list; this is a replacement for the former Set class that now defines an interface.

IntIntHashTable and IntHashSet are the most important ones since they provide the core functionality used in other classes. IntHashTable, HashTable and HashSet extend their behavior via composition.

The core classes use ‘alchemy’ memory and lots of inlining to achieve very good performance. I’ve documented all classes, and I hope it’s not that difficult to understand. Some notes:

  • Although hash tables implement a Map interface, they allow multiple entries of the same key following the FIFO rule. If you want to make sure that the hash table contains unique keys, use the setIfAbsent(key, val) method or manually check for existence using hasKey(key) before calling set(key, val). Example:

    //duplicate key
    var hash = new IntIntHashTable(1024);
    hash.set(1, 2);
    hash.set(1, 3);
    trace(hash.hasKey(1)); //true
    trace(hash.get(1)); //2
    hash.clr(1);
    trace(hash.hasKey(1)); //true
    trace(hash.get(1)); //3
    
    //ensure unique keys
    var success = myHashTable.setIfAbsent(1, "value1"); //success == true
    var success = myHashTable.setIfAbsent(1, "value2"); //success == false
    //or
    if (!myHashTable.hasKey(1)) myHashTable.set(1, "value");
  • As you know, the Dictionary lets you use the object ‘identity’ as a key, and not the value returned from calling toString() on it. This behavior is not available in JavaScript and other targets. So objects used as keys in a HashTable or as values in a HashSet have to implement the Hashable interface or extend from the abstract class HashableItem. Hashable defines a single method getKey() (or just a field key if using haXe) returning an unique integer value to identify the object. This is a little awkward, but I currently don’t see any other (simple) solution. Example:

    class Foo implements Hashable {
      public var key(default, null):Int;
      public function new() { key = HashKey.next(); }
    }
    //or
    class Foo extends HashableItem {
      public function new() { super(); }
    }
    ...
    var item = new Foo();
    myHashTable.set(foo, "myValue");
  • For the AS3 users out there, I’m providing the following swc files (xxx stands for debug or release):
    • ds_xxx_alchemy.swc: ds version with alchemy support for FP10.
    • ds_xxx_.swc: ds version without alchemy support but using Vectors for FP10.
    • ds_xxx_fp9.swc: ds version without alchemy support but using Arrays for FP9.

    When using the alchemy version, it’s important to call free() to release all used memory once the object is no longer needed.

The Dictionary class

If you want to take a look at the hash table implementation used in the Dictionary, you can do so by downloading the Tamarin source code and open the file core/MultinameHashtable.cpp or core/avmplusHashtable.cpp. From my understanding (please correct me if I’m wrong!) flash uses an open-addressed hash table with quadratic probing for resolving collisions. This means that keys are directly stored within hash slots, while my hash table is open: in the case of a hash collision, a single slot stores multiple entries, which must be searched sequentially. Also the Tamarin implementation automatically rehashes the hash table when it’s full (load factor > 0.75), while I’m only allocating more capacity and leave rehashing to the user, because it’s an expensive operation and performance only slightly degrades when the load factor goes beyond one.

Performance

So here are the numbers for the IntIntHashTable. All results were done with the latest Flash Player for Windows. You can compile & run the benchmark on your own, but I guess you have to adjust the number of iterations or you get a script timeout.

The chart below shows how the HashTable behaves when a slot contains more than one key. A load factor of 1 means that each slot contains only one key/value pair. A load factor of 2 means each slot has two pairs that have to be searched sequentially and so on.

hash table benchmark

So it’s very predictable. A load factor of 10 makes the hash table 10x slower.

The chart and table below compares read/write/access operations between a IntIntHashTable and the Dictionary. Both structures are preallocated to minimize the time it takes to find a key.

hash table benchmark

size 1024 2048 4096 8192 16384 32768 65536 131072
IntIntHashTable 0,08 0,14 0,29 0,57 1,15 2,29 4,75 10,03
Dictionary 0,84 1,54 3,3 6,7 16,5 44,76 97,72 218,32
x times faster 10x 11x 11x 11x 14x 19x 20x 21x

The last chart compares the generic HashTable implementation against the Dictionary class. The difference is not too big, still the HashTable is about 20-30% faster.

hash table benchmark

size 1024 2048 4096 8192 16384 32768 65536 131072
HashTable 0,28 0,57 1,15 2,3 4,7 9,28 20,55 39,45
Dictionary 0,37 0,72 1,35 2,73 5,6 13,48 27,45 52,48
x times faster 1,32x 1,26x 1,17x 1,19x 1,19x 1,45x 1,34x 1,33x

Conclusion

While in most cases you won’t notice a big difference I have some applications in mind like hierarchical spatial hash tables for collision pruning where the extra speed should be very noticeable. So what’s next for ds? Probably a deque structure and lots of bug fixing of course ;).

14 Comments

  1. Hi Michael,

    great work. It would be interesting to see an implementation like HashTable<A> perform versus Dictionary because IntIntHashTable with both key and value typed int is a little bit biased.

    If you really want to compare performance you should take an implementation that offers the same features as Dictionary.

    Best,

    Joa

  2. Hi Joa – the point is that if you don’t need all the features of a Dictionary you can do a lot better :) I’ve just updated the article so it now includes a chart comparing the Dictionary to the HashTable. There is room for optimization here since the HashTable just wraps IntIntHashTable. I would need to find a custom solution here, basically get rid of all the array access and use linked lists instead.

  3. It seems that the new ds libs generates runtime errors if compiled against mxmlc.
    When I use the IntIntHashTable, flashPlayer moans “VerifyError #1111: de.polygonal.ds::IntHashTable can’t implement de.polygonal.ds.Set”

    While using IntHashTable in .as code, after firing-up the .swf, there is other error:
    “VerifyError #1111: de.polygonal.ds::ListSet can’t implement de.polygonal.ds.Set”

    Don’t know if this error is Haxe-related or ds-related, I’ve taken a look into ds code and got lost in preprocessor directives :)

  4. Hi, I can’t reproduce it, works just fine when compiling with FlexSDK4+FlashDevelop against the swc files. Can you send me a code snippet?

  5. When you said that it worked I was hoping that I can get it working too, but I’ve compiled it on my both macbooks, one on OSX Tiger, second on Leopard, with SDK’s: 3.5.0 , 4.0.0, 4.1.0, 4.5.0.1.
    All generated swf’s show this VerifyError 1111 on windows and osx players.

    The code of the snippet is as simple as possible:
    /// HashTableSNPT.as ///
    package
    {
    import de.polygonal.ds.IntIntHashTable;
    import flash.display.Sprite;

    public class HashTableSNPT extends Sprite
    {
    private var hash:IntIntHashTable;
    }
    }

    This is the compiled .swf:
    http://dl.dropbox.com/u/1268089/hash3-pure.swf

    This is same as above, but it tries to draw green rectangle in the constructor, so if somebody didn’t have a debug player he would have seen that no green rectangle appears, due to verifyError: http://dl.dropbox.com/u/1268089/hash2-shape.swf

  6. I’ve spotted a bug with the MemoryManager which is not working properly with the swc files.. I’ll try to fix that soon but this issue throws a regular error. VerifyError 1111 means that the byte code at some point is messed up (function bodies not allowed in interfaces)

    I’m basically compiling with:
    mxmlc -sp ./src -library-path ./lib/ds_debug.swc -debug ./src/HashTableSNPT.as -o ./bin/foo.swf

    this produces a working swf. Sadly I can’t test it on osx. could post the full compile command line?

  7. You’ve had a good intuition – after several recompiles it turned out that the source path defined in flex_config.xml caused that VerifyError.
    I’ve had sources of as3ds in my source path and that confused FlashPlayer.
    BTW I think that compiler should do something with ambiguous classes in compile time.

  8. It seems that the new ds libs generates runtime errors if compiled against mxmlc. When I use the IntIntHashTable, flashPlayer moans “VerifyError #1111: de.polygonal.ds::IntHashTable can’t implement de.polygonal.ds.Set” While using IntHashTable in .as code, after firing-up the .swf, there is other error: “VerifyError #1111: de.polygonal.ds::ListSet can’t implement de.polygonal.ds.Set” Don’t know if this error is Haxe-related or ds-related, I’ve taken a look into ds code and got lost in preprocessor directives :)

  9. Hy, I saw in one of your posts an implementation of an A* algorithm =>> http://lab.polygonal.de/2007/06/13/data-structures-example-the-graph-class/ =>> The animation under the title “A graph-based A* pathfinder”.

    I was wondering if you can tell me how did you make the map? How did you manage to put the coordinates to the nodes so that they are spread in different locations on the map?

    I would be grateful for an answer.

  10. Glidias

    Do you have a benchmark result for IntHashTable? I’d like to have each Int key point to a linked-list pool object instance, and am wondering how fast it is compared to Dictionary.

  11. Am I correct in saying that while these classes are superior to Dictionary in performance that none of them replicate Dictionary’s ability to use an Object (or object reference) as a key? Do you have ideas about how to do that efficiently? My current implementations when that is required for JS/C++ are rather naïve.

  12. That is correct. My hash tables only work with integer keys. For storing objects, I simply store a unique integer with each object simply by incrementing a global counter variable. But I don’t fully understand your question: AFAIK you simply can’t use the object identity in JS as a key. doing something like dictObject[myObject] = myObject converts myObject to a string and then uses it as a key. In C++ you can use pointers as hashtable keys.

  13. Ian Callaghan

    Looks like great stuff. Exactly the workaround I have been looking for haxe dictionary replacement!

Trackbacks/Pingbacks

Get Adobe Flash player