SuperCache 模拟Intel CPU内部Cache实现的一个Cache

[Linker M Lin]

在CPU内部有一个关联存储器,CAM,可以通过Tag在一定的行数中快速找到tag匹配的行.
通过这个硬件机构并辅以SRAM,CPU可以实现CACHE.
我的这个SuperCache,通过一个完全Hash表(65536项的数组)来模拟CAM,效率上也是O(1)的.在实际的CPU中,为了提高命中
率,CPU的CACHE实际上并行使用多个CAM来实现CACHE.比如:
现在的酷睿2,按照不同的等级就有1MB 2MB 4MB L2CACHE
分别用 4路 8路 和 16路的CAM来实现.
之所以这样设计,也是为了方便封装时区分产品等级.
在这里,用的是数组的[CachePageNum]维度.因为没有CAM可以用,用的是轮训,但是轮训并不一定低效.在轮训涉及的数据在
L2CACHE
的同一个行内的时候,只有一个内存读操作,实际的效率在跳来跳去的链表之上(尤其对长流水的奔四来说更是如此),细节可以参考MSDN.
现在一般CPU的L2CACHE的行长不超过 64字节,也就是说,我的SuperCache维度不超过16维的时候(指针为4字节的时候),每次遍
历
查找的数据只需要从内存中读取一次.这是非常高效的.

感谢您的阅读!

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

class CacheObj;
class CacheObj
{
public:
CacheObj(unsigned long long UID)
{
_uid=UID;

}

static unsigned short Hahto16(unsigned long long UID)
{
return UID%65537;

}

unsigned long long Key()
{
return _uid;

}

int Purge()
{
return 0;

}

static CacheObj* LoadObj(unsigned long long UID)
{
// 假设可以非阻塞的快速取得对象,或者可以在这里阻塞
return (new CacheObj(UID));

}

unsigned long ong _uid;

};

template<typename CacheObjType,typename KeyType,unsigned int
CachePageNum=4 /*四路最经济*/>
class SuperCache
{
public:
SuperCache()
{
memset(this,0,sizeof(SuperCache));

}

CacheObjType* Get(const KeyType& key)
{
unsigned short index= CacheObjType::Hashto16(key);
for(unsigned int i=0;i<CachePageNum;i++)
{
if(_cache[index][i])
{
_hited++;
return _cache[index][i];

}

else
break;

}

_missed++;
unsigned int randPage=rand()%CachePageNum;
if(_cache[index][randPage])
{
_collision++;
_cache[index][randPage]->pUrge();
_cache[index][randPage]=NULL;

}

else
{
_new++;

}

_cache[index][randPage]=CacheObjType::LoadObj(key);
return _cache[index][randPage];

}

void Report()
{
double total=(_hited+_missed-_new)+0.00000001;
printf(hited:total = %lf \n",double(_hited/total));

}

CacheObjType* _cache[65536][CachePageNum];
unsigned int _hited;
unsigned int _missed;
unsigned int _collision;
unsigned int _new;

};

int main(int argc,char* argv[])
{
SuperCache< CacheObj, unsigned long long, 4> &cache=*(new
SuperCacheSuperCache< CacheObj, unsigned long long, 4 >());
std::list<CacheObj*> &objList=*(new std::list<CacheObj*>());
for(int i=0;i<10*1000*1000;i++)
{
static unsigned long long key;
key+=rand();
key%=(1*1000*1001+17);// 假设一百万用户进行一千万次登录,登陆一次读取两次数据,时间间隔100个用户,命中率在65%
左
右
objList.push_back(cache.Get(key));
if(objList.size()>100)
{
cache.Get(objList.front()->Key())->Key();
objList.pop_front();

}
}

cache.Report();
return 0;
}

[red...@gmail.com]

之前做过的一个项目, 要尽量快速判断某个 ip 地址上有没有定义特殊的标志, 用
的 hash 比你这个还大, 是这样的

byte mask[256*256*256];
占 16M ram, 查出来一个 byte, 其中每个 bit 表示相邻的 32个 ip(降低精度以
求速度).

其实也就是先降低精度, 然后一一对应, 等于直接用index对应过去.

当时想着, 如果有个 8M~32M 的 TCAM 存储芯片就好了, 不必降低精度, 直接让它
做关联查找, 又快又准, 软件怎么也比不上.

Linker M Lin 写道:

[top]

SuperCache< CacheObj, unsigned long long, 4> &cache=*(new
SuperCacheSuperCache< CacheObj, unsigned long long, 4 >());

这里有错误，兄台该做个typedef，放置把大家包括自己都搞晕。