STD HashMap is slower than other languages HashMap

help
1

Hello, I just read about Swiss Table map is used by Rust, Golang and Zig. While C++ uses linked list. So I am curious about the performance of all of them, then I benchmarked them

The full benchmark code can be found here GitHub - fuji-184/HashMap-Benchmark · GitHub

The benchmark uses Assembly X86 RDTSCP instruction to make all languages use the same timer not STD time

Edit : Previously I used RDTSC. I just found it does not wait all previous instructions are done, but it runs out of order, good for speed but not good for timing execution speed like benchmark, because there will operarions that are not counted. I changed to the version that waits all previous instructions finish, aka RDTSXP. I also updated the result below and code in the github

To reproduce the benchmark :

  1. Clone the repo
  2. chmod +x ./run.sh
  3. ./run.sh

The bash script is abstraction to compile all in release mode then run all of them

You can also compile and run by your own if you find any better compile flags

The result is supprising. Because the STD HashMap is slower

Here is the result for 1000000 items

=== 1. COMPILING ===
[+] Compiling C++ with Clang...
[+] Compiling C++ Abseil Swiss Table with Clang...
[+] Compiling Rust...
[+] Compiling Rust Rustc_Hash library...
[+] Compiling Rust Ahash library...                      
[+] Compiling Rust Hashbrown library...
[+] Compiling Zig...
[+] Compiling Go...

=== 2. RUNNING BENCHMARKS ===

-----------------------------------
C++ (std::unordered_map via Clang)
-----------------------------------
N: 1,000,000
Get: 499,999,500,000
Insert: 346,769,016 cycles
Get Hit: 16,441,728 cycles
Get Miss: 18,854,272 cycles
Update: 17,794,388 cycles
Delete: 91,483,570 cycles
-----------------------------------
C++ (absl::flat_hash_map via Clang)
-----------------------------------
N: 1,000,000
Get: 499,999,500,000
Insert: 617,524,586 cycles
Get Hit: 180,881,470 cycles
Get Miss: 46,403,484 cycles
Update: 391,016,774 cycles
Delete: 388,502,294 cycles

-----------------------------------
Rust (std::collections::HashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 508.799.908 cycles
Get Hit: 480.473.190 cycles
Get Miss: 93.977.088 cycles
Update: 628.344.672 cycles
Delete: 745.041.942 cycles

-----------------------------------
Rust (rustc_hash::FxHashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 401.385.032 cycles
Get Hit: 129.132.822 cycles
Get Miss: 14.771.436 cycles
Update: 376.373.640 cycles
Delete: 397.623.422 cycles

-----------------------------------
Rust (ahash::AHashMap)
-----------------------------------
N: 1000000                                            Get: 499999500000
Insert: 416.307.314 cycles
Get Hit: 102.810.244 cycles
Get Miss: 36.378.782 cycles
Update: 358.037.282 cycles
Delete: 358.654.686 cycles

-----------------------------------
Rust (hashbrown::HashMap;)                            -----------------------------------
N: 1000000
Get: 499999500000
Insert: 406.681.224 cycles
Get Hit: 125.862.512 cycles
Get Miss: 27.706.644 cycles
Update: 354.708.998 cycles
Delete: 299.873.148 cycles

-----------------------------------
Zig (std::AutoHashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 449.253.678 cycles
Get Hit: 195.605.874 cycles
Get Miss: 76.549.814 cycles
Update: 282.018.606 cycles
Delete: 167.909.892 cycles

-----------------------------------
Go (map[int]int)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 1.348.740.788 cycles
Get Hit: 366.265.524 cycles
Get Miss: 459.286.064 cycles
Update: 416.440.874 cycles
Delete: 431.979.628 cycles

=== Done ===

Anyone know why?

Also if there is error in my benchmark code, please don't hestitate to correct it

If the benchmark is valid, we may need to find why and how to improve the performance

2

I believe reading somewhere that other languages use faster hashing algorithms by default. Maybe try using a different hashing algorithm for HashMap? Hashing - The Rust Performance Book

3

I think that is 3rd library, not STD library

4

Yes, third party libraries like ahash provide faster hashing algorithms than the default hasher from std for std::collections::HashMap.

5

Because C++'s std::unordered_map has a static anti-hash-test and Rust's does not; if you could factor out the hashing from the benchmark, though?

6

There is also the HashBrown crate that provides a faster implementation. It would be nice to add its benchmark as well.

7

I just added rustc_hash and ahash. The code is also updated in the github

Here is the result

=== 1. COMPILING ===
[+] Compiling C++ with Clang...
[+] Compiling C++ Abseil Swiss Table with Clang...
[+] Compiling Rust...
[+] Compiling Rust Rustc_Hash library...
[+] Compiling Rust Ahash library...                      
[+] Compiling Rust Hashbrown library...
[+] Compiling Zig...
[+] Compiling Go...

=== 2. RUNNING BENCHMARKS ===

-----------------------------------
C++ (std::unordered_map via Clang)
-----------------------------------
N: 1,000,000
Get: 499,999,500,000
Insert: 273,606,154 cycles
Get Hit: 15,344,796 cycles
Get Miss: 16,510,684 cycles
Update: 15,180,844 cycles
Delete: 62,615,288 cycles
-----------------------------------
C++ (absl::flat_hash_map via Clang)
-----------------------------------
N: 1,000,000
Get: 499,999,500,000
Insert: 674,338,004 cycles
Get Hit: 273,807,458 cycles
Get Miss: 57,701,012 cycles
Update: 368,076,318 cycles
Delete: 354,000,140 cycles

-----------------------------------
Rust (std::collections::HashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 450.880.338 cycles
Get Hit: 492.068.886 cycles
Get Miss: 189.771.198 cycles
Update: 580.598.652 cycles
Delete: 424.567.084 cycles

-----------------------------------
Rust (rustc_hash::FxHashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 357.438.252 cycles
Get Hit: 80.029.694 cycles
Get Miss: 11.356.880 cycles
Update: 484.255.892 cycles
Delete: 491.284.688 cycles

-----------------------------------
Rust (ahash::AHashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 386.020.656 cycles
Get Hit: 126.232.144 cycles
Get Miss: 31.714.976 cycles
Update: 331.611.794 cycles
Delete: 464.551.884 cycles

-----------------------------------
Rust (hashbrown::HashMap;)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 395.102.554 cycles
Get Hit: 102.983.944 cycles
Get Miss: 29.085.134 cycles
Update: 321.366.318 cycles
Delete: 281.449.274 cycles

-----------------------------------
Zig (std::AutoHashMap)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 9.956.064.903.291.714 cycles
Get Hit: 9.956.061.831.106.652 cycles
Get Miss: 18.446.744.071.686.191.830 cycles
Update: 18.446.744.073.708.233.538 cycles             Delete: 16.722.463.649.779.212.845 cycles

-----------------------------------
Go (map[int]int)
-----------------------------------
N: 1000000
Get: 499999500000
Insert: 1.276.340.958 cycles                          Get Hit: 292.602.744 cycles
Get Miss: 316.676.624 cycles
Update: 316.226.082 cycles
Delete: 446.475.884 cycles

=== Done ===

The 3rd libs are not equally secure

Does other languages HashMap also uses DOS protection algorithm?

Because if yes it can be interesting how can they be faster while using DOS protection algorithm?

Edit : I made mistake because I forgot to change the path to run the binary for Ahash. It is fixed and I also added Hashbrown

8

std's hash map uses hashbrown's underneath, only with a different hasher. OP tested std's hash map with ahash, which should give the same results as using hashbrown::HashMap with default configuration.

9

What is anti hash test?

I just added Rustc_Hash, Ahash, and Hashbrown. They are still slower

10

I just added Hashbrown, yeah it is still slower. I also fixed miss path for Ahash. The result is updated in the comment above, the code is also update in the github

11

I think he/she is refering to the default hashing algorithm. IIRC, C++ uses the identity function for its std::hash<int>, i.e. hash(i) == (size_t) i. so your test literally insert into the hash bucket in a linear fashion, just like pushing into a vector.

rust's default hashing algorithm is SIP hash.

12

If one is just hashing a bunch of ints, why not try the No Hash Hasher which forgoes hashing altogether and may provide better performance.

13

If I change the int to String, will it correct that?

14

All the input is same for all languages

It is to see the performance different of them. Not to remove the hash operation

15

A second important component of a hashmap is how fast it inserts a value into a known bucket, which could be measured with the most trivial hashing. I'd be curious to see results of that benchmark.

16

That is new for me :[ Do you mean about implementing BuildHasher and Hasher manually to make it not calculating hash?

17

That's what the suggested nohash-hasher does.

18

What a day to be a Zig enthusiast. Poor guys must have had no idea their AutoHashMap needs, quite literally, quadrillions[1] of CPU cycles just to insert or retrieve an int. Even worse than that, on any miss or update or remove, that blows up all the way to eighteen quintillion[2]. A quarter of a century just to figure out if your number is in the map or not?[3] Now that's some dedication.

Seriously though, you might want to review your handle-rolled asm for Zig there.

No need to do them folks so dirty, out of the blue.

That would be the bare minimum here, given the way the std::unordered_map of C++ "cheats" around your (already synthetic / in no way representative of any real world use case) bench.

  1. Insert: 9.956.064.903.291.714 cycles ↩︎

  2. Update: 18.446.744.073.708.233.538 cycles ↩︎

  3. On my CPU of 2.3 GHz: 18.446.744.073.708.233.538 / (2.3e9 x 60 x 60 x 24 x 365) = 254.322 years ↩︎

19

If you're benchmarking a hashtable you shouldn't test inserting sequential integers. That will just let the "dumber" hashtables win, while they will likely perform badly in practice. At the very least you should benchmark with (pseudo-)random keys. Also, try using i << 32 as the key and let's see if std::unordered_map is still fast.

20

there's two aspects of a hash table: the hash part and the table part.

it's ok to measure the end-to-end performance, as long as you understand what you are actually measuring.

if you just want to compare the table implementation (rust uses SwissTable, as you mentioned in OP), you need to factor out the difference in the hashing algorithms, or you must use the same hasher for all.

if you only want to compare the hashing algorithm, you don't need the table at all.

if you measure the hash table as a whole, a direct comparison is rarely useful, not even very meaningful comparison abou the default strategy of the standard librariy authors. they suit very different workloads and access patterns.

when you compare two very specific things, like "C++'s std::unordered_map<int, int> with std::hash<int> is XX% faster than rust's std::HashMap with std::DefaultHasher when using small consecutive integer keys and accessed in ascending sorted order", I don't find it very informative.