一种MRU缓冲换出机制的实现

一、问题起因

Nu-Link调试器实现了flash断点和硬件断点。

其中, 设定硬件断点速度很快，但只能设定最多4个；设定flash断点速度比硬件断点稍慢一点，个数不受限制；

由此，我们希望应用MRU缓冲换出机制（Most Recently Used），

让最近经常使用的断点，优先使用硬件断点实现。

如果某些断点已经用flash断点实现，也可以动态的调整，切换到硬件断点。

这样用户在调试软件时，将最大限度的在硬件断点上工作，加快调试速度。

例如，用户程序如下，调试时在每一行赋值处设定断点。初始时，断点分布情况如下：

//volatile int v;

int main()

{

    v = 0; //断点1位置，硬件断点

    v = 1; //断点2位置，硬件断点

    v = 2; //断点3位置，硬件断点

    v = 3; //断点4位置，硬件断点

    v = 4; //断点5位置，flash断点

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点6位置，flash断点

        v = 6; //断点7位置，flash断点

        v = 8; //断点8位置，flash断点

        v = 5; //断点9位置，flash断点

        v = 5; //断点10位置，flash断点

        v = 5; //断点11位置，flash断点

    }

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点12位置，flash断点

        v = 5; //断点13位置，flash断点

        v = 6; //断点14位置，flash断点

        v = 8; //断点15位置，flash断点

    }

}

在程序调试进第一个for循环时，我们希望断点能自动调整，

让大多数硬件断点在第一个for循环中：

int main()

{

    v = 0; //断点1位置，flash断点

    v = 1; //断点2位置，flash断点

    v = 2; //断点3位置，flash断点

    v = 3; //断点4位置，flash断点

    v = 4; //断点5位置，flash断点

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点6位置，硬件断点

        v = 6; //断点7位置，硬件断点

        v = 8; //断点8位置，硬件断点

        v = 5; //断点9位置，硬件断点

        v = 5; //断点10位置，flash断点

        v = 5; //断点11位置，flash断点

    }

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点12位置，flash断点

        v = 5; //断点13位置，flash断点

        v = 6; //断点14位置，flash断点

        v = 8; //断点15位置，flash断点

    }

}

在程序调试进第二个for循环时，同样的，我们希望断点能自动调整，

让大多数硬件断点在第二个for循环中：

int main()

{

    v = 0; //断点1位置，flash断点

    v = 1; //断点2位置，flash断点

    v = 2; //断点3位置，flash断点

    v = 3; //断点4位置，flash断点

    v = 4; //断点5位置，flash断点

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点6位置，flash断点

        v = 6; //断点7位置，flash断点

        v = 8; //断点8位置，flash断点

        v = 5; //断点9位置，flash断点

        v = 5; //断点10位置，flash断点

        v = 5; //断点11位置，flash断点

    }

    for(int i = 0; i < 100; ++i)

    {

        v = 5; //断点12位置，硬件断点

        v = 5; //断点13位置，硬件断点

        v = 6; //断点14位置，硬件断点

        v = 8; //断点15位置，硬件断点

    }

}

二、解决方案

上面例子举的太长了。实际上实现时，我们采用 "MRU最近最常用" 的机制，

对所有断点进行排序，"MRU最近最常用" 的4个断点，就用硬件断点实现。

每次运行到任何一个断点，有个全局的总次数n加1， 

每个断点都有两个n值, 最近一次运行到此断点时的"总次数n值", 记录为m_curr,

和次近一次运行到此断点时的"总次数n值", 记录为m_near。

这样 m_curr - m_near 为两次运行到该断点时，其他断点再这期间被运行的次数，

当前的 n - m_curr 为多久没有运行到这个断点了。

这样 interval = max(m_curr - m_near, n - m_curr) 就是每个断点最近被执行到的频繁度的一个指标。

取interval的值，所有断点按照这个值排序，

再取排序值最小的4个，就找到了 "最近最常用" 的4个断点。

三、程序实现

实现的麻烦在于排序，每增加一个断点进入统计，或者每次运行到一个断点，

都需要重新排序。而作为排序的interval键值，

随着总次数n的值增加，每次每个断点的interval键值可能变化。

如何实现一个高效的排序方案，就成为需要解决的问题。

为此，我们将断点分为两组，第一组满足：

   m_curr - m_near >= n - m_curr

   第一组断点以 m_curr - m_near 作为键值，用std::map进行保存。

第二组满足

   m_curr - m_near < n - m_curr

   第二组断点以m_curr作为键值，用std::map进行保存。不管n如何增加，

根据m_curr的值做出的排序不会改变，事实上也就对 n - m_curr 进行了排序。

由于使用std::map, 两组数据都是动态有序的，

这样任何时候都可以从两组std::map中，直接取出interval值最小的4个断点。

某个断点被运行到时或者增加新的断点时，重新将该断点放到第一组std::map中。

某个断点被运行到时，总次数n自增1， 导致某些断点要从第一组上移动到第二组上。

决定移动的条件是 m_curr - m_near < n - m_curr, 也就是 2*m_curr - m_near，

为了加速这个移动动作，用 2*m_curr - m_near 作为键值，再维护另一个std::map对象，

这样直接用n值，很快就能查找到哪些断点需要移动到第二组std::map.

以上操作均为map对象的插入/删除。假设总共断点数为N, 总体估算，每运行到一个断点，更新这些断点的时间复杂度在O(log N)的数量级。

所有断点都被执行到一遍，总时间复杂度为O(N * log N)的数量级。

最后将附上实现的模板类代码，PosSwap中的函数InsertMember用于插入一个新的成员，

SelectMember用于取出最近最频繁的成员。

由于用模板类实现，也可很方便的用在除断点外的其他类型。

作为对比，另外用vector排序的办法做了另一个实现PosSwap_vector, 这个复杂度应该在 O(N * N * log N)

最后一对比x-hawk就胸闷了，在20断点数以下，map实现的MRU程序，比vector实现更慢呢！

到50个以上，vector的差距就很明显了。但是。。。怎么会有人用到50个以上的断点呢。。。

/*

   MIT License

   Copyright (c) 2010 X-Hawk cublog: http://file.chinaunix.com

 */

#include 

#include 

#include 

#include 

#include 

#include 

template<class T>

class PosSwap_vector

{

protected:

    struct AccessIndex

    {

        unsigned int    m_prev;

        unsigned int    m_curr;

        unsigned int    m_next;

        T               m_member;

        AccessIndex(unsigned int prev, unsigned int curr, unsigned int next, T member)

            : m_prev(prev)

            , m_curr(curr)

            , m_next(next)

            , m_member(member)

        {

        }

        AccessIndex &operator=(const AccessIndex &right)

        {

            AccessIndex(right).swap(*this);

            return *this;

        }

        void swap(AccessIndex &right)

        {

            std::swap(m_prev, right.m_prev);

            std::swap(m_curr, right.m_curr);

            std::swap(m_next, right.m_next);

            std::swap(m_member, right.m_member);

        }

        inline unsigned int GetAccessFreq(unsigned int globalIndex) const

        {

            unsigned long freq0 = m_curr - m_prev;

            unsigned long freq1 = globalIndex - m_curr;

            return (freq0 > freq1 ? freq0 : freq1);

        }

    };

    std::vector<AccessIndex>    m_members;

    unsigned int                m_globalIndex;

    class Comp:

        public std::binary_function<const AccessIndex &, const AccessIndex &, bool>

    {

    protected:

        unsigned int m_globalIndex;

    public:

        Comp(unsigned int globalIndex)

            : m_globalIndex(globalIndex)

        {

        }

        bool operator()(const AccessIndex &l, const AccessIndex &r) const

        {

            unsigned int freq0 = l.GetAccessFreq(m_globalIndex);

            unsigned int freq1 = r.GetAccessFreq(m_globalIndex);

            if(freq0 == freq1)

                return l.m_member < r.m_member;

            else

                return freq0 < freq1;

        }

    };

public:

    void SelectMember(std::vector<T> &members, size_t n) const

    {

        members.clear();

        size_t i = 0;

        typename std::vector<AccessIndex>::const_iterator itr = m_members.begin();

        while(i < n && itr != m_members.end())

        {

            members.push_back(itr->m_member);

            ++i;

            ++itr;

        }

    }

    void InsertMember(const T &member)

    {

        AccessIndex insert(0, 0, 0, member);

        for(typename std::vector<AccessIndex>::iterator i = m_members.begin();

            i != m_members.end();

            ++i)

        {

            if(i->m_member == member)

            {

                insert = *i;

                m_members.erase(i);

                break;

            }

        }

        ++m_globalIndex;

        if(m_globalIndex == 0)

        {

            m_members.clear();

            return;

        }

        insert.m_prev = insert.m_curr;

        insert.m_curr = m_globalIndex;

        insert.m_next = insert.m_curr * 2 - insert.m_prev;

        m_members.push_back(insert);

        std::sort(m_members.begin(), m_members.end(), Comp(m_globalIndex));

    }

    PosSwap_vector()

        : m_members()

        , m_globalIndex(0)

    {

    }

    virtual ~PosSwap_vector()

    {

    }

};

template<class T>

class PosSwap

{

protected:

    struct AccessIndex

    {

        unsigned int    m_prev;

        unsigned int    m_curr;

        unsigned int    m_next;

        const T         *m_member;

        AccessIndex(unsigned int prev, unsigned int curr, unsigned int next, T *member)

            : m_prev(prev)

            , m_curr(curr)

            , m_next(next)

            , m_member(member)

        {

        }

        inline unsigned int GetAccessFreq(unsigned int globalIndex) const

        {

            unsigned long freq0 = m_curr - m_prev;

            unsigned long freq1 = globalIndex - m_curr;

            return (freq0 > freq1 ? freq0 : freq1);

        }

        static bool CompNear0(const AccessIndex &l, const AccessIndex &r)

        {

            unsigned int freq0 = l.m_curr - l.m_prev;

            unsigned int freq1 = r.m_curr - r.m_prev;

            if(freq0 == freq1)

            {

                //return l.m_curr < r.m_curr;

                return *l.m_member < *r.m_member;

            }

            else

                return freq0 < freq1;

        }

        static bool CompNear1(const AccessIndex &l, const AccessIndex &r)

        {

            if(l.m_next == r.m_next)

                return l.m_curr < r.m_curr;

            else

                return l.m_next < r.m_next;

        }

        static bool CompFar(const AccessIndex &l, const AccessIndex &r)

        {

            return l.m_curr < r.m_curr;

        }

    };

    typedef bool (*CompFunc)(const AccessIndex &, const AccessIndex &);

    typedef std::map<T, AccessIndex>                MemberType;

    MemberType                                      m_allMembers;

    /* For the members with m_next >= current index, put member's iterator in m_nearMembers0,

       the 1st argument of map is "m_curr - m_prev" */

    std::map<AccessIndex, typename MemberType::iterator, CompFunc>  m_nearMembers0;

    /* For the members with m_next >= current index, put member's iterator in m_nearMembers1,

       the 1st argument of map is "m_next" */

    std::map<AccessIndex, typename MemberType::iterator, CompFunc>  m_nearMembers1;

    /* For the members with m_next < current index, put member's iterator in m_farMembers,

       the 1st argument of map is "m_curr" */

    std::map<AccessIndex, typename MemberType::iterator, CompFunc>  m_farMembers;

    unsigned int                                    m_globalIndex;

public:

    PosSwap()

        : m_allMembers()

        , m_nearMembers0(&AccessIndex::CompNear0)

        , m_nearMembers1(&AccessIndex::CompNear1)

        , m_farMembers(&AccessIndex::CompFar)

        , m_globalIndex(0)

    {

    }

    void SelectMember(std::vector<T> &members, size_t n) const

    {

        members.clear();

        typename std::map<AccessIndex,  typename MemberType::iterator, CompFunc>::const_reverse_iterator ifar

            = m_farMembers.rbegin();

        typename std::map<AccessIndex,  typename MemberType::iterator, CompFunc>::const_iterator inear

            = m_nearMembers0.begin();

        size_t i = 0;

        for(; i < n; ++i)

        {

            if(ifar != m_farMembers.rend() && inear != m_nearMembers0.end())

            {

                unsigned int freqFar = m_globalIndex - ifar->first.m_curr;

                unsigned int freqNear = inear->first.m_curr - inear->first.m_prev;

                if(freqFar < freqNear)

                {

                    members.push_back(ifar->second->first);

                    ++ifar;

                }

                else if(freqFar > freqNear)

                {

                    members.push_back(inear->second->first);

                    ++inear;

                }

                else if(ifar->second->first < inear->second->first)

                {

                    members.push_back(ifar->second->first);

                    ++ifar;

                }

                else

                {

                    members.push_back(inear->second->first);

                    ++inear;

                }

            }

            else if(ifar != m_farMembers.rend())

            {

                members.push_back(ifar->second->first);

                ++ifar;

            }

            else if(inear != m_nearMembers0.end())

            {

                members.push_back(inear->second->first);

                ++inear;

            }

            else

                break;

        }

    }

    unsigned int GetMemberFrequency(const T &member) const

    {

        typename MemberType::const_iterator itr = m_allMembers.find(member);

        if(itr != m_allMembers.end())

        {

            return itr->second.GetAccessFreq(m_globalIndex);

        }

        else

            return 0;

    }

    void InsertMember(const T &member)

    {

        AccessIndex index(0, 0, 0, NULL);

        /* Check if member exists */

        typename MemberType::iterator itr = m_allMembers.find(member);

        if(itr != m_allMembers.end())

        {

            index = itr->second;

            if(m_globalIndex <= itr->second.m_next)

            {

                m_nearMembers0.erase(itr->second);

                m_nearMembers1.erase(itr->second);

            }

            else

                m_farMembers.erase(itr->second);

            m_allMembers.erase(itr);

        }

        /* Move from m_nearMembers0 & m_nearMembers1 to m_farMembers. */

        AccessIndex end(0, 0, m_globalIndex, NULL);

        typename std::map<AccessIndex,  typename MemberType::iterator, CompFunc>::iterator pos

            (m_nearMembers1.lower_bound(end));

        while(pos != m_nearMembers1.end())

        {

            typename std::map<AccessIndex, typename MemberType::iterator, CompFunc>::iterator move = pos;

            ++pos;

            if(move->first.m_next == m_globalIndex)

            {

                m_farMembers.insert(*move);

                m_nearMembers0.erase(move->first);

                m_nearMembers1.erase(move);

            }

            else

                break;

        }

        /* Increase m_globalIndex */

        ++m_globalIndex;

        if(m_globalIndex == 0)

        {

            /* Overflow, clear all records, start new statistics */

            m_allMembers.clear();

            m_nearMembers0.clear();

            m_nearMembers1.clear();

            m_farMembers.clear();

            return;

        }

        /* Insert the member */

        index.m_prev = index.m_curr;

        index.m_curr = m_globalIndex;

        index.m_next = index.m_curr * 2 - index.m_prev;

        itr = m_allMembers.insert(std::make_pair(member, index)).first;

        itr->second.m_member = &itr->first;

        /* m_globalIndex - index.m_next

            = index.m_curr - (index.m_curr * 2 - index.m_prev)

            = index.m_prev - index.m_curr <= 0 */

        m_nearMembers0.insert(std::make_pair(itr->second, itr));

        m_nearMembers1.insert(std::make_pair(itr->second, itr));

    }

    virtual ~PosSwap()

    {

    }

};

template<class SWAP>

void test_time(SWAP &ps0)

{

#define MAX_NUM     150

#define SELECT_NUM  4

#define LOOP_TIME   3000

    time_t start = time(0);

    srand(time(0));

    for(int j = 0; j < LOOP_TIME; ++j)

    {

        for(int i = 0; i < MAX_NUM; ++i)

        {

            /* Insert a random value */

            int r = rand() % MAX_NUM;

            ps0.InsertMember(r);

            /* Select the most recent value */

            std::vector<unsigned int> members0;

            ps0.SelectMember(members0, SELECT_NUM);

        }

    }

    printf("time = %d\n", (int)(time(0) - start));

}

int main()

{

    PosSwap<unsigned int>   ps0;

    test_time(ps0);

    PosSwap_vector<unsigned int>    ps1;

    test_time(ps1);

    return 0;

}

/* End */