為什么增加一個if(!memcmp())會加快一個在巨大的位元組陣列中隨機短跨度的回圈？

對不起，我從來沒有理解過這里的規則。我已經洗掉了我所發的所有重復的帖子。這是第一個相關的問題。 請不要把這個帖子標記為與我的另一個帖子（將執行次數減少3倍，但執行效率幾乎沒有變化。在C語言中），即使代碼有些相似，它們提出了非常不同的問題。這也是我在同一天發現的兩個問題。一個類似的帖子已經被 "誤判 "重復了，然后被關閉。可能是我沒有弄清楚這個問題。我真的希望能得到答案，所以我重新發了帖子。希望大家都能看清楚這個問題，非常感謝！

在下面的C代碼中，我在第一個測驗時間的回圈中加入了一個 "if "陳述句，執行時間完全相同。從理論上講，它應該更慢。盡管分支預測可以使其性能幾乎相同，但實際上卻變得快了很多。這其中的原理是什么？我嘗試使用clang和gcc編譯器分別在Mac和Linux環境下運行，并嘗試了各種優化級別。為了防止快取受到影響，我讓速度快的先執行，但有冗余代碼的回圈執行得更快。

如果你認為我的描述不可信，請將以下代碼編譯到你的電腦中并運行。希望有人能為我解答這個問題，謝謝。

C代碼：

#include <stdio.h>/span>
#include <time.h>
#include <stdlib.h>
#include <string.h>

#define TLen 300000000
#define SLen 10

int main(int argc, const char * argv[]） {
    srandom((unsigned)time(NULL))。
    
    //一個陣列來增加索引，。
    //其元素的范圍是1-256。
    int rand_arr[128] 。
    for (int i = 0; i < 128;   i)
        rand_arr[i] = random()%256 1。
    
    //一個隨機文本（很長），其元素范圍是0-127。
    char *tex = malloc((sizeof *tex) * TLen) 。
    for (int i = 0; i < TLen;   i)
        tex[i] = random()%128;
    
    //A random string(very short))。
    char *str = malloc((sizeof *str) * SLen) 。
    for (int i = 0; i < SLen;   i)
        str[i] = random()%128。
    
    //第一次測驗。
    clock_t start = clock();
    for (int i = 0; i < TLen; ) {
        if (!memcmp（tex i, str, SLen）) printf("yes!
"）。)
        i  = rand_arr[tex[i]]。
    }
    clock_t end = clock（）。
    printf("No.1: %lf s
", ((double) (end - start)) / clocks_per_sec）。)
    
    //第二個測驗for (int i = 0; i < TLen; ) {
        i  = rand_arr[tex[i]]。
    }
    end = clock()。
    printf("No.2: %lf s
", ((double) (end - start)) / clocks_per_sec）。)
    
    return 0。
}

我已經運行了數百次，幾乎都是這個比例。下面是在Linux中測驗的一個代表性結果：

No.1。0.110000 s
沒有.2。0.140000 s

uj5u.com熱心網友回復：

關鍵的瓶頸是在跨過tex[]時，作為從舊的i到新的i的依賴鏈的一部分，快取錯過的負載使用延遲。 從小的rand_array[]中的查找將在快取中命中，并且只是在回圈攜帶的依賴鏈中增加了大約5個周期的L1d負載使用延遲，這使得除了通過i的延遲之外，其他的東西更不可能與回圈的整體速度有關。

memcmp(tex i, str, SLen)如果tex i接近快取行的末尾，可能會作為預取的行為。 如果你用-O0編譯，你正在呼叫glibc memcmp，所以在glibc memcmp中完成的SSE 16位元組或AVX2 32位元組的加載跨越了快取行的邊界并拉入下一行。 (IIRC, glibc memcmp檢查并避免page crossing, 但不包括cache-line splits, 因為這些在現代CPU上相對便宜。 單步進入它看看。 進入第二次呼叫，以避免懶惰的動態鏈接，或用-fno-plt）編譯。

可能觸及一些會被隨機stride跳過的快取行有助于HW prefetch更加積極，并將其檢測為一個順序訪問模式。 一個 32 位元組的 AVX 負載是半個高速快取行，所以它相當有可能跨越到下一個高速快取行。

因此，L2 快取看到的更可預測的快取線請求序列是 memcmp 版本更快的一個合理解釋。（Intel CPU 將主要預取器放在 L2。

如果你在編譯時進行了優化，那個 10 位元組的 memcmp 行內和內回圈中只接觸到 8 位元組。 (如果它們匹配，那么它將跳轉到另一個塊，在那里它將檢查最后兩個位元組。 但這種情況極不可能發生）。

這可能就是為什么-O0比-O3在我的系統上更快的原因，在i7-6700k Skylake上使用GCC11.1，使用DDR4-2666 DRAM，使用Arch GNU/Linux。 (你的問題沒有說明你的數字來自哪個編譯器和選項，也沒有說明哪個硬體。)

$ gcc -O3 array-stride.c $ taskset -c 3 perf stat --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycle, instructions,uops_issued.any,uops_executed.thread,mem_load_retired.l1_hit,mem_load_retired.l1_miss -r 2 ./a.out 沒有.1。0.041710 s 沒有.2。0.063072 s 沒有.1。0.040457 s 沒有.2。0.061166 s 性能計數器統計 for './a.out' (2 運行)。 1,843.71 msec task-clock # 0. 999 CPU utilized ( - 0.14% ) 0背景關系切換 # 0.000 /秒 0 個 cpu-migrations # 0.000 /秒 73,300 次頁面故障 # 39.757 K/sec ( - 0.00% ) 6,607,078,798周期# 3.584 GHz ( - 0.06% )/span> 18,614,303,386條指令#每周期2.82insn ( - 0.00% )/span> 19,407,689,229 uops_issued.any # 10.526 G/sec ( - 0.02% ) 21,970,261,576 uops_executed.thread # 11.916 G/sec ( - 0.02% ) 5,408,090,087 mem_load_retired.l1_hit # 2.933 G/sec ( - 0.00% ) 3,861,687 mem_load_retired.l1_miss # 2.095 M/sec ( - 2.11% ) 1.84537 - 0.00135秒時間 elapsed ( - 0.07% ) $ grep . /sys/devices/system/cpu/cpufreq/policy*/energy_performance_preference /sys/devices/system/cpu/cpufreq/policy0/energy_performance_preference: balance_performance ...在所有8個邏輯核心上都一樣

perf計數器資料基本上沒有意義；它是針對整個運行時間，而不是計時區域（在1.8秒中大約有0.1秒），所以這里的大部分時間是在glibc random(3)，它使用"一個非線性加性反饋亂數發生器，采用大小為31長整數的默認表"。 也是在大malloc區域的頁面故障中。

這只是一個有趣的例子。

這只是在兩次構建之間的delta方面比較有趣，但是在定時區域之外的回圈仍然貢獻了許多額外的uops，所以它仍然沒有像人們希望的那樣有趣。

vs.

vs. gcc -O0: No.1 更快，No.2 正如預期的那樣更慢，-O0 在涉及 i 的依賴鏈中加入了一個存盤/重新加載。

$ gcc -O0 array-stride.c
$ taskset -c 3 perf stat --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycle, instructions,uops_issued.any,uops_executed.thread,mem_load_retired.l1_hit,mem_load_retired.l1_miss -r 2 . / a.out 
沒有.1。0.028402 s
沒有.2。0.076405 s
沒有.1。0.028079 s
沒有.2。0.069492 s

 性能計數器統計for './a.out'（2運行）。

          1,979.57 msec task-clock # 0. 999 CPU utilized (  - 0.04% ) 
                 0背景關系切換 # 0.000 /秒                   
                 0 個 cpu-migrations # 0.000 /秒                   
            66,656 次頁面故障 # 33.672 K/sec (  - 0.00% )
     7,252,728,414周期# 3.664 GHz (  - 0.02% )/span>
    20,507,166,672條指令# 每周期2.83insn (  - 0.01% )/span>
    22,268,130,378 uops_issued.any # 11.249 G/sec (  - 0.00% ) 
    25,117,638,171 uops_executed.thread # 12.688 G/sec (  - 0.00% ) 
     6,640,523,801 mem_load_retired.l1_hit # 3.355 G/sec (  - 0.01% ) 
         3,350,518 mem_load_retired.l1_miss # 1.693 M/sec (  - 1.39% ) /-span>

         1.9810591  - 0.0000934秒時間 elapsed (  - 0.00% )