Benchmarking hash table implementations

A first iteration of benchmarks of different hash table implementations.

Candidates

Tested implementations

  • C++11 unordered_map – Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
  • C++ Google DenseHash – Google SparseHash v2.0.2
  • Java native HashMap – Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
  • C khash – Above clang environment with khash v0.2.8
  • Lua builtin – LuaJIT v2.0.3

Environment

A 2.6 GHz i7 Macbook Pro, 8 GB RAM, running Mac OS X 10.9.1.

Source

https://code.google.com/p/hash-table-benchmarks/

Random integer lookups with a hit probability of 100%

Random integers, p1

Random integer lookups with a hit probability of 95%

Random integers, p0.95

Random integer lookups with a hit probability of 50%

Random integers, p0.5

Random integer lookups with a hit probability of 5%

Random integers, p0.05

Random integer lookups with a hit probability of 0%

 Random integers, p0

Advertisements

8 thoughts on “Benchmarking hash table implementations”

  1. Why not publish the full code, so we can see if your Lua implementation is creating unnecessary globals or deliberate upvalues?

  2. What about avoiding a call to containsKey() + get() in the Java version, and just issue only one call to get() and check for null as you do in Lua.

    Something like : Integer x = m.get(b[i]); if (x != null) sum += x;
    instead of : if (m.containsKey(b[i])) sum += m.get(b[i]);

    My 2 cents

  3. I do hope you used the JMH benchmarking harness for Java, otherwise your results have a high likelihood of being invalid.

  4. I’d be interested in including the .net implementations, and a java collection library optimized for primitive types (like hppc) also, as it would show the overhead of the unnecessary boxing/unboxing of objects of the (imho fubar) java primitive types + generics support.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s