在没有优化的情况下编译时添加冗余赋值可以加速代码
Adding a redundant assignment speeds up code when compiled without optimization
我发现一个有趣的现象：
#include<stdio.h>
#include<time.h>
int main() {
int p, q;
clock_t s,e;
s=clock();
for(int i = 1; i < 1000; i++){
for(int j = 1; j < 1000; j++){
for(int k = 1; k < 1000; k++){
p = i + j * k;
q = p; //Removing this line can increase running time.
}
}
}
e = clock();
double t = (double)(e - s) / CLOCKS_PER_SEC;
printf("%lf\n", t);
return 0;
}
我在 i5-5257U Mac OS 上使用 GCC 7.3.0 来编译代码 没有任何优化。这是超过 10 次的平均 运行 时间：
还有其他人在其他英特尔平台上测试了这个案例，得到了相同的结果。
我 post GCC here 生成的程序集。两个汇编代码的唯一区别是在addl , -12(%rbp)之前，速度快的多了两个操作：
movl -44(%rbp), %eax
movl %eax, -48(%rbp)
那么为什么程序 运行 使用这样的赋值会更快？
很有帮助。 AMD Phenom II X4 810 和 ARMv7 处理器 (BCM2835) 上的测试显示相反的结果，支持存储转发加速特定于一些英特尔 CPU.
驱使我重写问题。 :)
这个问题的核心是与处理器架构和组装有关的有趣现象。所以我觉得可能值得讨论一下。
TL:DR：如果重新加载不尝试“立即”发生，Sandybridge-family store-forwarding 具有较低的延迟。添加无用代码可以加快 debug-mode 循环，因为 loop-carried -O0 anti-optimized 代码中的延迟瓶颈几乎总是涉及 store/reload of some C variables.
这种行动放缓的其他例子：, , accessing vars through pointers.
显然也是 on low-power Goldmont，除非有不同的原因需要额外的负载帮助。
None 与优化代码相关。 store-forwarding 延迟的瓶颈偶尔会发生，但向您的代码添加无用的复杂性不会加快它的速度。
您正在对调试版本进行基准测试，。它们与优化代码有不同的瓶颈，而不是统一的减速。
但很明显，一个版本的调试版本 运行ning 比另一个版本的调试版本慢是有真正原因的。 （假设您测量正确并且不仅仅是 CPU 频率变化（turbo / power-saving）导致 wall-clock 时间差异。）
如果你想深入了解 x86 性能分析的细节，我们可以尝试解释为什么 asm 以它最初的方式执行，以及为什么 asm 来自一个额外的 C 语句（带有 -O0 编译成额外的 asm 指令）可以使它整体上更快。 这将告诉我们一些有关 asm 性能影响的信息，但对优化 C 没有任何用处。
你没有显示整个内部循环，只显示了部分循环体，但是 gcc -O0 是 pretty predictable。每个 C 语句都与其他所有语句分开编译，所有 C 变量在每个语句的块之间溢出/重新加载。这允许您在 single-stepping 时使用调试器 更改 变量，甚至跳转到函数中的不同行，并且代码仍然有效。以这种方式编译的性能成本是灾难性的。例如，您的循环没有 side-effects（none 的结果被使用）因此整个 triple-nested 循环可以并且会在实际构建中编译为零指令，运行宁无限快。或者更现实地说，运行即使没有优化或进行重大转换，每次迭代也只有 1 个周期而不是 ~6 个。
瓶颈可能是 loop-carried 对 k 的依赖，store/reload 和 add 增加 。 Store-forwarding 延迟通常为 around 5 cycles on most CPUs。因此，您的内部循环被限制为每 ~6 个周期 运行ning 一次，memory-destination add.
的延迟
如果您使用的是 Intel CPU，store/reload 当重新加载无法立即尝试执行时，延迟实际上可以更低（更好）.在依赖对之间有更多独立的 loads/stores 可以解释你的情况。参见 。
因此，随着循环中的更多工作，addl , -12(%rbp) 在 运行 back-to-back 时可以维持每 6 个周期的吞吐量可能反而只会造成瓶颈每 4 或 5 个周期迭代一次。
根据测量 from a 2013 blog post，这种效应显然发生在 Sandybridge 和 Haswell（不仅仅是 Skylake）上，所以是的，这也是您的 Broadwell i5-5257U 上最可能的解释。似乎 这种影响发生在所有英特尔 Sandybridge-family CPUs.
没有关于您的测试硬件、编译器版本（或内部循环的 asm 源代码）、和绝对 and/or 相对性能的更多信息 数字对于两个版本，这是我对解释的最佳low-effort猜测。在我的 Skylake 系统上进行基准测试/分析 gcc -O0 还不够有趣，无法亲自尝试。下次，包括时间编号。
对于不属于 loop-carried 依赖链的所有工作，stores/reloads 的延迟无关紧要，重要的是吞吐量。现代 out-of-order CPUs 中的存储队列确实有效地提供了内存重命名，消除了 write-after-write and write-after-read hazards from reusing the same stack memory for p being written and then read and written somewhere else. (See https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies for more about memory hazards specifically, and 更多关于延迟与吞吐量的关系并重用相同的寄存器/寄存器重命名）
内部循环的多次迭代可以同时进行，因为 memory-order 缓冲区 (MOB) 跟踪每个加载需要从哪个存储中获取数据，而不需要以前的存储到相同的提交到 L1D 并退出存储队列的位置。 （有关 CPU 微架构内部结构的更多信息，请参阅英特尔的优化手册和 Agner Fog 的微架构 PDF。MOB 是 和加载缓冲区的组合）
这是否意味着添加无用的语句会加快实际程序的速度？ （启用优化）
一般来说，不，不会。编译器将循环变量保存在最内层循环的寄存器中。无用的语句实际上会在启用优化的情况下进行优化。
为 gcc -O0 调整您的源代码是没有用的。 使用 -O3 或项目使用的默认构建脚本的任何选项进行测量。
此外，此 store-forwarding 加速是英特尔特有的 Sandybridge-family，您不会e 它在 Ryzen 等其他微体系结构上，除非它们也具有类似的 store-forwarding 延迟效果。
Store-forwarding 延迟可能是实际（优化的）编译器输出中的一个问题，尤其是如果您没有使用 link-time-optimization (LTO) 让微小的内联函数，尤其是通过引用传递或 return 任何东西的函数（因此它必须通过内存而不是寄存器）。如果你真的想在 Intel CPUs 上解决这个问题并且可能在其他 CPUs 上使事情变得更糟，则可能需要像 volatile 这样的 hack 来缓解这个问题。参见
我发现一个有趣的现象：
#include<stdio.h>
#include<time.h>
int main() {
int p, q;
clock_t s,e;
s=clock();
for(int i = 1; i < 1000; i++){
for(int j = 1; j < 1000; j++){
for(int k = 1; k < 1000; k++){
p = i + j * k;
q = p; //Removing this line can increase running time.
}
}
}
e = clock();
double t = (double)(e - s) / CLOCKS_PER_SEC;
printf("%lf\n", t);
return 0;
}
我在 i5-5257U Mac OS 上使用 GCC 7.3.0 来编译代码 没有任何优化。这是超过 10 次的平均 运行 时间：
我 post GCC here 生成的程序集。两个汇编代码的唯一区别是在addl , -12(%rbp)之前，速度快的多了两个操作：
movl -44(%rbp), %eax
movl %eax, -48(%rbp)
那么为什么程序 运行 使用这样的赋值会更快？
这个问题的核心是与处理器架构和组装有关的有趣现象。所以我觉得可能值得讨论一下。
TL:DR：如果重新加载不尝试“立即”发生，Sandybridge-family store-forwarding 具有较低的延迟。添加无用代码可以加快 debug-mode 循环，因为 loop-carried -O0 anti-optimized 代码中的延迟瓶颈几乎总是涉及 store/reload of some C variables.
这种行动放缓的其他例子：
显然也是 on low-power Goldmont，除非有不同的原因需要额外的负载帮助。
None 与优化代码相关。 store-forwarding 延迟的瓶颈偶尔会发生，但向您的代码添加无用的复杂性不会加快它的速度。
您正在对调试版本进行基准测试，
但很明显，一个版本的调试版本 运行ning 比另一个版本的调试版本慢是有真正原因的。 （假设您测量正确并且不仅仅是 CPU 频率变化（turbo / power-saving）导致 wall-clock 时间差异。）
如果你想深入了解 x86 性能分析的细节，我们可以尝试解释为什么 asm 以它最初的方式执行，以及为什么 asm 来自一个额外的 C 语句（带有 -O0 编译成额外的 asm 指令）可以使它整体上更快。 这将告诉我们一些有关 asm 性能影响的信息，但对优化 C 没有任何用处。
你没有显示整个内部循环，只显示了部分循环体，但是 gcc -O0 是 pretty predictable。每个 C 语句都与其他所有语句分开编译，所有 C 变量在每个语句的块之间溢出/重新加载。这允许您在 single-stepping 时使用调试器 更改 变量，甚至跳转到函数中的不同行，并且代码仍然有效。以这种方式编译的性能成本是灾难性的。例如，您的循环没有 side-effects（none 的结果被使用）因此整个 triple-nested 循环可以并且会在实际构建中编译为零指令，运行宁无限快。或者更现实地说，运行即使没有优化或进行重大转换，每次迭代也只有 1 个周期而不是 ~6 个。
瓶颈可能是 loop-carried 对 k 的依赖，store/reload 和 add 增加 。 Store-forwarding 延迟通常为 around 5 cycles on most CPUs。因此，您的内部循环被限制为每 ~6 个周期 运行ning 一次，memory-destination add.
如果您使用的是 Intel CPU，store/reload 当重新加载无法立即尝试执行时，延迟实际上可以更低（更好）.在依赖对之间有更多独立的 loads/stores 可以解释你的情况。参见
因此，随着循环中的更多工作，addl , -12(%rbp) 在 运行 back-to-back 时可以维持每 6 个周期的吞吐量可能反而只会造成瓶颈每 4 或 5 个周期迭代一次。
根据测量 from a 2013 blog post，这种效应显然发生在 Sandybridge 和 Haswell（不仅仅是 Skylake）上，所以是的，这也是您的 Broadwell i5-5257U 上最可能的解释。似乎 这种影响发生在所有英特尔 Sandybridge-family CPUs.
没有关于您的测试硬件、编译器版本（或内部循环的 asm 源代码）、和绝对 and/or 相对性能的更多信息 数字对于两个版本，这是我对解释的最佳low-effort猜测。在我的 Skylake 系统上进行基准测试/分析 gcc -O0 还不够有趣，无法亲自尝试。下次，包括时间编号。
对于不属于 loop-carried 依赖链的所有工作，stores/reloads 的延迟无关紧要，重要的是吞吐量。现代 out-of-order CPUs 中的存储队列确实有效地提供了内存重命名，消除了 write-after-write and write-after-read hazards from reusing the same stack memory for p being written and then read and written somewhere else. (See https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies for more about memory hazards specifically, and
内部循环的多次迭代可以同时进行，因为 memory-order 缓冲区 (MOB) 跟踪每个加载需要从哪个存储中获取数据，而不需要以前的存储到相同的提交到 L1D 并退出存储队列的位置。 （有关 CPU 微架构内部结构的更多信息，请参阅英特尔的优化手册和 Agner Fog 的微架构 PDF。MOB 是
这是否意味着添加无用的语句会加快实际程序的速度？ （启用优化）
一般来说，不，不会。编译器将循环变量保存在最内层循环的寄存器中。无用的语句实际上会在启用优化的情况下进行优化。
为 gcc -O0 调整您的源代码是没有用的。 使用 -O3 或项目使用的默认构建脚本的任何选项进行测量。
此外，此 store-forwarding 加速是英特尔特有的 Sandybridge-family，您不会e 它在 Ryzen 等其他微体系结构上，除非它们也具有类似的 store-forwarding 延迟效果。
Store-forwarding 延迟可能是实际（优化的）编译器输出中的一个问题，尤其是如果您没有使用 link-time-optimization (LTO) 让微小的内联函数，尤其是通过引用传递或 return 任何东西的函数（因此它必须通过内存而不是寄存器）。如果你真的想在 Intel CPUs 上解决这个问题并且可能在其他 CPUs 上使事情变得更糟，则可能需要像 volatile 这样的 hack 来缓解这个问题。参见