随机内存访问很昂贵？

Question

在优化我的连接四游戏引擎期间,我达到了一个点,在这一点上,进一步的改进只能是最小的,因为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通过分配表来替换new没有速度改进的表.

我怀疑随机访问内存(因为Zobrist Hashing功能)可能很昂贵,但真的那么多？你有改进功能的建议吗？

谢谢!

编辑: BUCKETSIZE值为4.它用作碰撞策略.一个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是正确的,并且缓慢失误的主要原因是缓慢.

Answer 1

您正在制作表条目的副本,如何使用TableEntry&作为类型.对于底部的默认值,静态默认值TableEntry()也可以.我想那是你失去很多时间的地方.

const TableEntry& getTableEntry(unsigned __int64 lock)
{
    int idx = (lock & 0xFFFFF) * BUCKETSIZE;
    for (int i = 0; i < BUCKETSIZE; i++)
    {
        // hopefuly now less than 35% of CPU usage :-)
        const TableEntry& te = mTable[idx + i];
        if (te.height == NOTSET || lock == te.lock)
            return te;
    }
    return DEFAULT_TABLE_ENTRY;
}

Answer 2

关于复制的观点TableEntry是有效的。但是让\xe2\x80\x99s看看这个问题：

\n\n

\n

我怀疑随机访问内存（\xe2\x80\xa6）可能会很昂贵，但真的有那么多吗？

\n

\n\n

总之，是的。

\n\n

使用您大小的数组进行随机内存访问是缓存杀手。它将产生大量缓存未命中，这可能比访问缓存中的内存慢三个数量级。三个数量级 \xe2\x80\x93 是 \xe2\x80\x99 的因数 1000。

\n\n

另一方面，实际上看起来好像您按顺序使用了大量数组元素，即使您使用哈希生成了起点。这违背了缓存未命中理论，除非你的BUCKETSIZE代码很小并且代码经常被lock外部使用不同的值调用。

\n