Sunday, May 22, 2016

Hash maps: Rust, F#, D, Go, Scala

Let's compare performance of hashmap implementation in Rust, .NET, D (LDC) and Go.
As you can see, Rust is slower at about 17% on insersions and at about 21% on lookups.


As @GolDDranks suggested on Twitter, since Rust 1.7 it's possible to use custom hashers in HashMap. Let's try it:
Yes, it's significantly faster: additions is only 5% slower than .NET implementation, and lookups are 32% *faster*! Great.

Update: D added

LDC x64 on windows
It's very slow at insertions and quite fast on lookups.

Update: Go added

Update: Scala added

Compared to Scala all the other languages looks equally fast :) What's worse, Scala loaded all four CPU cores at almost 100% during the test, while others used roughly single core. My guess is that JVM allocated so many objects (each Int is an object, BTW), that 3/4 of CPU time was spend for garbage collecting. However, I'm a Scala/JVM noob, so I just could write the whole benchmark in a wrong way. Scala developers, please review the code and explain why it's so slow (full IDEA/SBT project is here). Thanks!


Anonymous said...

The tests a re not the same. The equivalent of what you do in Go to D is

elapsed = stopTime!({
auto acc = 0;
foreach(i; 0 .. 50_000_000)
acc += m[i] % 10;
}) ;

Also in D you seem to repeat twice the operations because of the additional

auto _ = m[x];

Which is not done in the other languages. So finally I think that's it's unfair.
What you really should do in D is

elapsed = stopTime!({
auto acc = 0;
foreach(x; source) {
if (auto v = x in m)
acc += *v % 10;

And you'll see the lookup time reduced by 65 to 75 %.

Vasily said...

Thanks! I've fixed the D code as well as Go one (it does not use random numbers for filling the map), I will rerun both of them tonight.

Vasily said...

I rerun the benchmarks. D's become the winner at lookups.

Vasily said...

Added Scala. It's very, very slow.

Kensuke Matsuzaki said...

Scala/JVM's boxing and unboxing is very slow in such a tight loop.
Eclipse collections may be useful. 13x faster

andrea chiu said...

The strongest and fearless person is the one who knows his/her mistakes and still seek for guidance and forgiveness. Have a pleasant day and keep on smiling. Visit my site for more information.