使用CPU高速緩存行跳動二分搜索

Question

爲了教育目的，我試圖使用CPU高速緩存行擊敗binary search。

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

如果取消註釋#define EXIT_ONLY，搜索就像正常binary search，除非有幾個要素，搜索成爲linear search。

如預期的那樣，這比執行更快。

但是，我想改善未來，所以如果您評論#define EXIT_ONLY，那麼「小」linear search而不是隻訪問「中」元素。

理論上，線性搜索的值必須在CPU高速緩存行中，並且訪問必須是「免費的」。

但是實際上這個搜索過程比正常的binary search要慢得多。

如果我硬編碼CACHE_COUNT_2等於1，那麼速度是可比較的，但仍然比較慢。

注意我從來沒有嘗試在_linear()中展開for循環。

什麼可以解釋執行速度較慢？

回購了所有的文件是在這裏：
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。