#include <cassert>
#include <cstdint>
#include <print>

int main() {
LFU<std::string, uint64_t> freq_cache(3);

freq_cache.set("foo", 11);
freq_cache.set("bar", 22);
freq_cache.set("baz", 33);

freq_cache.get("foo");
std::optional<uint64_t> foo = freq_cache.get("foo");
foo = fr...

In the last post I wrote up a naive implementation of a Least Frequently Used cache. A better and, for a time, more common implementation would have used a tree with the min-heap property to give O(log n). In the conclusion I mentioned that there’s a way to implement one with O(1) time complexity for both operations at the cost of some extra memory. Here is such an implementation in C++23.

We’ll start with the same main function as before:

#include <cassert>
#include <cstdint>
#include <print>

int main() {
LFU<std::string, uint64_t> freq_cache(3);

freq_cache.set("foo", 11);
freq_cache.set("bar", 22);
freq_cache.set("baz", 33);

freq_cache.get("foo");
std::optional<uint64_t> foo = freq_cache.get("foo");
foo = freq_cache.get("foo");

assert(foo);

std::optional<uint64_t> bar = freq_cache.get("bar");

assert(bar);

freq_cache.set("qux", 44);

std::optional<uint64_t> baz = freq_cache.get("baz");

assert(baz.has_value() == false);

return 0;
}

Our goal today is to provide an implementation for LFU that behaves the same way as the naive implementation but whose operations are O(1) in the worst case.

Return of the Doubly Linked List

Remember the Least Recently Used Cache post? We used a doubly-linked list there which gave us an optimal solution. We’ll use it again for this implementation.

The nice thing about heaps is that they allow us to control where a value is located in our structure so that accessing it is O(1). The disadvantage of them is that in order to maintain the heap invariant the code is repeatedly swapping values over the structure, O(log n) times in the worst case. What we would like is a structure that allows us to place our value where we can access it fast while building the structure in a way that doesn’t require us to traverse it.

We can do this with doubly-linked lists but we’re going to need one for each frequency count in the set of cache values.

So we’re going to need two maps: one for the cached values and counts and one for the frequencies mapping the counts to the cached values!

Since both maps will share the structure of cached values and counts let’s start with a definition for CacheValue:

template <typename K, typename V> struct CacheValue {
K key;
V value;
uint64_t freq_count;

// Neat C++20 feature that tells the compiler to generate the
// equality relations for us
auto operator<=>(const CacheValue<K, V>&) const = default;
};

Then we can sketch out the structure of LFU:

// additional includes
#include <list>
#include <map>

template <typename K, typename V> struct LFU {
size_t capacity;
uint64_t min_freq; // This will be used to lookup the LFU key in
// `freq`.

std::map<K, CacheValue<K, V>> cache;
std::map<uint64_t, std::list<CacheValue<K, V>>> freq;

LFU(size_t capacity) : capacity(capacity), cache() {}

size_t size() {
return cache.size();
}
}

The frequency map freq stores a double-linked list of cache values for each frequency count in the set of cache values.

Efficient Operations

First, let’s implement the get operation. It looks similar to the naive implementation:

template <typename K, typename V> struct LFU {
// ...

std::optional<V> get(K key) {
// We're adding our invariant here that there should be at most as
// many frequency lists as there are values in the cache.
assert(size() >= freq.size());

if (cache.contains(key)) {
CacheValue cv = cache.at(key);
update_frequency(cv);
return cv.value;
}

return {};
}
};

This time we’re going to be able to implement update_frequency as an O(1) operation thanks to the way the data is structured:

template <typename K, typename V> struct LFU {
// ...
private:
void update_frequency(CacheValue<K, V>& cv) {
assert(freq.contains(cv.freq_count));

// Keys in the frequency map are frequency counts of cache values.
// Cache values in the list at that key all share the same
// frequency and should be added in "LRU" order...
uint64_t freq_key = cv.freq_count;
std::list<CacheValue<K, V>> freq_list = freq.at(freq_key);

// Since we're going to modify the frequency count of this cache
// value, we need to remove it from this frequency list
freq_list.remove(cv);

if (freq_list.empty()) {
// And if there are no more cache values at this frequency
// count, remove it from the frequency map.
freq.erase(freq_key);
if (freq_key == min_freq) {
min_freq += 1; // This was the least frequently used before
// but we've accessed it one more time so we
// increment it.
}
}

cv.freq_count++;
add_cache(cv);
}

void add_cache(const CacheValue<K, V>& cv) {
// When we add a cache value to the cache, we also add the cache
// value to the frequency list in the frequency map.
uint64_t freq_key = cv.freq_count;
if (freq.contains(freq_key)) {
freq[freq_key].emplace_front(cv);
} else {
freq[freq_key] = {cv};
}
}
}

Most of the work is done by the two helper functions, update_frequency and add_cache which will also be used in the implementation of set:

template <typename K, typename V> struct LFU {
// ...
void set(K key, V value) {
if (cache.contains(key)) {
// Very similar to the naive version...
CacheValue cv = cache.at(key);
cv.value = value;
update_frequency(cv);
} else {
if (size() == capacity) {
// Because we keep track of the least frequently used count
// in `min_freq` we have `O(1)` access to look up its
// frequency list
std::list<CacheValue<K, V>> lfu_list = freq.at(min_freq);
// And get the cache value from the front of it, also `O(1)`
// and better, in LRU order... no tie breaking needed
CacheValue<K, V> cv = lfu_list.front();
lfu_list.pop_front();
cache.erase(cv.key);
}

// A new cache value always has a frequency of 1...
CacheValue<K, V> new_cv = {key, value, 1};
add_cache(new_cv);
cache[key] = new_cv;

// Which means our least frequenty used key is also 1
min_freq = 1;
}
}
}

Conclusion

We’re going to use a fair bit more memory to achieve O(1) get and set operations on our cache than in a heap-based solution. However this could make it a more attractive option when compared to an LRU cache!

Programming often requires us to think about trade-offs. What we gain in speed, in this structure, we sacrifice in space. It’s good to know what those requirements are so that we can choose a sufficient structure.

Thanks for reading and happy hacking out there.