starred/terminal
1
0
Fork 0
mirror of https://github.com/microsoft/terminal.git synced 2026-02-03 21:25:34 +00:00
Code Issues 19.0k Packages Projects Releases 20 Wiki Activity

Boost hashing performance with Robin Hood #14942

New Issue
Closed
opened 2026-01-31 04:23:53 +00:00 by claunia · 2 comments
claunia commented 2026-01-31 04:23:53 +00:00
Owner
Copy Link

Originally created by @WSLUser on GitHub (Aug 23, 2021).

Originally assigned to: @lhecker on GitHub.

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 https://github.com/microsoft/terminal/pull/10521#issuecomment-873255814. Also see https://github.com/microsoft/terminal/pull/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.

Originally created by @WSLUser on GitHub (Aug 23, 2021). Originally assigned to: @lhecker on GitHub. <!-- 🚨🚨🚨🚨🚨🚨🚨🚨🚨🚨 I ACKNOWLEDGE THE FOLLOWING BEFORE PROCEEDING: 1. If I delete this entire template and go my own path, the core team may close my issue without further explanation or engagement. 2. If I list multiple bugs/concerns in this one issue, the core team may close my issue without further explanation or engagement. 3. If I write an issue that has many duplicates, the core team may close my issue without further explanation or engagement (and without necessarily spending time to find the exact duplicate ID number). 4. If I leave the title incomplete when filing the issue, the core team may close my issue without further explanation or engagement. 5. If I file something completely blank in the body, the core team may close my issue without further explanation or engagement. All good? Then proceed! --> # 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 https://github.com/microsoft/terminal/pull/10521#issuecomment-873255814. Also see https://github.com/microsoft/terminal/pull/10341 which addressed a bug with hashing that likely will need to be refactored slightly when adopting this library. <!-- A clear and concise description of what the problem is that the new feature would solve. Describe why and how a user would use this new functionality (if applicable). --> # Proposed technical implementation details (optional) Replace use of `std::unordered_map` and/or `std::unordered_set` with Robin Hood equivalent among other changes. <!-- A clear and concise description of what you want to happen. -->
claunia added the Issue-TaskNeeds-Tag-FixProduct-TerminalArea-Performance labels 2026-01-31 04:23:53 +00:00
claunia commented 2026-01-31 04:23:54 +00:00
Author
Owner
Copy Link

@lhecker commented on GitHub (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.

@lhecker commented on GitHub (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.
claunia commented 2026-01-31 04:23:54 +00:00
Author
Owner
Copy Link

@lhecker commented on GitHub (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 commented on GitHub (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.
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
⛺ Reserved
A11yCO
A11yMAS
A11ySev1
A11ySev2
A11ySev3
A11yTTValidated
A11yUsable
A11yVoiceAccess
A11yWCAG
Area-Accessibility
Area-AtlasEngine
Area-AzureShell
Area-Build
Area-Build
Area-Chat
Area-CmdPal
Area-CodeHealth
Area-Commandline
Area-CookedRead
Area-DefApp
Area-Extensibility
Area-Fonts
Area-GroupPolicy
Area-i18n
Area-Input
Area-Interaction
Area-Interop
Area-Localization
Area-Output
Area-Performance
Area-Portable
Area-Quality
Area-Remoting
Area-Rendering
Area-Schema
Area-Server
Area-Settings
Area-SettingsUI
Area-ShellExtension
Area-ShellExtension
Area-ShellExtension
Area-Suggestions
Area-Suggestions
Area-TerminalConnection
Area-TerminalControl
Area-Theming
Area-UserInterface
Area-VT
Area-Windowing
Area-WPFControl
AutoMerge
Blocking-Ingestion
Culprit-Centennial
Culprit-WinUI
Disability-All
Disability-Blind
Disability-LowVision
Disability-Mobility
External-Blocked-WinUI3
Fixed
Gathering-Data
good first issue
HCL-E+D
HCL-WindowsTerminal
Help Wanted
Impact-Compatibility
Impact-Compliance
Impact-Correctness
Impact-Visual
In-PR
InclusionBacklog
InclusionBacklog-Windows TerminalWin32
InclusionCommitted-202206
Issue-Bug
Issue-Docs
Issue-Feature
Issue-Feature
Issue-Question
Issue-Samples
Issue-Scenario
Issue-Task
Needs-Attention
Needs-Author-Feedback
Needs-Bisect
Needs-Discussion
Needs-Repro
Needs-Tag-Fix
Needs-Tag-Fix
Needs-Triage
No-Recent-Activity
Priority-0
Priority-1
Priority-2
Priority-3
Product-Cmd.exe
Product-Colortool
Product-Colortool
Product-Colortool
Product-Conhost
Product-Conpty
Product-Meta
Product-Powershell
Product-Terminal
Product-WSL
pull-request
Mirrored from GitHub Pull Request
 Resolution-Answered
Resolution-By-Design
Resolution-Duplicate
Resolution-External
Resolution-Fix-Available
Resolution-Fix-Committed
Resolution-No-Repro
Resolution-Won't-Fix
Severity-Blocking
Severity-Crash
Severity-DataLoss
spam
this-will-be-a-breaking-change
Tracking-External
WindowsTerminal_Win32
Work-Item
zAskModeBug
zInbox-Bug
No Label Area-Performance Issue-Task Needs-Tag-Fix Product-Terminal
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
claunia
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: starred/terminal#14942
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?