deven96 / deven96/ahnlich

Add `auto_shrink()` for papaya map/set reclamation

Open
#418 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.