Избиение бинарного поиска с использованием строки кэша ЦП

Question

Для образовательных целей я пытаюсь победить binary search с использованием строки кэша ЦП.

https://github.com/nmmmnu/beating_binsearch/blob/master/improved.h

Если вы раскомментировать #define EXIT_ONLY, поиск работает как обычный binary search, за исключением, если есть несколько элементов, поиск стал linear search.

Как и ожидалось, это выполняет быстрее, чем binary search.

Однако я хочу улучшить будущее, поэтому, если вы прокомментируете #define EXIT_ONLY, то вместо небольшого элемента «средний» будет создан «маленький» linear search.

Теоретически значения для линейного поиска должны быть в строке кэша ЦП, и доступ должен быть «бесплатным».

Однако на практике этот поиск слишком медленный, чем обычный binary search.

Если I hardcode CACHE_COUNT_2 будет равен 1, то скорость сравнима, но все же медленнее.

Примечание. Я никогда не пытался развернуть цикл for в _linear().

Что может быть объяснением более медленного выполнения?

Repo со всеми файлами здесь:
https://github.com/nmmmnu/beating_binsearch

Answer 1

Я раскатал версию поиска,

https://github.com/nmmmnu/beating_binsearch/blob/master/improved_unroll.h

здесь код в вопросе:

char search(uint64_t const start1, uint64_t const end1, const T *data, const T key, uint64_t &index) const{ 
    /* 
    * Lazy based from Linux kernel... 
    * http://lxr.free-electrons.com/source/lib/bsearch.c 
    */ 

    uint64_t start = start1; 
    uint64_t end = end1; 

    char cmp = 0; 

    //while (start < end){ 
    while (start < end){ 
    // uint64_t mid = start + ((end - start)/2); 
     uint64_t mid = start + ((end - start) >> 1); 

     //char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid); 

     #define _LINE_HALF_SIZE 7 
     #define _LINE(i)      \ 
     if (i >= end){       \ 
      start = mid + _LINE_HALF_SIZE + 1; \ 
      continue;       \ 
     }          \ 
               \ 
     cmp = comp.cmp(data[i], key);   \ 
               \ 
     if (cmp == 0){       \ 
      index = i;       \ 
      return 0;       \ 
     }          \ 
               \ 
     if (cmp > 0){       \ 
      end = i + 1;      \ 
      continue;       \ 
     } 

     _LINE(mid - 7); 
     _LINE(mid - 6); 
     _LINE(mid - 5); 
     _LINE(mid - 4); 
     _LINE(mid - 3); 
     _LINE(mid - 2); 
     _LINE(mid - 1); 
     _LINE(mid ); 
     _LINE(mid + 1); 
     _LINE(mid + 2); 
     _LINE(mid + 3); 
     _LINE(mid + 4); 
     _LINE(mid + 5); 
     _LINE(mid + 6); 
     _LINE(mid + 7); 

     #undef _LINE 

     start = mid + _LINE_HALF_SIZE + 1; 
    } 

    index = start; 
    return cmp; 
} 

Кажется там слишком много предсказаний промаха ветви, потому что если я удалю следующий if заявление:

 if (i >= end){       \ 
      start = mid + _LINE_HALF_SIZE + 1; \ 
      continue;       \ 
     }          \ 

скорость «магически» стал таким же или даже лучше, чем classical binary search - конечно, потому что я устранил ветвь алгоритм действительно не работал правильно, но это ясно указывает, почему алгоритм медленнее, чем classical binary search ,

Answer 2

В коде есть некоторые проблемы. Например, этот код не учитывает границы строки кэша.

while (end - start > CACHE_COUNT_MIN){ 
// uint64_t mid = start + ((end - start)/2); 
uint64_t mid = start + ((end - start) >> 1); 

и т.д ...

char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid); 

строки кэша распределены по адресам модулю размера строки. Таким образом, чтобы отсканировать всю строку кэша, вы хотели бы замаскировать соответствующие биты адреса. Даже если это кеш-хит, вы все равно будете тратить циклы на доступ к линии (тем больше она находится в иерархии).

Двоичный поиск уже является одним из наиболее эффективных алгоритмов кэширования для поиска на основе сравнения, хотя его улучшение с помощью кэширования может быть затруднено. Вы исключаете половину пространства поиска на каждой итерации, которая уже позволяет избежать большинства промахов в кеше, и это линейное пространство, и вы увеличиваете локальность при каждом поиске. Предсказание может даже скрыть некоторые промахи.

Возможно, вы захотите использовать perf для отбора проб событий в вашем коде. Кроме того, чтобы получить представление о том, как иногда используется кеш-память для оптимизации алгоритмов, вы также можете взглянуть на некоторые из существующих знакомых, например hopscotch hashing.