hashbrown: `foldhash::fast::RandomState` is very bad

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=8d9004344a0ddd7799b90e24f5866e75

This counts collisions. The number fluctuates wildly from 1.5% to 7% and mostly depends on global seed (if one measurement is bad then all of them are). Both foldhash::quality::RandomState and ahash::RandomState remain at around 2.9% and would be acceptable as default.

About this issue

  • Original URL
  • State: open
  • Created 2 years ago
  • Comments: 15 (1 by maintainers)

Most upvoted comments

@arthurprs I’m working on analyzing it, at this point I don’t have a concrete answer yet. I’ve collected 1GB worth of seeds along with a performance score on the average number of equality checks performed when inserting the numbers 0..1<<16 into an hashbrown set, and I’m trying to establish a concrete pattern for what determines whether a seed is good or not, and why. Then I can hopefully update the seed selection to only generate good seeds.

Foldhash-q is rock-solid regardless of seed, so if you want to be 100% certain performance is predictable, it’s a good choice, especially in the meantime.

I’m seeing a massive decrease in performance when upgrading hashbrown from 0.14 to 0.15 and I think the issue describe here may be the problem.

My application went from well over 60fps to below 10fps after the update. I only realized hashbrown was the cause after attaching a profiler and seeing an outsized impact in the flame graph.

Flame graph when using hashbrown v1.14: Image

Flame graph when using hashbrown v1.15: Image

With v1.14 hashbrowns functions aren’t significant enough to be noticed in the graph, but with v1.15 they dominate most of the cpu time.