Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
Requirements revisitedLet's define the operations we want the cache to perform.
DesignWe certainly need a data structure that lets us look up values for keys efficiently. This will be the core cache table. We can use the C++ standard map container for this purpose - it provides logarithmic lookup and insertion (O(log N) where N is the cache size). But how do we implement LRU removal? We can keep some count of "recent access time stamp" for each key, but how do we know which to throw away? Going over the whole cache to find the LRU key is a O(N) operation - too slow. We solve this using a very common programming trick - we sacrifice space for time. Such problems are usually solved by using another data structure that provides the special requirement quickly and is kept fully coherent with the main data structure. What we need here, for example, is a priority queue - keys sorted in a linear structure with the most recent key in some known location - like the front of the queue, which lets us remove it quickly. This leaves the question of how to implement the queue. We could go for a simple array, but that won't do (can you figure out why?). The problem is that when there's a lookup on some cache key, it immediately becomes the most-recently-used key and should be marked as such, for example by being moved to the back of the queue. This operation is called splicing - take an item from the middle of a container and put it in the end. Splicing in arrays is expensive (O(N)), which is unacceptable. Fortunately, there is a solution - a linked list. In a linked list insertion and removal at both ends is O(1), and so is splicing, given that we already have a pointer/handle to the key we want to splice. But that can be arranged by holding such a pointer in the main cache data structure. So, we'll go for two data structures: a map for the table, and a list (another container in the C++ standard library) for the recent-usage queue. For each key, the table will hold the value and a pointer to the key in the queue, which makes it trivial to mark it as recent on lookups. So, enough babbling, let's get to the code. ImplementationThe source code package provided with this column contains a file named cache.h - this is the implementation of the cache (it is wholly in a .h file because it's templated): template <typename key_type, typename value_type> class cache Our cache can work for any key type and value type, given to it at creation as template arguments. Here is a portion of the cache class that lists its data members:
typedef typename list<key_type>::iterator list_iter;
struct cached_value
{
cached_value(value_type value_, list_iter cache_i_)
: value(value_), cache_i(cache_i_)
{
}
value_type value;
list_iter cache_i;
};
typedef typename map<key_type, cached_value>::iterator table_iter;
unsigned maxsize;
list<key_type> lru_list;
map<key_type, cached_value> table;
maxsize is the maximal size given to the cache at creation. table is the main cache table - for each key, it holds a value and a pointer to the queue. lru_list is the queue - a list sorted by recent use (with the most recently used key in the front). Note that the class also defines a cache_statistics subtype. This is to collect statistics of cache usage. The implementation of statistics is simple enough that I won't mention it in the column. It can be very useful, however, when you plan to use the cache for your needs and want to analyze its performance. Lookup of keys in the cache is done as follows:
value_type* find(const key_type& key)
{
table_iter ti = table.find(key);
IF_DEBUG(stats.finds++);
if (ti == table.end())
return 0;
IF_DEBUG(stats.finds_hit++);
list_iter li = ti->second.cache_i;
lru_list.splice(lru_list.begin(), lru_list, li);
return &(ti->second.value);
}
The key is looked up in the table which has efficient lookups. If the key wasn't found, we simply return 0. If the key was found, we have to splice the accessed key out of its place in the queue and place it in the front - since now this key is the most recently used. Then, we return the value of the key. Insertion is just a little more complex:
void insert(const key_type& key, const value_type& value)
{
value_type* valptr = find(key);
if (valptr)
{
*valptr = value;
}
else
{
lru_list.push_front(key);
cached_value cv(value, lru_list.begin());
table.insert(make_pair(key, cv));
if (lru_list.size() > maxsize)
{
key_type lru_key = lru_list.back();
table.erase(lru_key);
lru_list.pop_back();
IF_DEBUG(stats.removed++);
}
}
}
First we look for the key in the table. Note that the local cache function find() is used here, because if we do find the element we want it marked as MRU. If the key was found, we just update its value and return. More interesting is what happens when the key is not found - here the insertion takes place. After adding the key to the cache, we check to see if the cache size is exceeded. If it is, we throw out the key that's in the back of lru_list which is, if you recall, the LRU key - just what we need! |
|
