Lin*_*nke 1 c performance x86-64 cpu-architecture
抱歉，我一直不明白这里的规则。我已经删除了所有重复的帖子。这是第一个相关问题。\n请不要将此帖子标记为我另一篇帖子的重复（执行次数减少 3 倍，但执行效率几乎不变。在 C 中），即使代码有些相似，他们提出了截然不同的问题。这也是我同一天发现的两个问题。类似的帖子因“误判”而被重复，然后被关闭。可能是我没有把这个问题说清楚。我真的很希望得到答案，所以我重新发布了它。希望大家能够看清问题，非常感谢！
\n在下面的C代码中，我在第一次测试时间的循环中添加了一个“if”语句，执行时间完全相同。从理论上讲，它应该更慢。尽管分支预测可以使它们的性能几乎相同，但它实际上变得更快。这是什么原理呢？我尝试使用clang和gcc编译器分别在Mac和Linux环境中运行，并尝试了各种优化级别。为了防止缓存受到影响，我让速度较快的先执行，但有冗余代码的循环执行得更快。
\n如果您认为我的描述不可信，请将以下代码编译到您的计算机中并运行。希望有人能为我回答这个问题\xef\xbc\x8c谢谢。
\nC代码：
\n#include <stdio.h>\n#include <time.h>\n#include <stdlib.h>\n#include <string.h>\n\n#define TLen 300000000\n#define SLen 10\n\nint main(int argc, const char * argv[]) {\n srandom((unsigned)time(NULL));\n \n // An array to increase the index,\n // the range of its elements is 1-256\n int rand_arr[128];\n for (int i = 0; i < 128; ++i)\n rand_arr[i] = random()%256+1;\n \n // A random text(very long), the range of its elements is 0-127\n char *tex = malloc((sizeof *tex) * TLen);\n for (int i = 0; i < TLen; ++i)\n tex[i] = random()%128;\n \n // A random string(very short))\n char *str = malloc((sizeof *str) * SLen);\n for (int i = 0; i < SLen; ++i)\n str[i] = random()%128;\n \n // The first testing\n clock_t start = clock();\n for (int i = 0; i < TLen; ){\n if (!memcmp(tex+i, str, SLen)) printf("yes!\\n");\n i += rand_arr[tex[i]];\n }\n clock_t end = clock();\n printf("No.1: %lf s\\n", ((double)(end - start)) / CLOCKS_PER_SEC);\n \n // The second testing\n start = clock();\n for (int i = 0; i < TLen; ){\n i += rand_arr[tex[i]];\n }\n end = clock();\n printf("No.2: %lf s\\n", ((double)(end - start)) / CLOCKS_PER_SEC);\n \n return 0;\n}\n我跑了几百次，几乎都是这个比例。以下是 Linux 中测试的代表性结果：
\nNo.1: 0.110000 s\nNo.2: 0.140000 s\n关键瓶颈是跨越 时缓存未命中的加载使用延迟tex[]，作为从旧i到新的依赖链的一部分i。从小的查找rand_array[]将命中缓存，并且只会向循环携带的依赖链添加大约 5 个周期的 L1d 加载使用延迟，这使得除了延迟之外的任何内容都更不可能与i循环的整体速度相关。（J\xc3\xa9r\xc3\xb4me Richard对上一个问题的回答讨论了延迟 dep 链和随机步幅增量。）
memcmp(tex+i, str, SLen)如果接近缓存行的末尾，则可能充当预取。tex+i如果使用 进行编译-O0，则调用 glibc memcmp，以便在 glibc memcmp 中完成的 SSE 16 字节或 AVX2 32 字节加载跨越缓存行边界并拉入下一行。（IIRC，glibc memcmp 检查并避免页面交叉，但不检查高速缓存行分割，因为这些在现代 CPU 上相对便宜。单步进入它即可查看。进入第二个调用以避免延迟动态链接，或使用 进行编译）-fno-plt。
可能触及随机步长会跳过的一些缓存行有助于硬件预取更加积极，并将其检测为顺序访问模式。32 字节 AVX 负载是缓存行的一半，因此很可能会跨入下一个缓存行。
\n因此，L2 缓存看到的更可预测的缓存行请求序列是 memcmp 版本更快的合理解释。 （Intel CPU 将主预取器放在 L2 中。）
\n如果使用优化进行编译，则 10 字节 memcmp 内联并在内部循环中仅涉及 8 个字节。（如果它们匹配，那么它会跳转到另一个块，在那里检查最后两个。但这种情况极不可能发生）。
\n这可能就是为什么比我的系统-O0更快的-O3原因，在带有 DDR4-2666 DRAM 的 i7-6700k Skylake 上使用 GCC11.1，在 Arch GNU/Linux 上。（您的问题没有具体说明您的数字来自哪个编译器和选项，或者哪个硬件。）
$ gcc -O3 array-stride.c\n$ taskset -c 3 perf stat --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycles,instructions,uops_issued.any,uops_executed.thread,mem_load_retired.l1_hit,mem_load_retired.l1_miss -r 2 ./a.out \nNo.1: 0.041710 s\nNo.2: 0.063072 s\nNo.1: 0.040457 s\nNo.2: 0.061166 s\n\n Performance counter stats for \'./a.out\' (2 runs):\n\n 1,843.71 msec task-clock # 0.999 CPUs utilized ( +- 0.14% )\n 0 context-switches # 0.000 /sec \n 0 cpu-migrations # 0.000 /sec \n 73,300 page-faults # 39.757 K/sec ( +- 0.00% )\n 6,607,078,798 cycles # 3.584 GHz ( +- 0.06% )\n 18,614,303,386 instructions # 2.82 insn per cycle ( +- 0.00% )\n 19,407,689,229 uops_issued.any # 10.526 G/sec ( +- 0.02% )\n 21,970,261,576 uops_executed.thread # 11.916 G/sec ( +- 0.02% )\n 5,408,090,087 mem_load_retired.l1_hit # 2.933 G/sec ( +- 0.00% )\n 3,861,687 mem_load_retired.l1_miss # 2.095 M/sec ( +- 2.11% )\n\n 1.84537 +- 0.00135 seconds time elapsed ( +- 0.07% )\n\n$ grep . /sys/devices/system/cpu/cpufreq/policy*/energy_performance_preference\n/sys/devices/system/cpu/cpufreq/policy0/energy_performance_preference:balance_performance\n ... same on all 8 logical cores\n性能计数器数据基本上没有意义；它是针对整个运行时间，而不是定时区域（大约 1.8 秒中的 0.1 秒），因此这里花费的大部分时间是在glibcrandom(3)中，它使用“采用默认值的非线性加性反馈随机数生成器”大小为 31 的长整数的表”。也在大 malloc 区域上出现页面错误。
它的唯一有趣之处在于两次构建之间的增量，但定时区域之外的循环仍然会贡献许多额外的微指令，因此它仍然不如人们想象的那么有趣。
\nvs.gcc -O0：No.1 更快，No.2 正如预期的那样慢一点，-O0 将存储/重新加载到涉及i.
$ gcc -O0 array-stride.c\n$ taskset -c 3 perf stat --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycles,instructions,uops_issued.any,uops_executed.thread,mem_load_retired.l1_hit,mem_load_retired.l1_miss -r 2 ./a.out \nNo.1: 0.028402 s\nNo.2: 0.076405 s\nNo.1: 0.028079 s\nNo.2: 0.069492 s\n\n Performance counter stats for \'./a.out\' (2 runs):\n\n 1,979.57 msec task-clock # 0.999 CPUs utilized ( +- 0.04% )\n 0 context-switches # 0.000 /sec \n 0 cpu-migrations # 0.000 /sec \n 66,656 page-faults # 33.672 K/sec ( +- 0.00% )\n 7,252,728,414 cycles # 3.664 GHz ( +- 0.02% )\n 20,507,166,672 instructions # 2.83 insn per cycle ( +- 0.01% )\n 22,268,130,378 uops_issued.any # 11.249 G/sec ( +- 0.00% )\n 25,117,638,171 uops_executed.thread # 12.688 G/sec ( +- 0.00% )\n 6,640,523,801 mem_load_retired.l1_hit # 3.355 G/sec ( +- 0.01% )\n 3,350,518 mem_load_retired.l1_miss # 1.693 M/sec ( +- 1.39% )\n\n 1.9810591 +- 0.0000934 seconds time elapsed ( +- 0.00% )\n请记住，此分析针对的是总运行时间，而不是计时区域，因此 2.83 IPC 不适用于计时区域。
\ncmp由于乱序执行，运行宏融合/微指令的实际吞吐量成本je不会增加任何瓶颈。或者甚至是一个整体call memcmp@plt并设置参数。瓶颈是延迟，而不是前端或后端的加载端口，并且 OoO 执行窗口足够深，足以隐藏 memcmp 工作。另请参阅以下内容以了解现代 CPU。（是的，需要大量阅读才能理解它们。）
循环携带的依赖关系通过i- i> tex[i]-> 间接返回到i下一次迭代，单调增加它。 tex[]太大而无法放入缓存，并且硬件预取无法跟上这些步伐。
因此，如果硬件预取未检测到并锁定对连续或每隔一个缓存行的某种顺序访问模式，DRAM 带宽可能是限制因素，甚至是 DRAM 延迟。
\n实际分支可以完美预测，因此它可以在加载结果到达时执行（并确认预测），与等待在同一位置开始的符号扩展字节加载的内容并行。
\n\n\n并且执行时间完全相同。...它实际上变得更快了。
\n
啊？您的时间显示不完全相同。是的，它确实变得更快了memcmp。
\n\n从理论上讲，它应该更慢。
\n
除非您的理论过于简单，无法对现代 CPU 进行建模。不减慢速度很容易解释，因为在等待加载延迟时有空闲的无序执行吞吐量可以完成独立的工作。
\n也可能与性能相关-O0：
-O0是更广泛的负载带来的预取效果。作为参考， Godbolt 上 GCC的 with-memcmp 内部循环与我在桌面上进行的基准测试相匹配。
\n# gcc11.1 -O0 -fPIE\n.L10: # do{\n mov eax, DWORD PTR -16[rbp]\n movsx rdx, eax\n mov rax, QWORD PTR -32[rbp]\n lea rcx, [rdx+rax]\n mov rax, QWORD PTR -40[rbp]\n mov edx, 10\n mov rsi, rax\n mov rdi, rcx\n call memcmp@PLT\n test eax, eax\n jne .L9 # normally taken jump over puts\n lea rax, .LC0[rip]\n mov rdi, rax\n call puts@PLT\n.L9:\n mov eax, DWORD PTR -16[rbp]\n movsx rdx, eax\n mov rax, QWORD PTR -32[rbp]\n add rax, rdx # strange not using an addressing mode, but ok\n movzx eax, BYTE PTR [rax]\n movsx eax, al # GCC -O0 is dumb,\n cdqe # really dumb.\n mov eax, DWORD PTR -576[rbp+rax*4] # look up in rand_array[]\n add DWORD PTR -16[rbp], eax # i += ...\n.L8:\n cmp DWORD PTR -16[rbp], 299999999\n jle .L10 # }while(i<300000000)\n与 -O3 代码对比：
\n# RBP holds char *tex at at this point\n.L10: # do{\n movsx r12, r13d # sign-extend i\n mov rax, QWORD PTR [rbx] # str[0..7] gets reloaded because alias analysis and the possible call to puts defeated the optimizer. Avoiding malloc for it may have helped.\n add r12, rbp # i+tex to avoid indexed addressing modes later? Probably not optimal\n cmp QWORD PTR [r12], rax # first 8 bytes of the memcmp\n je .L18 # code at .L18 checks next 2 and maybe does puts, before jumping back\n.L5:\n movsx rax, BYTE PTR [r12] # sign-extending byte load to pointer width, of tex[i]\n add r13d, DWORD PTR [rsp+rax*4] # i += look up in rand_array[]\n cmp r13d, 299999999\n jle .L10 # }while(i < 300000000)\n由于je .L18从未被采用，因此每次迭代 7 uops，因此 Skylake 可以轻松地以每次迭代 2 个周期以下的速度发出它。
i即使 L1d 缓存命中，通过(R13D)的循环携带依赖关系为：
movsx r12, r13dadd r12, rbpmovsx rax, BYTE PTR [r12]. （不是 4c，这种乐观的特殊情况仅适用于简单寻址模式下的 reg 本身就是 load 的直接结果。）add r13d, DWORD PTR [rsp+rax*4]因此，在 L1d 命中的最佳情况下，总共大约有 13 个周期延迟，在前端留下大量空闲“槽”，以及空闲的后端执行单元，即使调用实际的 glibc memcmp 也没什么大不了的。
\n（当然，-O0代码噪音更大，因此管道区域中的一些空闲插槽已经用完，但 dep 链更长，因为-O0代码保留i在内存中：Why does clang generated inefficient asm with -O0 （对于这个简单的浮点和）？）
初始化循环为 CPU 在定时区域之前达到最大睿频提供了充足的时间，并通过首先接触分配的页面来预防故障。 绩效评估的惯用方式？
\n如果在等待来自缓存未命中加载的传入数据期间有更多的工作、更少的停顿，也可能会产生保持 CPU 频率较高的效果。请参阅通过施加内存压力来降低 CPU 频率。
\n上面的结果是我用 EPP = 进行测试的balance_performance。
我还使用 , 进行了测试performance，并且 -O0 (libc memcmp) 仍然比 -O3 (内联 memcmp) 更快，但是所有 4 个循环确实加快了一些速度（有/没有 memcmp，以及优化与否）。
| 编译器/CPU | 1号if(memcmp) | 2号plain |
|---|---|---|
-O0/balance_performance | 0.028079秒 | 0.069492秒 |
-O0/performance | 0.026898秒 | 0.053805秒 |
-O3/balance_performance | 0.040457秒 | 0.061166秒 |
-O3/performance | 0.035621秒 | 0.047475秒 |
即使使用，更快的-O0效果仍然存在并且非常重要EPP=performance，因此我们知道这不仅仅是时钟速度的问题。根据之前的实验，performance即使在内存有限的情况下（其他设置将从 4.2 GHz 降频到 2.7 GHz），它也能保持最大睿频。因此，调用 memcmp 很可能有助于触发更好的预取，以减少平均缓存未命中延迟。
不幸的是，我没有为 PRNG 使用固定种子，因此就访问的整个缓存行的模式而言，由于预取器的随机性好坏，可能会存在一些变化。我只是为每个运行了一次特定的运行（该对中的第二次运行是由 perf stat -r 2 启动的，所以它应该受到系统波动的影响更小。）
\n看起来performance对 No.2 循环（其中发生的事情更少）以及版本-O3（同样，其中发生的事情更少）产生了更大的差异，这与 Skylake 在核心几乎耗尽时降低时钟速度是一致的在 EPP 设置中，除了performance.
| 归档时间： |
|
| 查看次数： |
470 次 |
| 最近记录： |