提高指令緩存命中率

前面說的是數據緩存，現在看看指令緩存命中率該如何提高。

有一個數組array，數組元素內容為0-255之間的隨機數：

int array[N];
for (i = 0; i < TESTN; i++) 
 array[i] = rand() % 256;

現在，要把數組中數字小于128的元素置為0，并且對數組排序。

大家應該都能想到，有兩種方法：

• 先遍歷數組，把小于128的元素置為0，然 后排序 。
• 先對數組排序 ， 再遍歷數組 ，把小于128的元素置為0。

for(i = 0; i < N; i++) {
 if (array [i] < 128) 
  array[i] = 0;
}
sort(array, array +N);

先排序后遍歷的速度會比較快，為什么？

因為在for循環中會執行很多次if分支判斷語句，而CPU擁有分支預測器。

如果分支預測器可以預測接下來要執行的分支（執行if還是執行else），那么就可以提前把這些指令放到緩存中，CPU執行的時候就會很快了。

如果一個數組的內容完全隨機的話，那么分支預測器就很難進行正確的預測。但如果數組內容是有序的，它就會根據歷史命中數據的情況對未來進行預測，那命中率就會很高，所以先排序后遍歷的速度會比較快。

怎么驗證指令緩存命中率的情況呢？

在Linux下，可以使用Perf性能分析工具進行驗證。通過-e選項，指定branch-loads和branch-loads-misses事件，可以分別統計出分支預測成功的次數和 分支預測失敗的次數 ，通過L1-icache-load-misses事件也能統計一級緩存中指令未命中的次數。但是，這些性能事件都屬于硬件事件，perf工具能否統計這些事件取決于CPU是否支持以及芯片原廠是否去實現了該接口，我看很多都是不支持或者沒實現的。

另外，在Linux內核中，可以看到大量的likely和unlikely宏，并且它們都出現if語句中，這 兩個宏的作用就是為了提高性能 。

這是顯示預測概率的宏，如果你覺得CPU的分支預測不準，但if中條件為"真"的概率很高，那么你就可以使用likely()括起來，以此提升性能。

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (likely(a == 1)) …