Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Boost hashing performance with Robin Hood #11016

Closed
WSLUser opened this issue Aug 23, 2021 · 2 comments
Closed

Boost hashing performance with Robin Hood #11016

WSLUser opened this issue Aug 23, 2021 · 2 comments
Assignees
Labels
Area-Performance Performance-related issue Issue-Task It's a feature request, but it doesn't really need a major design. Needs-Tag-Fix Doesn't match tag requirements Product-Terminal The new Windows Terminal.
Milestone

Comments

@WSLUser
Copy link
Contributor

WSLUser commented Aug 23, 2021

Description of the new feature/enhancement

Use MIT-licensed https://github.com/martinus/robin-hood-hashing to improve performance and increase memory efficiency. It does come with a custom allocator but it won't win any medals and can be ignored. Instead mimalloc should be compiled in instead and is even recommended by maintainer to use a dedicated allocator instead. This is filed under another issue. Idea for adding this stems from #10521 (comment). Also see #10341 which addressed a bug with hashing that likely will need to be refactored slightly when adopting this library.

Proposed technical implementation details (optional)

Replace use of std::unordered_map and/or std::unordered_set with Robin Hood equivalent among other changes.

@WSLUser WSLUser added the Issue-Feature Complex enough to require an in depth planning process and actual budgeted, scheduled work. label Aug 23, 2021
@ghost ghost added Needs-Triage It's a new issue that the core contributor team needs to triage at the next triage meeting Needs-Tag-Fix Doesn't match tag requirements labels Aug 23, 2021
@lhecker
Copy link
Member

lhecker commented Aug 23, 2021

I already have a branch for this: https://github.com/microsoft/terminal/tree/dev/lhecker%2Frobin-hood-hashing
It results in a rather significant binary size increase and doesn't make any noticeable performance differences. It does however improve memory usage significantly under certain conditions.

I'm expecting to introduce that project in a later PR for a purpose were it has a true impact.

@zadjii-msft zadjii-msft added Area-Performance Performance-related issue Issue-Task It's a feature request, but it doesn't really need a major design. Product-Terminal The new Windows Terminal. and removed Issue-Feature Complex enough to require an in depth planning process and actual budgeted, scheduled work. labels Aug 24, 2021
@ghost ghost removed the Needs-Tag-Fix Doesn't match tag requirements label Aug 24, 2021
@DHowett DHowett removed the Needs-Triage It's a new issue that the core contributor team needs to triage at the next triage meeting label Aug 27, 2021
@lhecker
Copy link
Member

lhecker commented Aug 10, 2022

I ended up writing my own purpose built hashmap and won't need martinus/robin-hood-hashing anymore. In other areas of this application hashmaps aren't used much.

@lhecker lhecker closed this as completed Aug 10, 2022
@ghost ghost added the Needs-Tag-Fix Doesn't match tag requirements label Aug 10, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Area-Performance Performance-related issue Issue-Task It's a feature request, but it doesn't really need a major design. Needs-Tag-Fix Doesn't match tag requirements Product-Terminal The new Windows Terminal.
Projects
None yet
Development

No branches or pull requests

4 participants