提高指令緩存命中率

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

有一個(gè)數(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，并且對(duì)數(shù)組排序。

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

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

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

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

因?yàn)樵?code>for循環(huán)中會(huì)執(zhí)行很多次if分支判斷語句，而CPU擁有分支預(yù)測(cè)器。

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

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

怎么驗(yàn)證指令緩存命中率的情況呢？

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

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

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

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