schnellru

schnellru is a fast and flexible Least Recently Used (LRU) map implementation in Rust. It is designed to be high-performance, offering up to twice the speed of the lru crate with lower memory overhead.

Key features include:

• Ordered Map Capabilities: Can be used as an ordered map with performance comparable to indexmap, but with the advantage of $O(1)$ non-perturbing removals (removing an element without changing the relative order of other elements).
• Customizable Eviction: Supports custom limiters to control map size based on criteria other than just length or memory usage.
• Environment Support: Supports no_std environments.
• Reliability: Tested with Miri, Clippy, and fuzzing.

To run the fuzz tests provided in the fuzz package, you must first install honggfuzz on your system using cargo.

cargo install -f honggfuzz

The Limiter trait is the core mechanism for controlling the capacity of an LruMap. It allows you to define custom eviction logic based on various metrics (e.g., number of items, total memory usage, or custom costs).

Key methods include:

• is_over_the_limit(&self, length: usize) -> bool: Checks if the current map state violates the limit.
• on_insert(&mut self, ...) -> Option<(K, V)>: Called during insertion. Returning None prevents the insertion.
• on_replace(&mut self, ...) -> bool: Called when an existing key's value is updated. Returning false prevents the update.
• on_removed(&mut self, ...): Called when an item is evicted or manually removed.
• on_cleared(&mut self): Called when the map is cleared.
• on_grow(&mut self, ...) -> bool: Called when the map attempts to rehash/grow. Returning false prevents growth.

You can create an LruMap that automatically limits its total memory usage using the ByMemoryUsage limiter. This is useful when you want to ensure the cache does not exceed a specific byte threshold.

Use with_memory_budget(memory_budget) to create a map with a randomized hasher, or with_memory_budget_and_hasher(memory_budget, hasher) to provide a specific hasher.

// Using the default RandomState hasher
let mut map = LruMap::with_memory_budget(1024 * 1024); // 1MB budget

The drain() method returns a Drain iterator that removes all elements from the map in Most Recently Used (MRU) order. When the Drain iterator is dropped, the map is automatically cleared.

let mut lru = LruMap::new(UnlimitedCompact);
// ... populate lru ...

for (key, value) in lru.drain() {
    // Elements are removed from the map as you iterate
}
// After drain is dropped, lru is empty

You can access the Limiter associated with an LruMap via limiter() (for an immutable reference) or limiter_mut() (for a mutable reference). This is useful for inspecting the current cost or state of the capacity constraints.

let lru = LruMap::new(ByLength::new(10));
let limiter = lru.limiter();
// Use limiter methods...

If you need to access a value without updating its position in the LRU order, use peek.

• peek(&key) returns an Option<&V>.
• peek_mut(&key) returns an Option<RefMut<V>>, allowing you to modify the value in place without affecting its recency.

Note that standard get(&key) calls do update the recency of the element.

// Peek at a value without updating recency
if let Some(value) = lru.peek(&key) {
    println!("Value: {}", value);
}

// Mutably peek at a value without updating recency
if let Some(mut value) = lru.peek_mut(&key) {
    *value = new_value;
}

To remove all elements from an LruMap:

• Use clear() to remove all entries in place.
• Use drain() to return an iterator that removes elements from the map as they are consumed. The drain() iterator follows the recency order (newest to oldest).

// Clear everything
lru.clear();

// Drain elements into a collection
let items: Vec<_> = lru.drain().collect();

To ensure deterministic behavior (e.g., for testing), you can create an LruMap with a specific seed for its hasher using with_seed.

let limiter = ByLength::new(100);
let seed = [1, 2, 3, 4];
let map = LruMap::with_seed(limiter, seed);

You can remove elements from the LruMap based on their recency. pop_oldest() removes and returns the least recently used element, while pop_newest() removes and returns the most recently used element. Both methods return an Option<(K, V)> and return None if the map is empty.

// Removing the oldest element
if let Some((key, value)) = lru.pop_oldest() {
    println!("Popped oldest: {:?} = {:?}", key, value);
}

// Removing the newest element
if let Some((key, value)) = lru.pop_newest() {
    println!("Popped newest: {:?} = {:?}", key, value);
}