8
\$\begingroup\$

I've written a cache class which implements a last-recently-used (LRU) cache. I would like to know what you think about it and whether it's worth using it or not (due to performance issues for instance).

#include <functional>
#include <iterator>
#include <list>
#include <utility>
#include <unordered_map>

#include <boost/functional/hash.hpp>


class nop
{
public:
    void operator()(...) const volatile { }
}; /* class nop */
/* ------------------------------------------------------------------------------------- */

template<typename T>
class scale
    : public std::unary_function<T, std::size_t>
{
public:
    std::size_t operator()(T const&) const {
            return 1;
        }
}; /* template class scale */
/* ------------------------------------------------------------------------------------- */


template<typename key_type, typename T>
struct cache_traits
{
    typedef key_type                                               key_type;
    typedef T                                                      cached_type;
    typedef std::pair<key_type const, T>                           value_type;
    typedef value_type&                                            reference;
    typedef value_type const&                                      const_reference;
    typedef typename allocator_traits<value_type>::difference_type difference_type;
    typedef typename allocator_traits<value_type>::size_type       size_type;
    typedef typename allocator_traits<value_type>::pointer         pointer;
    typedef typename allocator_traits<value_type>::const_pointer   const_pointer;
}; /* template struct cache_traits */
/* ------------------------------------------------------------------------------------- */


/*********************************************************************************************************
 template class cache;
 *********************************************************************************************************/

template<
    typename key_type,
    typename T,
    class    drop     = nop<T>,
    class    hash     = boost::hash<key_type>,
    class    pred     = std::equal_to<key_type>,
    class    scale    = scale<T>,
    class    alloc    = std::allocator<std::pair<key_type const, T>>
>
class cache
    : public cache_traits<key_type, T>
{
public:
    typedef drop  drop_func;
    typedef hash  hasher;
    typedef pred  key_equal;
    typedef scale scale_func;
    typedef alloc allocator_type;
    /* --------------------------------------------------------------------------------- */

private:
    typedef std::list<value_type, alloc>                          storage_type;
    typedef typename storage_type::iterator                       storage_iterator;
    typedef typename storage_type::const_iterator                 const_storage_iterator;
    typedef std::pair<key_type const, storage_iterator>           index_pair;
    typedef std::unordered_map<key_type, storage_iterator, hash,
        pred, typename alloc::template rebind<index_pair>::other> index_type;
    typedef typename index_type::iterator                         index_iterator;
    typedef typename index_type::const_iterator                   const_index_iterator;
    /* --------------------------------------------------------------------------------- */

public:
    typedef storage_iterator                      iterator;
    typedef const_storage_iterator                const_iterator;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    /* --------------------------------------------------------------------------------- */

    cache(cache const& other)
            : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
              m_drop(other.m_drop), m_scale(other.m_scale),
              m_stg(other.m_stg), m_idx(other.m_idx) {
        }
    cache(cache const& other, alloc const& alloc)
            : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
              m_drop(other.m_drop), m_scale(other.m_scale),
              m_stg(other.m_stg, alloc), m_idx(other.m_idx, alloc) {
        }
    cache(size_type n, alloc const& alloc)
            : m_cur_size(0), m_max_size(n),
              m_stg(alloc), m_idx(n, alloc) {
        }
    cache(size_type n = 0, drop const& df = drop(), hash const& hf = hash(), pred const& eq = pred(),
        scale const& sf = scale(), alloc const& alloc = alloc())
            : m_cur_size(0), m_max_size(n),
              m_drop(df), m_scale(sf),
              m_stg(alloc), m_idx(n, hf, eq, alloc) {
        }
    template<class input_iterator>
    cache(size_type n, input_iterator first, input_iterator last, drop const& df = drop(),
        hash const& hf = hash(), pred const& eq = pred(), scale const& sf = scale(),
        alloc const& alloc = alloc())
            : m_cur_size(0), m_max_size(n),
              m_drop(df), m_scale(sf),
              m_stg(alloc), m_idx(n, hf, eq, alloc)
        {
            insert(first, last);
        }
    virtual ~cache() {
        }
    cache& operator=(cache other)
        {
            swap(other);
            return *this;
        }
    alloc get_allocator() const {
            return this->m_stg.get_allocator();
        }
    /* --------------------------------------------------------------------------------- */


    // iterators:
    iterator begin() {
            return m_stg.begin();
        }
    const_iterator begin() const {
            return m_stg.begin();
        }
    iterator end() {
            return m_stg.end();
        }
    const_iterator end() const {
            return m_stg.end();
        }
    /* --------------------------------------------------------------------------------- */

    reverse_iterator rbegin() {
            return m_stg.rbegin();
        }
    const_reverse_iterator rbegin() const {
            return m_stg.rbegin();
        }
    reverse_iterator rend() {
            return m_stg.rend();
        }
    const_reverse_iterator rend() const {
            return m_stg.rend();
        }
    /* --------------------------------------------------------------------------------- */

    const_iterator cbegin() const {
            return m_stg.cbegin();
        }
    const_iterator cend() const {
            return m_stg.cend();
        }
    const_reverse_iterator crbegin() const {
            return m_stg.crbegin();
        }
    const_reverse_iterator crend() const {
            return m_stg.crend();
        }
    /* --------------------------------------------------------------------------------- */

    // capacity:
    bool empty() const {
            return size() == 0;
        }
    size_type max_size() const {
            return m_max_size;
        }
    void resize(size_type n)
        {
            m_max_size = n;
            adjust();
        }
    size_type size() const {
            return m_cur_size;
        }
    /* --------------------------------------------------------------------------------- */

    // element access:
    T& at(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
                return pos->second->second;
            throw std::out_of_range("cache::at() : no such element is present");
        }
    T const& at(key_type const& key) const {
            return const_cast<cache*>(this)->at(key);
        }
    iterator fetch(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                touch(pos->second);
                return pos->second;                
            }
            return end();
        }
    bool touch(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                touch(pos->second);
                return true;
            }
            return false;
        }
    /* --------------------------------------------------------------------------------- */

    // modifiers:
    std::pair<iterator, bool> insert(const_reference x)
        {
            if (m_idx.find(x.first) == m_idx.end())
            {
                iterator pos = add(x);
                return std::make_pair(pos, pos == end());
            }
            return std::make_pair(m_stg.end(), false);
        }
    template<class input_iterator> void insert(input_iterator first, input_iterator last)
        {
            for (; first != last; ++first) 
                store(*first);
        }
    size_type erase(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                remove(pos);   
                return 1;
            }
            return 0;
        }
    iterator erase(const_iterator pos)
        {
            const_index_iterator index_pos = m_idx.find(pos->first);
            if (index_pos != m_idx.end())
                return remove(index_pos);   
            return end();
        }
    iterator erase(const_iterator first, const_iterator last)
        {
            for (const_iterator i = first; i != last; ++i)
            {
                m_drop(i->second);
                m_cur_size -= m_scale(i->second);
                m_idx.erase(i->first);
            }
            return m_stg.erase(first, last);
        }
    void clear()
        {
            m_idx.clear();
            m_stg.clear();
            m_cur_size = 0;
        }
    void swap(cache& other)
        {
            using std::swap;

            swap(m_idx, other.m_idx);
            swap(m_stg, other.m_stg);
            swap(m_cur_size, other.m_cur_size);
            swap(m_max_size, other.m_max_size);
        }
    iterator store(const_reference x)
        {
            const_index_iterator pos = m_idx.find(x.first);
            if (pos != m_idx.end())
            {
                pos->second->second = x.second;
                touch(pos->second);
                return pos->second;
            }
            return add(x);
        }
    size_type exchange_key(key_type const& x, key_type const& y)
        {
            const_index_iterator xpos = m_idx.find(x);
            if (xpos != m_idx.end())
            {
                const_index_iterator ypos = m_idx.find(y);
                if (ypos != m_idx.end())
                {
                    swap(const_cast<key_type&>(xpos->second->first),
                        const_cast<key_type&>(ypos->second->first));

                    touch(xpos->second);
                    touch(ypos->second);
                    return 1;
                }
            }
            return 0;
        }
    size_type replace_key(key_type const& old_key, key_type const& new_key)
        {
            const_index_iterator pos = m_idx.find(old_key);
            if (pos != m_idx.end())
            {
                if (m_idx.insert(std::make_pair(new_key, pos->second)).second)
                {
                    const_cast<key_type&>(pos->second->first) = new_key;
                    touch(pos->second);
                    m_idx.erase(pos);
                    return 1;
                }
            }
            return 0;
        }
    /* --------------------------------------------------------------------------------- */

    // observers:
    drop drop_function() const {
            return m_drop;
        }
    hash hash_function() const {
            return m_idx.hash_function();
        }
    pred key_eq() const {
            return m_idx.key_eq();
        }
    scale scale_function() const {
            return m_scale;
        }
    /* --------------------------------------------------------------------------------- */

    // map operations:
    size_type count(key_type const& key) const {
            return m_idx.find(key) != this->m_idx.end() ? 1 : 0;
        }
    iterator find(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
                return pos->second;
            return end();
        }
    const_iterator find(key_type const& key) const {
            return const_cast<cache*>(this)->find(key);
        }
    /* --------------------------------------------------------------------------------- */

    iterator lower_bound(key_type const& key)
        {
            const_index_iterator lower_bound = m_idx.lower_bound(key);
            if (lower_bound != m_idx.end())
                return lower_bound->second;
            return end();
        }
    const_iterator lower_bound(key_type const& key) const {
            return const_cast<cache*>(this)->lower_bound(key);
        }
    iterator upper_bound(key_type const& key)
        {
            const_index_iterator upper_bound = m_idx.upper_bound(key);
            if (upper_bound != m_idx.end())
                return upper_bound->second;
            return end();
        }
    const_iterator upper_bound(key_type const& key) const {
            return const_cast<cache*>(this)->upper_bound(key);
        }
    /* --------------------------------------------------------------------------------- */

    std::pair<iterator, iterator> equal_range(key_type const& key)
        {
            const_index_iterator equal_range = m_idx.find(key);
            if (equal_range != m_idx.end())
                return std::make_pair(equal_range->second, equal_range->second);

            iterator end = end();
            return std::make_pair(end, end);
        }
    std::pair<const_iterator, const_iterator> equal_range(key_type const& key) const {
            return const_cast<cache*>(this)->equal_range(key);
        }
    /* --------------------------------------------------------------------------------- */

private:
    iterator add(const_reference x)
        {
            m_stg.push_front(x);
            iterator pos = m_stg.begin();

            size_type size = m_scale(pos->second);
            if (size <= m_max_size)
            {
                m_cur_size += size;
                m_idx[pos->first] = pos;
                adjust();
                return pos;
            }

            m_stg.erase(pos);
            return end();
        }
    void adjust()
        {
            while (m_cur_size > m_max_size)
                overflow();
        }
    void overflow() {
            erase(boost::prior(m_stg.end())->first);
        }
    iterator remove(const_index_iterator const& pos)
        {
            T const& x = pos->second->second;
            m_drop(x);
            m_cur_size -= m_scale(x);

            iterator next = m_stg.erase(pos->second);
            m_idx.erase(pos);
            return next;
        }
    void touch(const_storage_iterator const& pos) {
            m_stg.splice(m_stg.begin(), m_stg, pos);
        }
    /* --------------------------------------------------------------------------------- */

    drop  m_drop;
    scale m_scale;
    /* --------------------------------------------------------------------------------- */

    index_type   m_idx;
    storage_type m_stg;
    size_type    m_cur_size,
                 m_max_size;
    /* --------------------------------------------------------------------------------- */

    friend void swap(cache& x, cache& y) {
            x.swap(y);
        }
}; /* template class cache */
/* ------------------------------------------------------------------------------------- */
\$\endgroup\$
4
\$\begingroup\$
  • For one thing, this is not gonna work if m_idx contains iterators into m_stg:

    cache(cache const& other)
                : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
                  m_drop(other.m_drop), m_scale(other.m_scale),
                  m_stg(other.m_stg), m_idx(other.m_idx) {
    
  • you cannot shuffle keys of unordered_maps like that:

    size_type exchange_key(key_type const& x, key_type const& y)
        {
            const_index_iterator xpos = m_idx.find(x);
            if (xpos != m_idx.end())
            {
                const_index_iterator ypos = m_idx.find(y);
                if (ypos != m_idx.end())
                {
                    swap(const_cast<key_type&>(xpos->second->first),
                        const_cast<key_type&>(ypos->second->first));
    
  • this may cause UB when overflow() unfortunately removes pos.

    iterator add(const_reference x)
        {
            m_stg.push_front(x);
            iterator pos = m_stg.begin();
    
            size_type size = m_scale(pos->second);
            if (size <= m_max_size)
            {
                m_cur_size += size;
                m_idx[pos->first] = pos;
                adjust();
                return pos;
            }
    
  • I'd be happier if accessor functions hadn't thrown exceptions on missing data, since you can't really control what is and what isn't in the cache. A return of eg. boost::optional<T> would be appropriate.

     // element access:
    T& at(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
                return pos->second->second;
            throw std::out_of_range("cache::at() : no such element is present");
        }
    
\$\endgroup\$
  • \$\begingroup\$ The at() method is supposed to throw. Traditionally at() is a checked access into a container that throws when the key is invalid. That is why you have other accessors that return iterators (in this case fetch()) so you can compare the iterator against end() to validate if the key is in the container. \$\endgroup\$ – Martin York Oct 12 '11 at 18:29
  • \$\begingroup\$ @LokiAstari: That is traditional for vectors, but not really appropriate for caches. Using this interface (even fetch()) would be terribly annoying, I'd suggest something like T get(Key k, function<T()> gen) that would return the cached value or recompute it with gen, other designs are possible too. Still, a method that throws an exception unpredictably is really bad design. \$\endgroup\$ – jpalecek Oct 12 '11 at 19:15
  • \$\begingroup\$ I have to disagree. I think it perfectly appropriate for caches where you can quite literally miss. Also returning an iterator with end() fits with all the standard usage patterns of C++ and is not going to confuse anybody. \$\endgroup\$ – Martin York Oct 12 '11 at 19:19
  • \$\begingroup\$ Depends what level you want to work at. I don't want my CPU's caches to draw my attention to the fact every time I fetch some RAM which isn't cached... I just want them to transparently go away and get hold of the value. Ditto OS's RAM caching of disk... the OS can take care of some data not being present, and I'm happy for my app/process to block while I wait. See my answer for more. \$\endgroup\$ – timday Nov 4 '11 at 21:27
1
\$\begingroup\$

On the cache miss issue specifically: in my experience, for most applications of LRU caches, rather than having the cache throwing or returning an empty boost::optional on a cache miss, it's more usable if the cache knows how to compute the missing value (e.g by providing it with a function object to do such). Then the user can just use the cache as though it was a more efficient (assuming a reasonable proportion of cache hits) version of the the function. Like function memoisation but with a limited size.

Examples of such a style of cache interface here (although considerably less configurable than yours).

Such an interface could just be implemented as a thin wrapper around your class of course.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.