CPU Branch Prediction 的成本...

在公司搞定一個速度最佳化的問題,想到之前在 Stack Overflow 上有看到 CPU branch prediction 的問題 (跟我解的問題應該沒關係,只是剛好想到),把文章找出來...

出自 Stack Overflow 上有人詢問某段 C++ 程式為什麼加上 sort 後快多了:「Why is processing a sorted array faster than an unsorted array?」。

發文者的範例程式已經簡化到很容易理解:先產生一個 32Kytes 的 array,然後裡面塞亂數。

接下來把每個 byte 當作 unsigned char,要找出這個 array 裡面所有值大於等於 128 的元素,把這些元素的值加起來。

原發文者發現,如果先把這個 array 排過再計算,十萬次只要 1.93 秒,但如果不排就直接計算需要 11.54 秒,時間差不多是原來的六倍。

回答的人答的相當詳細,還給了一個 branchless 的 hack 來解這個問題 (於是就不需要先 sort),很值得一看。