4
\$\begingroup\$

I recently implemented a cache for a pet project of mine. The main objectives behind this implementation were:

  1. Support move-only types for values: C++11 is here, and some of the objects that will be used with this template are movable but not copyable. Keys are fine with a copyable requirement because move-only keys make little sense in my opinion.

  2. Fast key lookup.

  3. Lazy evaluation: if the creation of the cached value type is an expensive operation, unnecessary creation is undesirable. Instead of creating the value directly and passing it along, I can simply pass a lambda or an existing factory function or function object, like this:

    lru_cache<int,int> c;
    c.get_or_add(17, [&blah]{ return long_calculation(blah); });
    
  4. Simple syntax when lazy evaluation is not needed: sometimes if an instance is available, or its creation is "free", using a lambda can be cumbersome. I'd rather just pass it directly:

    c.get_or_add(17, 42); // int literals are "free", no need for laziness
    

Points 1 and 2 are achieved with a hash map of nodes in a linked list. The hash map gives fast lookup, and the linked list tracks the order of use. I tried to use Boost.Intrusive for the internal linked list, but its hooks don't have move semantics, so I had to roll my own :)

Points 3 and 4 are achieved through the meta::lazy<T>::eval function. It alone decides whether the argument is a function that is to be called or just a value to be returned.

Here is the code:

// for wheels::meta::lazy
#include "../meta/traits.hpp"

#include <functional>
#include <cstddef>
#include <type_traits>
#include <unordered_map>
#include <utility>

namespace wheels {
    //! A cache that evicts the least recently used item.
    template <typename Key,
              typename T,
              typename Hash = std::hash<Key>,
              typename Pred = std::equal_to<Key>>
    class lru_cache {
    public:
        //! Initializes an LRU cache with the given capacity.
        lru_cache(std::size_t capacity) : front(), back(), map(), capacity(capacity) {}

        //! Fetches an item from the cache, or adds one if it doesn't exist.
        /*! The value parameter can be passed directly, or lazily (i.e. as a factory function). */
        template <typename Lazy>
        T& get_or_add(Key const& key, Lazy value) {
            auto it = map.find(key);
            if(it != map.end()) {
                touch(it);
                return it->second.value;
            } else {
                return add(key, meta::lazy<T>::eval(value));
            }
        }

        //! Flushes the cache evicting all entries.
        void flush() {
            front = back = nullptr;
            map.clear();
        }

    private:
        //! Moves a recently used entry to the front.
        template <typename Iterator>
        void touch(Iterator it) noexcept {
            auto& entry = it->second;
            unplug(entry);
            push_front(entry);
        }
        //! Adds a new entry.
        template <typename Tf>
        T& add(Key const& key, Tf&& value) {
            cache_entry entry(key, std::forward<Tf>(value));
            auto item = std::make_pair(key, std::move(entry));
            auto it = map.insert(std::move(item)).first;
            push_front(it->second);
            if(map.size() > capacity) evict();
            return it->second.value;
        }
        //! Evicts the least recently used entry.
        void evict() {
            map.erase(back->key);
            unplug(*back);
        }

        //! An entry in the cache. Maintains a linked list to track the LRU.
        struct cache_entry {
            template <typename Tf>
            cache_entry(Key const& key, Tf&& value)
            : key(key), value(std::forward<Tf>(value)), next(), prev() {}

            cache_entry(cache_entry&& that)
            : key(std::move(that.key)), value(std::move(that.value)) {}

            Key key;
            T value;
            cache_entry* next;
            cache_entry* prev;
        };

        //! Unplugs an entry from the linked list.
        void unplug(cache_entry& entry) {
            if(entry.prev) {
                entry.prev->next = entry.next;
            } else {
                front = entry.next;
            }
            if(entry.next) {
                entry.next->prev = entry.prev;
            } else {
                back = entry.prev;
            }
        }
        //! Pushes an entry to the front of the linked list.
        void push_front(cache_entry& entry) {
            entry.prev = nullptr;
            entry.next = front;
            if(front) {
                front->prev = &entry;
            } else {
                back = &entry;
            }
            front = &entry;
        }

        cache_entry* front; //! Front of the internal linked list.
        cache_entry* back; //! Back of the internal linked list.

        //! Hash table for quick lookup by key.
        std::unordered_map<Key,cache_entry, Hash> map;
        //! Maximum capacity.
        std::size_t capacity;
    };
}

I'm particularly concerned about exception safety (which I've been a bit lax about, and it's something I'm still assimilating), but any criticism is welcome.

\$\endgroup\$
  • \$\begingroup\$ Here's a nice article comparing two data structures: a) std::list and std::unordered_map and b) boost::bimap. Boost.MultiIndex also has an MRU example that should be easy to transform to LRU. \$\endgroup\$ – TemplateRex Jan 26 '14 at 16:22
5
\$\begingroup\$

I think you can make the maintenance of the list a lot easier if the list is circular.
With a circular list there are no test for NULL when inserting or removing an element (you just need a fake head node so that an empty list points back at itself).

Also you are not using encapsulation enough, this makes your methods a little more complex than they need to be. For example the cache_entry should be able to add and move itself around in the list.

Here is a simplified example of what I mean to try and show what I mean. Unfortunately there is no way I can implement the full template thing you have (way beyond me skill level).

The only worry I have for this technique is exception safety. There are no problems with this simplified version but I can quite convince myself this is true for your more complex cache. I would need to write the unit tests to make myself convinced.

#include <map>

class simple_cache
{
        // The node(s) used to maintain the circular list.
        struct Link
        {
            // Links are created into a list.
            Link(Link* n, Link* p)
                : next(n)
                , prev(p)
            {}

            // Remove a `this` from the list.
            void unlink()
            {
                // Unlink this from the chain
                prev->next      = next;
                next->prev      = prev;
            }

            // Move a link to `head` of the list.
            // But we do need to pass the head of the list.
            void move(Link& head)
            {
                unlink();

                // Put this node back into the chain at the head node
                this->next      = &head;
                this->prev      = head.prev;

                head.prev->next = this;
                head.prev       = this;
            }

            Link*    next;
            Link*    prev;
        };
        // A cache_entry is a link
        // So we can add it to the circular list.
        struct cache_entry: public Link
        {
            // Create a link AND add it to the head of the list.
            cache_entry(int key, int value, Link& head)
                : Link(&head, head.prev)
                , key(key)
                , value(value)
            {
                head.prev->next = this;
                head.prev       = this;
            }

            int         key;
            int         value;
        };
        typedef std::map<int, cache_entry>      Data;
        Link    head;   // Circular linked list
                        // If there are zero elements it points at itself
        Data    data;
    public:
        simple_cache() 
          : head(&head, &head)
        {}

        void add(int key, int value)
        {
            Data::iterator  find    = data.find(key);
            if (find != data.end())
            {
                find->second.value  = value;
                find->second.move(head);
            }
            else
            {
                data.insert(std::make_pair(key,cache_entry(key, value,head)));
                if (data.size() > 5)
                {
                    evict();
                }
            }
        }
    private:
        void evict()
        {
            /* This function will explode if called when the list is empty
             * i.e. if the only link in the chain is the fake node.
             * Thus it is important to make sure that you only call this
             * when their is a real node in the list.
             *
             * Maybe a check and exception may be worth it (though if done 
             * correctly it should be possible to make sure it does not happen)
             */


            // Get and remove the last element from the list
            Link*   lastElement = head.prev;
            lastElement->unlink();

            // Now remove it from the map.
            data.erase(static_cast<cache_entry*>(lastElement)->key);
        }

};
\$\endgroup\$
  • \$\begingroup\$ I think you have a good point about the encapsulation. Even though that API is completely private, it should have a place of its own. :) I'll have to give some more thought about the other stuff you mentioned :) \$\endgroup\$ – R. Martinho Fernandes Sep 14 '11 at 8:49
  • \$\begingroup\$ I think that making a circular list with a sentinel would require one of: 1) require DefaultConstructible keys; 2) keep an extra pointer to the key per node. Note that I need to access the key from the back of the list to erase it from the map. I can't think of a way to avoid this :( \$\endgroup\$ – R. Martinho Fernandes Sep 14 '11 at 9:31
  • \$\begingroup\$ Oh silly me, I didn't notice/think of just using a downcast since I know it's safe here! \$\endgroup\$ – R. Martinho Fernandes Sep 14 '11 at 11:23

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.