Skip to content

Replace internal hashtable with hashbrown RawTable#287

Merged
xacrimon merged 1 commit into
xacrimon:masterfrom
arthurprs:small-optimizations
Jun 17, 2024
Merged

Replace internal hashtable with hashbrown RawTable#287
xacrimon merged 1 commit into
xacrimon:masterfrom
arthurprs:small-optimizations

Conversation

@arthurprs

@arthurprs arthurprs commented Oct 23, 2023

Copy link
Copy Markdown
Contributor

Replace internal hashtable with hashbrown RawTable.

Benefits

  • Allows only hashing keys once
  • Allows a more efficient implementation of the Entry api. Which will always be a single hashtable operation.
    • Previously, building the entry would lookup the hashtable once, and other operations would do another lookup (e.g. OccupiedEntry::remove or VacantEntry::insert).
  • Allows dashmap raw api to be safely exposed even with the improvements above, as the shards are raw tables w/o hashers. This will avoid problems like Only hash keys once #259. crates.io use case (iterate the removed shards) will still be possible with rawtables.
  • Removes a lot of generic types for the hasher
  • Slightly simplifies some code paths as we don't have to fight lifetimes

The first two can be significant performance improvements in some circumstances.

Sadly, this is a breaking change for raw-api users so it'll require a major version bump.

Maybe the third time is the charm 😄

@arthurprs
arthurprs marked this pull request as draft October 23, 2023 22:44
@arthurprs
arthurprs force-pushed the small-optimizations branch from 096023f to b8ccad8 Compare October 24, 2023 08:42
@arthurprs
arthurprs force-pushed the small-optimizations branch from b8ccad8 to 0f95f59 Compare October 24, 2023 08:55
@arthurprs
arthurprs marked this pull request as ready for review October 24, 2023 09:47
@conradludgate

Copy link
Copy Markdown
Contributor

A potentially nicer setup could be to use the new HashTable API instead of RawTable. I put together a WIP of that in this commit conradludgate@3023a51.

@arthurprs

arthurprs commented Jun 10, 2024

Copy link
Copy Markdown
Contributor Author

The downside with Hashtable is still has all the lifetimes and that doesn't play well with dashmap lock wrappers. Meaning we keep having to transmute lifetimes at every corner with change_lifetime_const, etc..

@conradludgate

Copy link
Copy Markdown
Contributor

And now hashbrown 0.15 only offers HashTable and no RawTable API :D

@arthurprs

Copy link
Copy Markdown
Contributor Author

If I'm being honest, that came across as a pedantic act from the maintainers. They could have tried to reduce the more problematic surface areas, if there were really any. Now, some crates like this are back to having to fork or use large amounts of lifetime transmutes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants