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 100 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: 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 ===

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

12 posts - 6 participants

Read full topic