libcache

libcache is a C++ header-only library for software based caches that implements common cache algorithms. See below for the cache replacement polocies currently supported.

Cache Replacement Policy

Currently implemented:

• LRU - Least Recently Used
• LFU - Least Frequently Used

Time complexity:

Policy	put	get	resize
LRU	O(1)	O(1)	O(n)
LFU	O(1)	O(1)	O(n)

Space complexity is O(n) for all policies.

There are many other interesting policies; similar idea but for pages

Features

• Supports standard cache operations: get, put
  • Both have optimal big-oh runtime: O(1)
• Supports custom (user-defined) types as key and/or value using templates
  • Like std::unordered_map, operator== overload and hash functor on the custom type are required.
• Supports resize
  • It's unrealistic to resize a physical cache, but it could be useful for a software based cache
• Well tested (framework used: Catch). Tests are available here

Usage

See example.cpp for a more complete example, which includes a demo of using custom type as key.

#include "lfu.hpp"

void foo(...) {
    caches::lfu<int, int> cache(4);
    
    cache.put(1, 11);
    cache.put(3, 33);
    cache.put(5, 55);
    cache.put(3, 333);
    
    // Expected stdout: 333, 55
    std::cout << cache.get(3) << ", " << cache.get(5) << std::endl;
    
    // resizing down causes eviction, '1' will be evicted because it is the LFU
    cache.resize(2);
    
    // This call will cause an exception to be thrown because
    // '1' is not in the cache anymore
    cache.get(1);
}

Setup

The only requirement setup is a C++11 compiler.

References

• O(1) LFU paper - 2010
• LFU in Golang blog
• A cool cache library

Contribution

Contribution and questions are welcome at issues and eltonlin@umich.edu. Fork this repo to submit a pull request to the master branch. To implement another cache policy, visit cache.hpp to see the base class. Thanks!

Adding A New Policy

Simply create a subclass of the base class in cache.hpp. The new policy class needs to implement(override) 3 virtual functions for operating the policy and managing the internal data structures. And that's it! See tests/ for ideas to test the new cache policy.

• policy_put(k, val): adds a new entry to cache
• touch(k): updates the 'order' of the entry with key k (e.g. in LFU, increment its frequency count)
• evict(): performs a single eviction on the cache

TODO

• Use cmake to improve organizing project structure and managing dependencies. It can also aid compiling process and time.
• Implement other policies.
• Thread-safe