jonhoo / jonhoo/griddle

Small linear factor remaining

Open
#3 2 comments 0 reactions 0 assignees View on GitHub
enhancement help wanted question
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.