在优化我的连接四游戏引擎期间,我达到了一个点,其中进一步的改进只能是最小的,因为在下面的代码示例中,指令TableEntry te = mTable [idx i]使用了大部分cpu时间.
TableEntry getTableEntry(unsigned __int64 lock)
{
int idx = (lock & 0xFFFFF) * BUCKETSIZE;
for (int i = 0; i < BUCKETSIZE; i++)
{
TableEntry te = mTable[idx + i]; // bottleneck,about 35% of cpu usage
if (te.height == NOTSET || lock == te.lock)
return te;
}
return TableEntry();
}
哈希表mTable被定义为std :: vector< TableEntry>并且有大约4.2密耳.托管(约64 MB).我试图通过在没有速度改进的情况下分配新表来替换vector.
我怀疑随机访问内存(因为Zobrist Hashing功能)可能很昂贵,但真的那么多？你有改进功能的建议吗？
谢谢！
编辑：BUCKETSIZE的值为4.它用作collision strategy.一个TableEntry的大小是16字节,结构如下所示：
struct TableEntry
{ // Old New
unsigned __int64 lock; // 8 8
enum { VALID,UBOUND,LBOUND }flag; // 4 4
short score; // 4 2
char move; // 4 1
char height; // 4 1
// -------
// 24 16 Bytes
TableEntry() : lock(0LL),flag(VALID),score(0),move(0),height(-127) {}
};
摘要：该功能最初需要39秒.在进行jdehaan建议的更改后,该功能现在需要33秒(程序在100秒后停止).它更好,但我认为Konrad Rudolph是正确的,并且缓慢失误的主要原因是缓慢.
解决方法
关于复制TableEntry的观点是有效的.但是让我们来看看这个问题：
I suspect that accessing the memory randomly (…) could be expensive,but really that much?
@H_404_23@总之,是的.
使用您的大小的数组进行随机内存访问是缓存杀手.它会产生大量缓存未命中,比缓存中的内存访问速度快7000倍.三个数量级 – 这是1000倍.
另一方面,它实际上看起来好像你按顺序使用了很多数组元素,即使你使用哈希生成起点.这反映了缓存未命中理论,除非你的BUCKETSIZE很小并且代码经常使用来自外部的不同锁定值来调用.
