Skip to content

nitnelave/lru_cache

Repository files navigation

LRU cache

A fast, header-only, generic C++ 17 LRU cache library, with customizable backend.

Example usage

Cache calls to an expensive function

#include "lru_cache/lru_cache.h"

int very_expensive_function(int key) {
  // Do a network call to get the result.
  return 42;
}

int main() {
  // Keep up to 100 calls. The type of the cache is deduced from the function.
  auto memoized = lru_cache::memoize_function(100, very_expensive_function);
  for (int i = 0; i < 1000; ++i) {
    // Automatically calls very_expensive_function if the key is not in the
    // cache.
    int result = memoized(i);
    do_something_with(result);
  }
}

Memoize a recursive function

#include "lru_cache/lru_cache.h"

template <typename Cache>
size_t cached_fibo(int n, Cache& cache) {
  if (n < 2) return 1;
  // Get the element, or null. This updates the most recent access list.
  const size_t* maybe = cache.get_or_null(n);
  if (maybe) return *maybe;
  size_t result = cached_fibo(n - 1, cache) + cached_fibo(n - 2, cache);
  // Insert into the cache.
  cache.insert(n, result);
  return result;
}

int main() {
  // Cache 10 elements.
  auto cache = lru_cache::make_cache<int, size_t>(10);
  // Quick computation.
  size_t result = cached_fibo(60, cache);
}

Configurable backends

There are 3 configurations available out of the box:

  • DynamicLruCache, consisting of an std::unordered_map of key to index, and a std::vector to hold the values and the linked list of last accesses.
  • StaticLruCache, similar except that the vector is replaced by a std::array-like structure, allowing you to prevent reallocation, and hold the memory for the values on the stack if you want.
  • NodeLruCache, the default, consisting of an absl::node_hash_set containing the key, the value and the linked list in the nodes.

The last one is the main innovation of this repository, and the fastest implementation.

However, the backends are quite flexible, and it's relatively easy to switch a map for another, or implement an alternative. You just need to provide a container with the expected interface (see comments at the top of lru_cache_impl.h). Some cache implementations actually let you change the type of the containers in an "Options" type that you can pass in.

For instance, if you had a fixed-size map that doesn't allocate, it would be easy to plug it in the StaticLruCache and get a no-allocation cache.

Value provider and dropped entry callback

When using the memoizing cache, any missing key is resolved by calling the function-like object provided at construction time.

Moreover, if needed, you can pass a function that will be called with any deleted key. This allows you to have custom cleanup, keep some statistics and so on.

Benchmarks

The provided implementation were compared with several LRU cache implementations gathered from GitHub.

For the benchmarks, the mean is taken, with 100 samples, a minimum confidence interval of 0.95, and 100ms of warmup.

The benchmarks are run on a i7-3770 (3.4 GHz) with 16G RAM.

Random access

This benchmark initializes an array with random values chosen from a bigger range than the max cache size. The range of the random values can be modified to test different miss rates. Here we are experimenting with a 5% miss rate and a 50% miss rate.

The task is to convert the given integer to a string. The baseline doesn't use any caching.

The numbers are miss rate/cache size/queries.

Benchmark 5%/100/1k (μs) 5%/10k/100k (ms) 50%/100/1k (μs) 50%/10k/100k (ms)
baseline 352 36.3 355 36.1
nitnelave/lru_cache/dynamic 78.5 9.04 272 29.7
nitnelave/lru_cache/static 71.8 8.78 256 28.9
nitnelave/lru_cache/node 66.9 8.20 241 26.0
lamerman/lrucache 85.2 9.26 271 31.4
mohaps/LRUCache11 61.7 9.40 260 32.0
vpetrigo/caches 128.5 15.6 365 42.3
goldsborough/caches 77.2 9.64 262 31.4

Fibonacci

The task is to compute the _n_th Fibonacci number using the naive recursive formula:

fibo(n) = fibo(n - 1) + fibo(n - 2)

This usually has a O(2^n) complexity, but we can drastically reduce the runtime with caching.

The cache size was set to 10 elements.

The baseline was not run because it would take too long. We stopped at 92 because it's the biggest element that fits in 64 bits.

Benchmark fibo(60) (μs) fibo(80) (μs) fibo(92) (μs)
nitnelave/lru_cache/dynamic 4.56 6.09 7.01
nitnelave/lru_cache/static 4.27 5.96 6.60
nitnelave/lru_cache/node 3.15 4.30 4.91
lamerman/lrucache 6.11 8.29 9.49
mohaps/LRUCache11 6.04 7.90 9.38
vpetrigo/caches 12.2 16.4 18.7
goldsborough/caches 5.45 7.52 8.40

About

A C++ implementation of a LRU cache

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published