fliplru

flip LRU 是一个具有一些内置分析功能的 LRU 缓存，以帮助调整缓存容量。

此缓存数据结构的目标有两个

1. get API 应该快速且开销低，因为它是缓存的主要 API。
2. 公开一些分析指标，以帮助确定适当的容量。

还有一个目标，但与实现相关，我不想使用链表。

实现基于 2 个哈希表来提供 LRU 功能。因此，此缓存的总体容量是 2*cap LRU 项目。保证 cap LRU 项目将在缓存中。从 cap+1 到 2*cap 的 LRU 项目可能在缓存中，但这没有保证。

使用 hashbrown 映射和 2 个缓存设计一起提供快速的 get API。

公开一个翻转指标，以帮助调整缓存容量。翻转表示缓存容量达到的次数。它清空缓存并重新填充，以使性能不受影响（请参阅下面的基准测试）。如果翻转计数为 0，则缓存过大。如果翻转计数非常高，并且接近访问次数/容量，则缓存未得到有效利用，并且需要增加容量。

API 启发于 lru，由 Jerome Froelich 开发。


检查缓存容量是否太小，无法用于用例

以下是一个检查缓存的容量是否配置过小的示例。在这个例子中，缓存被访问了 20 次，对于容量为 2 的缓存，翻转计数为 8。这表明对于访问模式没有发生缓存。

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
for i in 0..5 {
    cache.put(i, i);
}
for i in 0..20 {
    cache.get(&(i % 5));
}

assert_eq!(cache.get_flips(), 8);

检查缓存容量是否过大，无法用于用例

以下是一个检查缓存是否配置了足够容量的示例。在这个示例中，缓存被访问了20次，对于容量为5的缓存，翻转次数为0。这表明缓存完全满足每次访问。

let mut cache = LruCache::new(NonZeroUsize::new(5).unwrap());
for i in 0..5 {
    cache.put(i, i);
}
for i in 0..20 {
    cache.get(&(i % 5));
}

assert_eq!(cache.get_flips(), 0);

状态

这是一个基本的LRU缓存，带有帮助调整缓存容量的指标。提供快速的get API。

基准测试

基准测试受到了Christian Mauduit的HashLRU的启发。

使用各种缓存实现配置的100000容量进行get API的基准测试比较。这在一个2020年的MacBook Air上运行。

running 8 tests
test tests::bench_read_usize_builtin_hashmap    ... bench:          16 ns/iter (+/- 0)
test tests::bench_read_usize_caches             ... bench:          37 ns/iter (+/- 16)
test tests::bench_read_usize_fastlru            ... bench:          48 ns/iter (+/- 7)
test tests::bench_read_usize_fliplru            ... bench:           7 ns/iter (+/- 0)
test tests::bench_read_usize_hashlru_cache      ... bench:          10 ns/iter (+/- 1)
test tests::bench_read_usize_hashlru_sync_cache ... bench:          15 ns/iter (+/- 0)
test tests::bench_read_usize_lru                ... bench:          10 ns/iter (+/- 0)
test tests::bench_read_usize_lru_cache          ... bench:          38 ns/iter (+/- 0)

test result: ok. 0 passed; 0 failed; 0 ignored; 8 measured; 0 filtered out; finished in 14.09s

要运行基准测试

cd bench
rustup default nightly
cargo bench