In the last post I wanted to demonstrate how to implement a time-efficient Least Frequently Used cache in C++23 using doubly-linked lists. While the idea and the approach was right, the implementation was not, and we ended up with O(n) operations (again) instead of the promised, O(1).
Here’s the annotated implementation so you can see where the problem is:
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <list>
#include <map>
#include <optional>
#include <print>
#include <ranges>
template <typename K, typename V> struct CacheValue {
K key;
V value;
uint64_t freq_count;
// There's a problem with this struct...
auto operator<=>(const CacheValue<K, V>&) const = def...In the last post I wanted to demonstrate how to implement a time-efficient Least Frequently Used cache in C++23 using doubly-linked lists. While the idea and the approach was right, the implementation was not, and we ended up with O(n) operations (again) instead of the promised, O(1).
Here’s the annotated implementation so you can see where the problem is:
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <list>
#include <map>
#include <optional>
#include <print>
#include <ranges>
template <typename K, typename V> struct CacheValue {
K key;
V value;
uint64_t freq_count;
// There's a problem with this struct...
auto operator<=>(const CacheValue<K, V>&) const = default;
};
template <typename K, typename V> struct LFU {
size_t capacity;
uint64_t min_freq;
// And there's a problem here...
std::map<K, CacheValue<K, V>> cache;
// the code has to maintain two copies of the same data
std::map<uint64_t, std::list<CacheValue<K, V>>> freq;
LFU(size_t capacity) : capacity(capacity), cache() {}
size_t size() {
return cache.size();
}
std::optional<V> get(K key) {
assert(size() >= freq.size());
if (cache.contains(key)) {
CacheValue cv = cache.at(key);
update_frequency(cv);
return cv.value;
}
return {};
}
void set(K key, V value) {
if (cache.contains(key)) {
// Problem here...
CacheValue cv = cache.at(key);
cv.value = value;
update_frequency(cv);
} else {
if (size() == capacity) {
// And problem here...
std::list<CacheValue<K, V>> lfu_list = freq.at(min_freq);
CacheValue<K, V> cv = lfu_list.front();
lfu_list.pop_front();
cache.erase(cv.key);
}
CacheValue<K, V> new_cv = {key, value, 1};
// And here...
add_cache(new_cv);
cache[key] = new_cv;
min_freq = 1;
}
}
private:
void update_frequency(CacheValue<K, V>& cv) {
assert(freq.contains(cv.freq_count));
uint64_t freq_key = cv.freq_count;
// Problem here!
std::list<CacheValue<K, V>> freq_list = freq.at(freq_key);
// The main problem is here, this operation is `O(n)`!
freq_list.remove(cv);
if (freq_list.empty()) {
freq.erase(freq_key);
if (freq_key == min_freq) {
min_freq += 1;
}
}
cv.freq_count++;
add_cache(cv);
}
void add_cache(const CacheValue<K, V>& cv) {
uint64_t freq_key = cv.freq_count;
if (freq.contains(freq_key)) {
freq[freq_key].emplace_front(cv);
} else {
freq[freq_key] = {cv};
}
}
};
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;
}
There are many problems with this code.
Let’s take a quick review of what we’re trying to achieve with this implementation. Like every cache we want to stash values under keys. We want to bound the size of the cache and evict keys that have been used the least frequently.
To achieve this we’re planning to use two maps:
- a map of keys to values
- a map of frequency count to frequency list
Now let’s revisit the main problem with the original implementation:
void update_frequency(CacheValue<K, V>& cv) {
// ...
// The main problem is here, this operation is `O(n)`!
freq_list.remove(cv);
// ...
}
This line destroys the performance of this cache, reducing both operations to O(n). This is because remove traverses the entire list structure using an equality check on each element to see if it needs to be removed. What we actually want is to erase the “node” in the doubly-linked list in O(1) time which is something we should be able to do if we could keep a reference to that node: we just drop the pointers and free the memory!
When we read a value in the cache with get or we update a value with set we need to update the frequency count for that key. We keep a map of frequency count to frequency list so that we can ensure that the least frequently used key is in a place where we can access it in O(1) time. So when we change the frequency count of a key, we need to update the frequency map by moving the CachValue values around.
Keep Everything In Its Right Place
In order to resolve the main issue we’re going to have to revisit how the original implementation structured the data. The problem is that the CacheValue values are stored in two places. There should be one place for any piece of data!
So let’s redefine our mappings:
template <typename K, typename V> struct LFU {
using iterator = std::list<CacheValue<K, V>>::iterator;
size_t capacity;
uint64_t min_freq;
// Here is the main change!
std::map<K, iterator> cache;
// An iterator is like a fat-pointer that points to a place in a
// collection... or like a pointer, if you're used to C.
//
// The main thing to note is that we're going to store the
// CacheValue in the frequency lists and provide pointers to them
// in the cache.
std::map<uint64_t, std::list<CacheValue<K, V>>> freq;
LFU(size_t capacity) : capacity(capacity), cache() {}
size_t size() {
return cache.size();
}
// ...
}
I’m tempted to invert the relationship between these maps, keeping the cache data values in the cache map and only keeping references to keys in the freq map. However this should be good enough. There is only one CacheValue across both maps.
Now we should be able to get an iterator when we insert a CacheValue into a frequency list, and keep it in the cache.
Enter the Iterator
An iterator, as mentioned in the comments of code sample in the previous section, is kind of like a pointer. It points to an element inside of a collection. In this case, a “node” inside our doubly-linked list.
We can get one of these from a call to insert on a frequency list in freq which will give us an iterator that points to the “location” in the std::list where we inserted the CacheValue.
We can then use the iterator to call erase which would then solve the problem!
Indirection Is Not Abstraction
All of this “safety” of not handling pointers, only opaque references through objects like iterators, still requires the same caution one would take when handling pointers.
This became apparent when I started making these changes and noticing junk data. It seemed like there was a life time issue. Whatever the iterator was pointing to was going out of scope or being destroyed when the code went to deference the iterator to access the value.
The approach I took to sort this out was to override the move and copy constructors on CacheValue. I wanted to ensure that once inserted into the cache that there was only ever one instance of a CacheValue: no copies, no moves.
So I enabled the following code on the CacheValue struct:
template <typename K, typename V> struct CacheValue {
// ...
CacheValue(K key, V value, uint64_t freq_count) : key(key), value(value), freq_count(freq_count) {}
CacheValue(CacheValue<K, V>&& other) {}
// ...
};
This quickly revealed several places in the code where copies of the frequency lists and CacheValue values were implicitly being made by assignment.
I went through the code line by line and checked every assignment and made sure that each assignment was taking a reference.
Changes to the Internals
Eventually I found that add_cache was poorly named and… unnecessary, so I removed it.
The main change is to update_frequency. We call this method in get and set. When get calls this function it expects to updated the frequency count of the CacheValue for the key but there’s a case where the cache map will need to update the iterator it holds on to: when the CacheValue is moved to a new frequency list in the frequency map.
Here’s the updated update_frequency:
template <typename K, typename V> struct LFU {
// ...
private:
void update_frequency(const K &key) {
assert(cache.contains(key));
// We take a reference to the iterator in the cache, not a copy
iterator& it = cache.at(key);
CacheValue<K, V>& cv = *it; // And we can get the `CacheValue` by
// this over-ride on the dereference
// operator.
V value = cv.value; // Copy the values for later...
uint64_t freq_count = cv.freq_count;
uint64_t new_freq_count = freq_count + 1;
std::list<CacheValue<K, V>>& freq_list = freq.at(freq_count);
freq_list.erase(it); // Ah, sweet `O(1)` goodness, problem solved!
// As before, we update the frequency map and min_count if needed
if (freq_list.empty()) {
freq.erase(freq_count);
if (freq_count == min_freq) {
min_freq++;
}
}
// We can end up deleting the frequency list in some cases, create
// a new one if needed.
if (!freq.contains(new_freq_count)) {
freq[new_freq_count] = {};
}
// Insert a new copy of the `CacheValue`, updating the cache
// iterator to point to the new node.
CacheValue<K, V> new_cv(key, value, new_freq_count);
iterator new_it = freq[new_freq_count].insert(freq[new_freq_count].end(), new_cv);
cache[key] = new_it;
}
// ...
};
Update Get and Set
We need to make some minor changes to the get and set functions to use the new internal structure. Here are the new definitions:
template <typename K, typename V> struct LFU {
// ...
std::optional<V> get(const K &key) {
if (cache.contains(key)) {
// As before only we dereference the iterator to get the
// `CacheValue`
CacheValue<K, V> &cv = *cache.at(key);
update_frequency(key);
return cv.value;
}
return {};
}
void set(const K& key, const V& value) {
if (cache.contains(key)) {
CacheValue<K, V>& cv = *cache.at(key);
cv.value = value;
update_frequency(key);
} else {
// Handle eviction...
if (size() == capacity) {
std::list<CacheValue<K, V>>& freq_list = freq.at(min_freq);
K lfu_key = freq_list.front().key;
freq_list.pop_front();
cache.erase(lfu_key);
}
// Now we set min_freq as before and ensure there's a frequency
// list to insert into
min_freq = 1;
if (!freq.contains(min_freq)) {
freq[min_freq] = {};
}
std::list<CacheValue<K, V>>& min_list = freq.at(min_freq);
CacheValue<K, V> cv(key, value, 1);
iterator it = min_list.insert(min_list.end(), cv);
cache[key] = it;
}
}
};
With this code we now need to enable copying again on CacheValue. We can remove or comment out the move constructor in the definition. We need it because if we try to use emplace_back to construct a new CacheValue in-place and try to use the end() method on the list to get the iterator, we actually get an invalid iterator!
This is because the “end” iterator refers to the place after the last value in the collection.
So we need to use insert to get an iterator to our placed value and insert does not have an override to construct the value in-place.
This change was largely okay with me. Constraining the copies and moves was very useful up until this point and allowing copies in one particular place instead of everywhere, as is the default, served it’s purpose: turning implicit copies into errors.
Conclusion
Here’s the full listing for the complete implementation:
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <list>
#include <map>
#include <optional>
#include <print>
#include <ranges>
template <typename K, typename V> struct CacheValue {
K key;
V value;
uint64_t freq_count;
CacheValue(K key, V value, uint64_t freq_count) : key(key), value(value), freq_count(freq_count) {}
// CacheValue(CacheValue<K, V>&& other) {}
auto operator<=>(const CacheValue<K, V>&) const = default;
};
template <typename K, typename V> struct LFU {
using iterator = std::list<CacheValue<K, V>>::iterator;
size_t capacity;
uint64_t min_freq;
std::map<K, iterator> cache;
std::map<uint64_t, std::list<CacheValue<K, V>>> freq;
LFU(size_t capacity) : capacity(capacity), cache() {}
size_t size() {
return cache.size();
}
std::optional<V> get(const K &key) {
if (cache.contains(key)) {
CacheValue<K, V> &cv = *cache.at(key);
update_frequency(key);
return cv.value;
}
return {};
}
void set(K key, V value) {
if (cache.contains(key)) {
CacheValue<K, V>& cv = *cache.at(key);
cv.value = value;
update_frequency(key);
} else {
if (size() == capacity) {
std::list<CacheValue<K, V>>& freq_list = freq.at(min_freq);
K lfu_key = freq_list.front().key;
freq_list.pop_front();
cache.erase(lfu_key);
}
min_freq = 1;
if (!freq.contains(min_freq)) {
freq[min_freq] = {};
}
std::list<CacheValue<K, V>>& min_list = freq.at(min_freq);
CacheValue<K, V> cv(key, value, 1);
iterator it = min_list.insert(min_list.end(), cv);
cache[key] = it;
}
}
private:
void update_frequency(const K &key) {
assert(cache.contains(key));
iterator& it = cache.at(key);
CacheValue<K, V>& cv = *it;
V value = cv.value;
uint64_t freq_count = cv.freq_count;
uint64_t new_freq_count = freq_count + 1;
std::list<CacheValue<K, V>>& freq_list = freq.at(freq_count);
freq_list.erase(it);
if (freq_list.empty()) {
freq.erase(freq_count);
if (freq_count == min_freq) {
min_freq++;
}
}
if (!freq.contains(new_freq_count)) {
freq[new_freq_count] = {};
}
CacheValue<K, V> new_cv(key, value, new_freq_count);
iterator new_it = freq[new_freq_count].insert(freq[new_freq_count].end(), new_cv);
cache[key] = new_it;
}
};
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;
}
While there are still improvements to explore I learned a lot about std::list, iterator, tricks with constructors to guide us towards better code, and was able to refresh my understanding of C++ references and qualifiers.
If I were to move forward with this implementation I would look into making the relationship between cache and freq explicit. I’d also look into trying to simplify those structures further to see if it would make the implementation more simple to manage and reduce the amount of data it stores.
All in all, a great exercise! Thank you for reading. All the best out there and happy hacking!