LRU Cache的C++实现

Posted on |

Cache是提升程序性能的利器，在程序设计中可以说无处不在。而大多数情况下，我们使用最简单LRU算法即可满足需求，利用C++标准库或者boost库短短的几十行代码即可设计出一个通用的LRU Cache。

为了保证访问性能，对于标准库我们可以使用std::map来保存需要缓存的Key和Value。LRU算法是指当Cache满的时候，需要淘汰掉最早访问过的那个Key，以便插入新的Key和Value。直观看起来，我们似乎需要另外一个数据结构来保存Cache里每个Key访问的时间，但实际上我们只要维持Cache里Key的访问顺序即可，并无需保存具体时间戳，所以我们可以利用std::list这个数据结构。因此，基本的容器定义如下：

typedef std::list<K> key_tracker_type;
typedef std::map<
    K, std::pair<V,typename key_tracker_type::iterator>
  > key_to_value_type;

在每个map的元素里保存了指向list的迭代器；当访问新Key时，直接在list末尾插入该Key，同时把该迭代器保存在map中；如果该Key已经在Cache中存在，则先从map里找到迭代器，然后把迭代器指向位置的Key元素挪到list的末尾；这样list越靠近开头的元素越老，越靠近末尾的元素越新，当Cache满后需要淘汰旧元素时，从list取到最老的Key，然后在map里删除即可。这就是大概的算法流程，具体代码实现如下：

#ifndef _lru_cache_using_std_
#define _lru_cache_using_std_

#include <cassert>
#include <map>
#include <list>

template <typename K, typename V>
class lru_cache_using_std
{
public:
    typedef K key_type;
    typedef V value_type;

    // 保存访问历史顺序，越老的数据约靠末尾
    typedef std::list<key_type> key_tracker_type;

    // 保存Key/Value数据，以及指向访问历史顺序的迭代器
    typedef std::map<
        key_type,
        std::pair<value_type, typename key_tracker_type::iterator>
        > key_to_value_type;

    lru_cache_using_std(value_type (*f)(const key_type&), size_t c)
        : fn_(f), capacity_(c)
    {
        assert(capacity_!=0);
    }

    // 对外提供的唯一访问接口
    value_type operator()(const key_type& k)
    {
        const typename key_to_value_type::iterator it = key_to_value_.find(k);

        if (it == key_to_value_.end()) {
            // 如果Key/Value尚不存在，则根据Key获取Value，并存入Cache后返回
            const value_type v=fn_(k);
            insert(k,v);
            return v;
        } else {
            // 如果Key/Value已经存在，调整list顺序后访问
            key_tracker_.splice(key_tracker_.end(),
                                key_tracker_,
                                (*it).second.second);
            return (*it).second.first;
        }
    }

private:
    // 插入新数据
    void insert(const key_type& k,const value_type& v)
    {
        assert(key_to_value_.find(k)==key_to_value_.end());

        // 当Cache满后，淘汰老数据
        if (key_to_value_.size() == capacity_) evict();

        typename key_tracker_type::iterator it
            = key_tracker_.insert(key_tracker_.end(), k);

        key_to_value_.insert(std::make_pair(k,
                std::make_pair(v,it)));
    }

    // 淘汰老数据
    void evict()
    {
        assert(!key_tracker_.empty());

        // list开头元素是最老的数据
        const typename key_to_value_type::iterator it
            = key_to_value_.find(key_tracker_.front());

        assert(it!=key_to_value_.end());

        // 同时在map和list中删除
        key_to_value_.erase(it);
        key_tracker_.pop_front();
    }

    // 当Cache未命中时，由Key获取Value的函数。通常会访问一个更慢速的资源来获取Value值，比如网络或磁盘。
    value_type (*fn_)(const key_type&);

    size_t capacity_;

    key_tracker_type key_tracker_;
    key_to_value_type key_to_value_;
};

#endif

测试用例如下：

#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE lru_test

#include <iostream>
#include <string>

#include <boost/test/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
#include <boost/mpl/list.hpp>

#include "lru_cache_using_std.h"

namespace {size_t count_evaluations=0;}

// Dummy function we want to cache
std::string fn(const std::string& s)
{
    ++count_evaluations;
    std::string r;
    std::copy(s.rbegin(),s.rend(),std::back_inserter(r));
    return r;
}

typedef lru_cache_using_std<std::string,std::string> dummy_type;

typedef boost::mpl::list<dummy_type> test_types;

BOOST_AUTO_TEST_CASE_TEMPLATE
(
 lru_test,
 CACHE,
 test_types
 )
{
    count_evaluations=0;

    CACHE lru(fn,5);

    // Some initial accesses to prime state
    BOOST_CHECK_EQUAL(lru("first"),"tsrif");
    BOOST_CHECK_EQUAL(lru("second"),"dnoces");
    BOOST_CHECK_EQUAL(lru("third"),"driht");
    BOOST_CHECK_EQUAL(lru("fourth"),"htruof");
    BOOST_CHECK_EQUAL(lru("fifth"),"htfif");
    BOOST_CHECK_EQUAL(count_evaluations,5);
    BOOST_CHECK_EQUAL(lru("sixth"),"htxis");
    BOOST_CHECK_EQUAL(count_evaluations,6);

    // This should be retrieved from cache
    BOOST_CHECK_EQUAL(lru("second"),"dnoces");
    BOOST_CHECK_EQUAL(count_evaluations,6);

    // This will have been evicted
    BOOST_CHECK_EQUAL(lru("first"),"tsrif");
    BOOST_CHECK_EQUAL(count_evaluations,7);

    // So check fourth is retrieved
    BOOST_CHECK_EQUAL(lru("fourth"),"htruof");
    BOOST_CHECK_EQUAL(count_evaluations,7);

    // That will have moved up "fourth" to the head
    // so this will evict fifth
    BOOST_CHECK_EQUAL(lru("seventh"),"htneves");
    BOOST_CHECK_EQUAL(count_evaluations,8);

    // Check fifth was evicted as expected
    BOOST_CHECK_EQUAL(lru("fifth"),"htfif");
    BOOST_CHECK_EQUAL(count_evaluations,9);
}

编译：

$ g++ -o lru_test lru_test.cpp -lboost_unit_test_framework-mt

此外，也可以使用boost::unordered_map替代std::map，对于Key是int等整型数据来说会有很大的性能提升，具体可以参考文末链接。其中还介绍了基于boost::bimap的实现方法，无需增加额外的数据结构。

由于直接使用的C++容器，所以该实现并非线程安全的，如果要在多线程环境中使用，考虑在共享资源处添加boost::unique_lock和boost::shared_lock等锁机制。

参考