search

rust-lang / hashbrown

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

Optimize Set is_disjoint #531

Closed ToMe25 closed 4 months ago

ToMe25 commented 4 months ago

By using the Intersection iterator in HashSet::is_Disjoint its performance can be significantly improved in some cases.
This is because intersection() always uses the shorter set as its iterator.

It would also be possible to replicate this "Iterate over the smaller set and check in the larger set" logic in the is_disjoint method.
However in my benchmarks the approach I chose is faster than that.

This change only causes a significant improvement when called on the larger of two disjoint sets.

My benchmark results:

Name Before After Diff (%)
disjoint_is_disjoint_large_small 1,147.43 535.25 -53,35 %
disjoint_is_disjoint_small_large 535.66 527.59 -1,51 %
subset_is_disjoint 9.90 10.44 5,45 %
superset_is_disjoint 9.80 10.43 6,43 %
Amanieu commented 4 months ago

@bors r+

bors commented 4 months ago

:pushpin: Commit fc448cf3f4f0927078f74974bac75bca0e874946 has been approved by Amanieu

It is now in the queue for this repository.

bors commented 4 months ago

:hourglass: Testing commit fc448cf3f4f0927078f74974bac75bca0e874946 with merge 62dd52194e4148ca91aab1a0687904719e51508c...

bors commented 4 months ago

:broken_heart: Test failed - checks-actions

ToMe25 commented 4 months ago

That error seems to be a Dead Code error which I'm pretty sure this PR couldn't have caused, is there anything I can/should do about this?

Amanieu commented 4 months ago

Just add #[cfg(feature = "raw")] to these types. The CI failure is probably due to lint changes in nightly rustc.

ToMe25 commented 4 months ago

Ok, I'll do that tomorrow.

ToMe25 commented 4 months ago

Hooray that actually fixed CI.

Amanieu commented 4 months ago

@bors r+

bors commented 4 months ago

:pushpin: Commit 4b6e11d3a5753521b2f6543a25da1366ac8809b6 has been approved by Amanieu

It is now in the queue for this repository.

bors commented 4 months ago

:hourglass: Testing commit 4b6e11d3a5753521b2f6543a25da1366ac8809b6 with merge e25e6bb02e4fe4d58835f525d60f86091f41d50f...

bors commented 4 months ago

:sunny: Test successful - checks-actions Approved by: Amanieu Pushing e25e6bb02e4fe4d58835f525d60f86091f41d50f to master...