Случайный доступ к памяти стоит дорого?

Во время оптимизации моего подключения четырех игровых движков я достиг точки, когда дальнейшие улучшения могут быть минимальными, поскольку большая часть процессорного времени используется инструкцией TableEntry te = mTable [idx + i] в следующем примере кода.

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 и имеет около 4,2 млн. записи (около 64 МБ). Я попытался заменить вектор , разместив в таблице новый без улучшения скорости.

Я подозреваю, что доступ к памяти осуществляется случайным образом (из-за хеширования Зобриста ] функция) может быть дорогостоящим, но неужели так много? У вас есть предложения по улучшению функции?

Спасибо!

Изменить: 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 секунд). Это лучше, но я думаю, что Конрад Рудольф прав, и основная причина, по которой это так медленно, - это промахи кеша.