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 integer lookups with a hit probability of 95%
Random integer lookups with a hit probability of 50%
Random integer lookups with a hit probability of 5%
Random integer lookups with a hit probability of 0%
lonewolfer 
Why not publish the full code, so we can see if your Lua implementation is creating unnecessary globals or deliberate upvalues?
Done
Reblogged this on Electronic Technician.
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
Updated
I do hope you used the JMH benchmarking harness for Java, otherwise your results have a high likelihood of being invalid.
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.
Tested Trove and Colt here: https://lonewolfer.wordpress.com/2014/03/17/benchmarking-hash-table-implementations-java/
If I have some time I’ll update this test with some more data at some point.