Почему моя таблица транспонирования такая медленная?(4-кратное замедление) - PullRequest
Новая
       22

Почему моя таблица транспонирования такая медленная?(4-кратное замедление)

0 голосов
/ 01 декабря 2018

Поэтому я использую таблицу транспозиции (TT), чтобы попытаться ускорить алгоритм минимаксного алфавита для некоторой настольной игры.Но к моему удивлению, когда я выключаю таблицу транспонирования, я получаю ускорение в 4 раза!Таблицы транспонирования должны ускорять процесс, верно?

Итак, я заметил одну вещь: только в 10% случаев я получаю попадание в кэш.Не самое большое, но мне не нужно 75% для того, чтобы ТТ был полезным.

Итак, идея в том, что ТТ - это очень быстрый поиск в кэше.Я использую схему замены 2Big.TT хранит нижние и верхние границы, глубину поиска, перемещение и количество усилий (размер), необходимых для вычисления наилучшего ответа.LockEntry это просто псевдоним для unsigned long long.

Мой код приведен ниже: 

ctypedef struct CacheEntry:
    LockEntry lock
    minimax_score lower_bound
    minimax_score upper_bound
    int depth
    Move move
    long long size

ctypedef struct BigEntry:
    CacheEntry small
    CacheEntry large  

cdef void set_entry(CacheEntry entry):
    """set an entry into the cache"""
    global cache
    cdef int key
    key = entry.lock % PRIME
    if entry.size > cache[key].large.size or entry.lock == cache[key].large.lock:
        cache[key].large = entry
    else:
        cache[key].small = entry
    return

cdef int get_entry(CacheEntry *entry, LockEntry lock):
    """retrieve an entry from cache"""
    global cache
    global cache_queries
    global large_hits
    global small_hits
    cdef int key
    cache_queries += 1
    key = lock % PRIME
    if cache[key].large.lock == lock:
        large_hits += 1
        entry[0] = cache[key].large
        return 1 #success
    elif cache[key].small.lock == lock:
        small_hits += 1
        entry[0] = cache[key].small
        return 1 #success
    return 0 #failure

Функция set_entry принимает тип struct CacheEntry и помещает его в TT (не созидательно)называется cache), в то время как функция get_entry берет указатель на CacheEntry и обновляет его значение (я пытался вернуть CacheEntry, но разницы в скорости не возникает.).Он также возвращает 1 для успешного попадания в кэш и 0 для неудачного.

Так что, в принципе, у меня нет идей о том, как правильно его использовать.Я удивлен, что это медленно, и когда скомпилировано с -a, это все white, поэтому кажется, что я правильно пишу код.

Помощь оценена.

...