search

JesperAxelsson / rust-intmap

Specialized hashmap for u64 keys
MIT License
30 stars 10 forks source link

add ahashmap and a no-op hash variant to benchmarks #47

Closed coderedart closed 1 month ago

coderedart commented 2 months ago

I wanted to add ahash and no-op hashes to check how they perform relatively. I know no-op is not exactly a hash, but there are common cases where the keys are already random. The best example is probably std::any::TypeId which is used in bevy and many other libraries like egui or flecs-rs.

I also added HashBrownMap as it seems to be popular and serves as an alternative to std. It uses ahash by default at this moment.

The README shows name time
get_built_in 22,320 ns/iter (+/- 446)
get_intmap 2,959 ns/iter (+/- 148)
insert_built_in 27,666 ns/iter (+/- 1,230)
insert_intmap 14,047 ns/iter (+/- 1,461)
But when I ran the benchmarks on my PC with cargo +nightly bench I got the following results name time
get_ahash 31,663.90 ns/iter (+/- 30.20)
get_brown 35,274.26 ns/iter (+/- 35.20)
get_built_in 135,327.27 ns/iter (+/- 977.37)
get_indexmap 158,904.48 ns/iter (+/- 696.72)
get_intmap 41,835.94 ns/iter (+/- 64.88)
get_no_op 20,464.68 ns/iter (+/- 31.09)
insert_ahash 78,251.27 ns/iter (+/- 896.50)
insert_ahash_without_capacity 246,609.52 ns/iter (+/- 833.62)
insert_brown 67,379.19 ns/iter (+/- 167.35)
insert_brown_without_capacity 208,466.40 ns/iter (+/- 796.46)
insert_built_in 189,085.58 ns/iter (+/- 4,039.36)
insert_built_in_without_capacity 466,260.85 ns/iter (+/- 982.45)
insert_intmap 74,454.27 ns/iter (+/- 2,788.48)
insert_intmap_without_capacity 844,878.60 ns/iter (+/- 13,812.12)
insert_no_op 65,322.24 ns/iter (+/- 894.27)
insert_no_op_without_capacity 193,376.62 ns/iter (+/- 688.68)

I don't know if I am doing something wrong, or maybe stdlib got better over time, but the README's measurements definitely don't reflect the current status.

It would nice if you could run the benchmarks yourself and update the README. It will help users take a more informed decision on whether intmap would be suitable for their usecase or not.

JesperAxelsson commented 1 month ago

I think I used an old intel CPU on windows for old benchmarks, the numbers are 7 years old at this point :) So if you used a newer CPU or another OS the numbers can differ a lot. Rust also changed the implementation of the standard hashmap to hashbrown variant if I remember correctly. I have been thinking of removing them altogether as performance will vary a lot between architectures and OSs. Always benchmark on your intended hardware with representative data if performance is important.

JesperAxelsson commented 1 month ago

Seems adding ahash and hashbrown bumps minimum rustc version. I don't see a reason to do this just for benchmarks as there might be users who are still on an older rustc version. Instead I will add a benchmark branch and merge your changes there.