在优化我的连接四游戏引擎期间,我达到了一个点,其中进一步的改进只能是最小的,因为在下面的代码示例中,指令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是正确的,并且缓慢失误的主要原因是缓慢.
