一种MRU缓冲换出机制的实现
时间：2010-07-04 来源：X-Hawk
一、问题起因
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个以上的断点呢。。。
/* End */
相关阅读 更多 +
