Add `auto_shrink()` for papaya map/set reclamation
- Dominant language
- Rust
- Stars
- 244
- Forks
- 29
- Avg merge
- 2d 41m
- Merged PRs (30d)
- 19
Description
Related to #416, idea by @deven96
Papaya has growth policies in that govern how the maps perform allocation.
They dont shrink at all and thats often fine for short running operations, but for us probably not.
I can see a world where we can initialize a papaya hashmap with this:
```rust
Hashmap::builder()
.auto_shrink(AutoShrink::...);
```
And we also expose some manual methods that shrink to fit and probably shrink to specific lower bound.
The `AutoShrink` enum would control the policies of how reclamation happens. Some basic ones we can do would be:
```rust
enum AutoShrink {
Never, // current default so it's a no-op for existing papaya maps
Preset(ShrinkPreset),
Custom(AutoShrinkPolicy),
}
enum AutoShrinkPolicy {
threshold: f32, // Shrink when map is this % full
min_savings: f32, // only if the new cap is less than this % of old cap,
check_frequency: u32, // Check map with every Nth remove (0 means every remove)
min_capacity: u32, // Never shrink below this
}
// Enum of pre-configured autoshrink policies and a bulk only
enum ShrinkPreset {
Conservative, //25% threshold, 50% savings, 1/256 op check
Balanced, // 33% threshold, 33% savings, 1/128 op check
Aggressive, // 40% threshold, 25% savings, 1/64 op check,
Bulk, // only shrink after clear()/retain()
}
```
Basically every shrink policy has built in hysteresis prevention through the fact that we use asymmetric thresholds (min_savings),
All in all I think when we are considering how to save space (which we aren't atm), we would consider something like this.
Contributor guide
Research direction
Start by reading related issue #416 and the existing Papaya growth policies. The proposal names Hashmap::builder(), AutoShrink, AutoShrinkPolicy, ShrinkPreset, and manual shrink methods, but no implementation files or tests. Done would require an agreed API and defined reclamation behavior for the proposed policies.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100