關於無網點二進制搜索

Question

我問了一個關於減少未命中預測的問題。

傑裏棺材給我一個令人印象深刻的答案。

About reducing the branch miss prediciton

二進制搜索網點，但是當我在我的交集算法使用它，我發現它遠遠超過原來的二進制搜索速度較慢。什麼原因？

更新：

我用下面的事件來測試i7處理器的分支預測小姐數量：BR_MISS_PRED_RETIRED。我發現無分支版本比原來的版本差一半左右。

對於高速緩存未命中：我使用LLC_MISSES來測試最後一級高速緩存未命中的數量，也是一半。

但是，時間比原來的時間大約2.5倍。

Answer 1

然後使用您的原始二進制搜索。訪問隨機位置的數組並不比分支未命中好，特別是因爲編譯器不能在這種情況下使用寄存器作爲變量。

Answer 2

因爲該版本正在做大量的加載和存儲。

因爲處理器有多個管道，所以在這樣的緊密循環中進行分支預測通常沒有效果。當分支測試正在被評估時，兩條代碼路徑已經被解碼和評估。只保留一條路徑的結果 - 但分支通常沒有管道延遲。

另一方面寫入內存可能會產生影響。通常情況下，您正在寫入CPU上的內存緩存，但是MMU必須將緩存行保持與系統其餘部分同步。如果陣列很大，並且您以基本上隨機的順序訪問它，緩存未命中並使CPU重新加載內存緩存。

Answer 3

我回過頭來看了一個有趣的方法，可能也是在stackoverflow上，關於避免數據提取成本。有人以這樣的方式編寫了一個二進制搜索，他們將數組視爲一棵隱含的樹並預取了左邊的孩子和右邊的孩子。這是在當前元素與測試值進行比較之前完成的。

增加雙倍的內存需求實際上可以加快搜索速度似乎有着強烈的違反直覺的感覺，但顯然開始提前取得的額外內存命中。

如果我沒有記錯的話，一半的讀數是非有效的，因爲這些值沒有被使用。它可以通過推測性預取加載，非依賴加載或普通加載完成，其中一個獲取的值在循環時移入保存當前元素的寄存器中。