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

Let's compare performance of hashmap implementation in Rust, .NET, D (LDC) and Go.
Rust:

	extern crate rand;
	extern crate time;
	#[macro_use]
	mod utils;
	use rand::*;
	use std::collections::{HashMap};
	fn main() {
	let mut m = HashMap::new();
	let mut rnd = rand::thread_rng();
	let source = (1..50_000_000).map(|_| rnd.gen::<i32>()).collect::<Vec<_>>();
	time!("Insertion", {
	for x in source.iter().cloned() {
	m.entry(x).or_insert(0);
	}
	});
	time!("Lookup", {
	let mut _acc = 0;
	for x in source.iter() {
	if let Some(x) = m.get(x) {
	_acc += x % 10
	}
	}
	})
	}
	// Insertion: PT9.190395246S elapsed.
	// Lookup: PT5.469118359S elapsed.

view raw hash_map.rs hosted with ❤ by GitHub

F#:

	open System.Collections.Generic
	open System.Diagnostics
	open System
	let rnd = Random()
	let source = Array.init 50000000 <| fun _ -> rnd.Next Int32.MaxValue
	let d = Dictionary<int, int>()
	time "Insertion" <| fun _ ->
	for x in source do
	d.[x] <- 0
	time "Lookup" <| fun _ ->
	let mutable _acc = 0
	for x in source do
	match d.TryGetValue x with
	| true, x -> _acc <- _acc + x % 10
	| _ -> ()
	// Insertion: 00:00:07.7138976 elapsed
	// Lookup: 00:00:04.3228718 elapsed

view raw dictionary.fs hosted with ❤ by GitHub

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:

	extern crate rand;
	extern crate time;
	extern crate fnv;
	#[macro_use]
	mod utils;
	use rand::*;
	use std::collections::{HashMap};
	use std::hash::BuildHasherDefault;
	use fnv::FnvHasher;
	type Hasher = BuildHasherDefault<FnvHasher>;
	fn main() {
	let mut m: HashMap<_, _, Hasher> = HashMap::default();
	let mut rnd = rand::thread_rng();
	let source = (1..50_000_000).map(|_| rnd.gen::<i32>()).collect::<Vec<_>>();
	time!("Insertion", {
	for x in source.iter().cloned() {
	m.entry(x).or_insert(0);
	}
	});
	time!("Lookup", {
	let mut _acc = 0;
	for x in source.iter() {
	if let Some(x) = m.get(x) {
	_acc += x % 10
	}
	}
	})
	}
	// Insertion: PT8.113402537S elapsed.
	// Lookup: PT3.419989949S elapsed.

view raw hash_map_custom_hasher.rs hosted with ❤ by GitHub

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

	module main;
	import std.random;
	import std.stdio;
	import std.datetime;
	template stopTime(alias f) {
	auto stopTime() {
	auto sw = StopWatch(AutoStart.yes);
	f();
	sw.stop();
	return sw.peek.msecs;
	}
	}
	int main() {
	int[] source;
	source.length = 50_000_000;
	foreach(ref x; source)
	x = uniform(0, int.max);
	int[int] m;
	auto elapsed = stopTime!({ foreach(x; source) m[x] = 0; });
	writefln("Insertion: %d msecs\n", elapsed);
	writefln("Map.length = %d", m.length);
	elapsed = stopTime!({
	auto acc = 0;
	foreach(x; source) {
	if (auto v = x in m)
	acc += *v % 10;
	}
	});
	writefln("Lookup: %d msecs\n", elapsed);
	readln();
	return 0;
	}
	// Insertion: 13523 msecs
	// Lookup: 3151 msecs

view raw assoc_array.d hosted with ❤ by GitHub

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

Update: Go added

	package main
	import (
	"fmt"
	"time"
	"math/rand"
	)
	func timeTrack(start time.Time, name string) {
	elapsed := time.Since(start)
	fmt.Printf("%s took %s", name, elapsed)
	}
	func main() {
	var source [50000000]int
	for i := 0; i < len(source); i++ {
	source[i] = rand.Int()
	}
	m := make(map[int]int)
	start := time.Now()
	for x := range source {
	m[x] = 0
	}
	fmt.Printf("Insertion: %s", time.Since(start))
	start = time.Now()
	acc := 0
	for x := range source {
	acc += m[x] % 10
	}
	fmt.Printf("Lookups: %s", time.Since(start))
	}
	// Insertion: 11.69s
	// Lookups: 5.16s

view raw hash_map.go hosted with ❤ by GitHub

Update: Scala added

	import scala.collection._
	import scala.util.Random
	object Utils {
	def time[A](name: String) (f: => Unit) = {
	val s = System.nanoTime
	f
	println(s"$name: ${((System.nanoTime - s) / 1e6).toLong} elapsed.")
	}
	}
	object Main {
	def main(args: Array[String]): Unit = {
	val source = Seq.fill(50000000){Random.nextInt()}.toArray
	val m = mutable.HashMap.empty[Int, Int]
	Utils.time("Insertion") {
	for (x <- source) {
	m.put(x, 0)
	}
	}
	Utils.time("Lookups") {
	var acc = 0
	for (x <- source)
	acc += m(x) % 10
	acc
	}
	}
	}
	// Insertion: 32627 elapsed.
	// Lookups: 14824 elapsed.

view raw scala_hash_map_test.scala hosted with ❤ by GitHub

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!