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

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

Update

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!















Comments

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 %.
May 27, 2016 at 3:26 AM
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.
May 27, 2016 at 11:10 AM
Vasily said…
I rerun the benchmarks. D's become the winner at lookups.
May 27, 2016 at 10:42 PM
Vasily said…
Added Scala. It's very, very slow.
May 30, 2016 at 7:42 PM
Unknown said…
Scala/JVM's boxing and unboxing is very slow in such a tight loop.
Eclipse collections may be useful.

https://gist.github.com/zakki/66d785b4a9d3c64bc9f8199d7e290e07 13x faster
June 9, 2016 at 4:14 PM
miegir said…
The F# one is not really F#-specific, it is the translation of what can be done in C# and other .NET languages. I prefer to call it ".NET", not "F#".
July 25, 2017 at 2:25 PM
Vasily said…
I don't care about C# or Nemerle or whatever. I'm still on .net solely because of F#.
July 25, 2017 at 3:06 PM
Kulma said…
@miegir made a fair point. For idmiomatic F# you'd rather use a `Map`
February 4, 2018 at 8:37 PM
Vasily said…
@Kulma The post is called "Hash maps: Rust, F#, D, Go, Scala". F# Map is an AVL tree map, not a hash map. So, the choice of Dictionary in the F# code is fair.
February 4, 2018 at 8:56 PM
Post a Comment

Popular posts from this blog

Haskell: performance

It turned out that it's not Haskell who was slow in my previous Fibonacci test. It was my lack of Haskell knowledge. Haskell has two integral types - Int, which has bounds -2147483648..2147483647 and Integer, which is unbounded. Both types implement Integral type class, so out fib function can be defined in terms of this type class: OK, now we can test performance of the function parametrizing it with the two concrete types. Integer first: We get our previous result ~15 seconds which is rather slow. Now test it with Int type: Whoa! The Int type is ~6 times faster than Integer! And with result of 2.8 seconds Haskell's took the third position in our small rating :) Current list (in seconds): C# - 1.26 F# - 1.38 Nemerle - 1.45 Haskell - 2.8 Clojure - 9 Erlang - 17 Ruby - 60 Python - 120
Read more

Regular expressions: Rust vs F# vs Scala

Image
Let's implement the following task: read first 10M lines from a text file of the following format: then find all lines containing Microsoft namespace in them, and format the type names the usual way, like "Microsoft.Win32.IAssemblyEnum". First, F#: Now Rust: After several launches the file was cached by the OS and both implementations became non IO-bound. F# one took 29 seconds and 31MB of RAM at peak; Rust - 11 seconds and 18MB. The Rust code is as twice as long as F# one, but it's handling all possible errors explicitly - no surprises at runtime at all. The F# code may throw some exceptions (who knows what kind of them? Nobody). It's possible to wrap all calls to .NET framework with `Choice.attempt (fun _ -> ...)`, then define custom Error types for regex related code, for IO one and a top-level one, and the code'd be even longer then Rust's, hard to read and it would still give no guarantee that we catch all possible exceptions. Up
Read more

STM: F# vs Haskell

STM is a very nice parallel programming model used intensively in Haskell and Clojure. There's a F# implementation which can be found in FSharpx library. Today I'm going to test performance of both the Haskell and the F# STMs. The test is very simple - read a couple TVars, check their equality, then write them back incremented by 1, repeat a million times. First, the Haskell code: So, it took about 170 ms. OK, now F#: It took about 1,6 seconds which is an order of magnitude slower than the Haskell result. It's rather frustrating.
Read more