LruSlabCache.hpp

Go to the documentation of this file.

#ifndef TATAMI_CHUNKED_LRU_SLAB_CACHE_HPP
#define TATAMI_CHUNKED_LRU_SLAB_CACHE_HPP
 
#include <unordered_map>
#include <list>
 
namespace tatami_chunked {
 
template<typename Id_, class Slab_> 
class LruSlabCache {
private:
    typedef std::pair<Slab_, Id_> Element;
    std::list<Element> my_cache_data;
    std::unordered_map<Id_, typename std::list<Element>::iterator> my_cache_exists;
    size_t my_max_slabs;
    Id_ my_last_id = 0;
    Slab_* my_last_slab = NULL;
 
public:
    LruSlabCache(size_t max_slabs) : my_max_slabs(max_slabs) {}
 
    LruSlabCache(const LruSlabCache&) = delete;
 
    LruSlabCache& operator=(const LruSlabCache&) = delete;
 
    // Iterators are guaranteed to be valid after move, see Notes in
    // https://en.cppreference.com/w/cpp/container/list/list
    // https://en.cppreference.com/w/cpp/container/list/operator%3D
    LruSlabCache& operator=(LruSlabCache&&) = default; 
    LruSlabCache(LruSlabCache&&) = default;
 
    // Might as well define this.
    ~LruSlabCache() = default;
public:
    template<class Cfunction_, class Pfunction_>
    const Slab_& find(Id_ id, Cfunction_ create, Pfunction_ populate) {
        if (id == my_last_id && my_last_slab) {
            return *my_last_slab;
        }
        my_last_id = id;
 
        auto it = my_cache_exists.find(id);
        if (it != my_cache_exists.end()) {
            auto chosen = it->second;
            my_cache_data.splice(my_cache_data.end(), my_cache_data, chosen); // move to end.
            my_last_slab = &(chosen->first);
            return chosen->first;
        } 
 
        typename std::list<Element>::iterator location;
        if (my_cache_data.size() < my_max_slabs) {
            my_cache_data.emplace_back(create(), id);
            location = std::prev(my_cache_data.end());
        } else {
            location = my_cache_data.begin();
            my_cache_exists.erase(location->second);
            location->second = id;
            my_cache_data.splice(my_cache_data.end(), my_cache_data, location); // move to end.
        }
        my_cache_exists[id] = location;
 
        auto& slab = location->first;
        populate(id, slab);
        my_last_slab = &slab;
        return slab;
    }
 
public:
    size_t get_max_slabs() const {
        return my_max_slabs;
    }
 
    size_t get_num_slabs() const {
        return my_cache_data.size();
    }
};
 
// COMMENT:
// As tempting as it is to implement an LruVariableSlabCache, this doesn't work out well in practice.
// This is because the Slab_ objects are re-used, and in the worst case, each object would have to be large enough to fit the largest slab.
// At this point, we have several options:
//
// - Pre-allocate each Slab_ instance to have enough memory to fit the largest slab, in which case the slabs are not variable.
// - Allow Slab_ instances to grow/shrink their memory allocation according to the size of its assigned slab.
//   This reduces efficiency due to repeated reallocations, and memory usage might end up exceeding the nominal limit anyway due to fragmentation.
// - Share a single memory pool across slabs, and manually handle defragmentation to free up enough contiguous memory for each new slab.
//   Unlike the oracular case, we don't have the luxury of defragmenting once for multiple slabs.
//   Instead, we might potentially need to defragment on every newly requested slab, which is computationally expensive.
//
// See also https://softwareengineering.stackexchange.com/questions/398503/is-lru-still-a-good-algorithm-for-a-cache-with-diferent-size-elements.
// This lists a few methods for dealing with fragmentation, but none of them are particularly clean.
// It's likely that just using the existing LruSlabCache with the maximum possible slab size is good enough for most applications.
 
}
 
#endif