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

Question

Во время оптимизации моего подключения четырех игровых движков я достиг точки, когда только дальнейшие улучшения могут быть минимальными, поскольку большая часть времени процессора используется инструкцией 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<TableEntry> и имеет около 4,2 мил. записи (около 64 МБ). Я попытался заменить 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 секунд). Лучше, но я думаю, что Конрад Рудольф прав, и главная причина, почему он так медленен, - это кеш пропускает.

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

Насколько велика запись в таблице?Я подозреваю, что это копия, которая стоит дорого, а не поиск памяти.

Доступ к памяти происходит быстрее, если они непрерывны из-за попаданий в кэш, но, похоже, вы делаете это.

Answer 3

Я уже видел эту проблему с хеш-таблицами раньше. Проблема в том, что непрерывный произвольный доступ к хеш-таблице затрагивает всю память, используемую таблицей (как основной массив, так и все элементы). Если он велик по отношению к размеру вашего кеша, вы будете трэшить. Это проявляется как точная проблема, с которой вы сталкиваетесь: эта инструкция, которая сначала ссылается на новую память, кажется очень дорогой из-за остановки памяти.

В случае, над которым я работал, еще одна проблема заключалась в том, что хеш-таблица представляла довольно небольшую часть пространства ключей. Значение «по умолчанию» (аналогично тому, что вы называете DEFAULT_TABLE_ENTRY) применимо к подавляющему большинству ключей, поэтому оно показалось , что хеш-таблица не использовалась интенсивно. Проблема заключалась в том, что хотя записи по умолчанию избегали многих вставок, непрерывное действие поиска снова и снова затрагивало каждый элемент кэша (и в случайном порядке). В этом случае мне удалось переместить значения из хешированных данных в соответствие со связанной структурой. Потребовалось больше общего пространства, потому что даже ключи со значением по умолчанию должны были явно хранить значение по умолчанию, но местность ссылок была значительно улучшена, а прирост производительности огромен.

Answer 4

Пункт о копировании TableEntry действителен. Но давайте посмотрим на этот вопрос:

Я подозреваю, что случайный доступ к памяти (…) может быть дорогим, но неужели так много?

Одним словом, да .

Случайный доступ к памяти с массивом вашего размера является убийцей кэша. Это приведет к большому количеству промахов в кеше, которые могут быть на до трех порядков медленнее, чем доступ к памяти в кеше. Три порядка - это фактор 1000.

С другой стороны, на самом деле все выглядит так, как будто вы используете много элементов массива по порядку, даже если вы сгенерировали свою начальную точку, используя хеш. Это говорит против теории пропуска кэша, если ваш BUCKETSIZE не является крошечным, а код вызывается очень часто с различными значениями lock извне.

Answer 5

Использовать указатели

TableEntry* getTableEntry(unsigned __int64 lock) {
int idx = (lock & 0xFFFFF) * BUCKETSIZE;

TableEntry* max = &mTable[idx + BUCKETSIZE];
for (TableEntry* te = &mTable[idx]; te < max; te++)
{
    if (te->height == NOTSET || lock == te->lock)
        return te;
}
return DEFAULT_TABLE_ENTRY; }