search

rust-lang / hashbrown

Rust port of Google's SwissTable hash map
https://rust-lang.github.io/hashbrown
Apache License 2.0
2.38k stars 275 forks source link

Introduce Swiss Cheese benchmark #507

Open matthieu-m opened 6 months ago

matthieu-m commented 6 months ago

The current design of RawTable leaves tombstones behind to indicate deleted elements, going from tightly packed elements to a much more sparse design as more and more elements are deleted -- until more elements are inserted again, at least.

This creates a "swiss cheese" situation, with a decreasing elements density over time. This situation is expected to lead to a higher number of cache misses as this density decreases.

The swiss_cheese.rs benchmark suite aims at measuring the impact of this effect on performance.

Amanieu commented 5 months ago

CI should be fixed now, can you rebase? I am curious to see what kind of results you are getting with this benchmark.

Amanieu commented 5 months ago

With that said, I don't think it makes sense to merge this benchmark. It is useful as an experiment, but it's less useful for measuring the actual performance of the table.

matthieu-m commented 5 months ago

I don't think it makes much sense either.

Making a PR was the easiest to share both code and result, but it may be a bit too specific.