Small linear factor remaining
- Dominant language
- Rust
- Stars
- 198
- Forks
- 7
- PR merge metrics
- No merged PRs in 30d
Description
Even though griddle spreads out _most_ of the cost of the resize, there is still a non-trivial additional cost at the time of the resize that appears to be proportional to the size of the map. That's unfortunate, and we should try to fix it.
I _believe_ this is due to the code here:
https://github.com/jonhoo/griddle/blob/b2a063c9efb82907447d92dad88015314379402c/src/lib.rs#L775-L782
Specifically, the _first_ time we try to carry elements from the old map to the new, we need to find the first non-empty bucket, which may actually take a while as the map grows. I wonder if `hashmap` could somehow keep track of the index of the first non-empty bucket?
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in src/lib.rs at lines 775-782 and trace how the first element is carried from the old map to the new one during resize. Measure the resize cost as the map grows, then determine whether tracking the first non-empty bucket removes the remaining linear work; done means resize migration no longer incurs that proportional scan.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100