提高指令緩存命中率

前面說的是數(shù)據(jù)緩存，現(xiàn)在看看指令緩存命中率該如何提高。

有一個數(shù)組array，數(shù)組元素內(nèi)容為0-255之間的隨機(jī)數(shù)：

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

現(xiàn)在，要把數(shù)組中數(shù)字小于128的元素置為0，并且對數(shù)組排序。

大家應(yīng)該都能想到，有兩種方法：

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

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

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

因為在for循環(huán)中會執(zhí)行很多次if分支判斷語句，而CPU擁有分支預(yù)測器。

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

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

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

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

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

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

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