为什么C ++优化器对这些临时variables有问题，或者为什么在紧密循环中应该避免使用v `？
在这个代码片段中 ，我比较了两个function相同的循环的性能：
for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } 和
for (int i = 1; i < v.size()-1; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n;
第一个运行速度明显慢于第二个，其优化标志设置为O2 ：
- 第二个循环现在比Clang 3.7.0 慢了大约330％
- 第二个循环比gcc 4.9.3慢2％左右
- 第二个循环比Visual C ++ 2015慢了大约2％
我很困惑，现代的C ++优化器在处理这种情况时遇到了问题。 任何线索为什么？ 为了获得最佳性能，我是否必须编写难看的代码而不使用临时variables？
使用临时variables可以使代码更快，有时甚至是显着的。 到底是怎么回事？
我正在使用的完整代码如下所示：
#include <algorithm> #include <chrono> #include <random> #include <iomanip> #include <iostream> #include <vector> using namespace std; using namespace std::chrono; vector<int> v(1'000'000); int f0() { int n = 0; for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } return n; } int f1() { int n = 0; for (int i = 1; i < v.size()-1; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n; return n; } int main() { auto benchmark = [](int (*f)()) { const int N = 100; volatile long long result = 0; vector<long long> timings(N); for (int i = 0; i < N; ++i) { auto t0 = high_resolution_clock::now(); result += f(); auto t1 = high_resolution_clock::now(); timings[i] = duration_cast<nanoseconds>(t1-t0).count(); } sort(timings.begin(), timings.end()); cout << fixed << setprecision(6) << timings.front()/1'000'000.0 << "ms min\n"; cout << timings[timings.size()/2]/1'000'000.0 << "ms median\n" << "Result: " << result/N << "\n\n"; }; mt19937 generator (31415); // deterministic seed uniform_int_distribution<> distribution(0, 1023); for (auto& e: v) e = distribution(generator); benchmark(f0); benchmark(f1); cout << "\ndone\n"; return 0; }
看来编译器对于std::vector<>::size()和内部向量缓冲区大小之间的关系知之甚less。 考虑std::vector是我们自定义的bugged_vector向量类对象，有轻微的bug – 它的::size()有时可能比内部缓冲区大小n ，但是只有v[n-2] >= v[n-1] 。
然后，两个片段再次具有不同的语义：第一个片断具有未定义的行为，因为我们访问元素v[v.size() - 1] 。 然而，第二个没有：由于&&的短路性质，我们在最后一次迭代中不会读v[v.size() - 1] 。
所以，如果编译器不能certificate我们的v不是一个bugged_vector ，那么它必须短路，这会在机器代码中引入额外的跳转。
通过查看clang汇编输出，我们可以看到它实际上发生了。
从Godbolt编译器资源pipe理器中 ，使用clang 3.7.0 -O2， f0的循环是：
### f0: just the loop .LBB1_2: # =>This Inner Loop Header: Depth=1 mov edi, ecx cmp edx, edi setl r10b mov ecx, dword ptr [r8 + 4*rsi + 4] lea rsi, [rsi + 1] cmp edi, ecx setl dl and dl, r10b movzx edx, dl add eax, edx cmp rsi, r9 mov edx, edi jb .LBB1_2
而对于f1 ：
### f1: just the loop .LBB2_2: # =>This Inner Loop Header: Depth=1 mov esi, r10d mov r10d, dword ptr [r9 + 4*rdi] lea rcx, [rdi + 1] cmp esi, r10d jge .LBB2_4 # <== This is Extra Jump cmp r10d, dword ptr [r9 + 4*rdi + 4] setl dl movzx edx, dl add eax, edx .LBB2_4: # %._crit_edge.3 cmp rcx, r8 mov rdi, rcx jb .LBB2_2
我已经指出了f1的额外跳跃。 正如我们（希望）知道的那样，在一个紧密的循环中进行条件跳转对性能是不利的。 （有关详细信息，请参阅x86标记wiki中的性能指南。）
GCC和Visual Studio意识到 编辑 。 原来， std::vector行为良好，并为这两个片段生成几乎相同的程序集。clang更好地优化代码。 所有这三个编译器都不能certificate在比较第二个例子（或不select）之前读v[i + 1]是安全的，但是只有clang才能设法优化第一个例子， v[i + 1]是有效的或UB。
2％的性能差异可以忽略不计，可以通过不同的顺序或某些指令的select来解释。
这里有更多的见解，以扩大@deniss的答案，正确诊断问题。
顺便说一下，这与所有时间最stream行的C ++ Q＆A都有关系。 “为什么处理sorting后的数组要比未sorting的数组快？ 。
主要的问题是编译器必须遵守逻辑AND运算符（&&），而不是从v [i + 1]加载，除非第一个条件为真。 这是逻辑AND运算符语义的结果，也是C ++ 11引入的严格的内存模型语义的结果，标准草案中的相关条款是
5.14逻辑AND运算符[expr.log.and]
不同于&& &&保证从左至右的评估：如果第一个操作数为假，则不评估第二个操作数。
ISO C ++ 14标准（草案N3797）
和投机阅读
1.10multithreading执行和数据竞赛[intro.multithread]
[ 注意：引入潜在共享内存位置的推测性读取的转换可能不会保留本标准中定义的C ++程序的语义，因为它们可能引入数据竞争。 但是，它们通常在优化编译器的上下文中有效，该优化编译器针对数据竞争定义明确的语义的特定机器。 对于不容忍比赛或提供硬件比赛检测的假设机器，它们将是无效的。 – 结束注意 ]
ISO C ++ 14标准（草案N3797）
我的猜测是，优化器发挥它的安全性，并且目前select不向每个目标处理器的潜在共享存储器发出推测负载而不是特殊情况，推测负载是否可以为该目标引入可检测的数据竞争。
为了实现这个，编译器生成一个条件分支。 通常这是不明显的，因为现代处理器具有非常复杂的分支预测，并且误预测率通常非常低。 然而这里的数据是随机的 – 这会杀死分支预测。 错误预测的成本是10到20个CPU周期，考虑到CPU通常每个周期退出2条指令，这相当于20到40条指令。 如果预测率是50％（随机），那么每次迭代都会有一个相当于10到20条指令的误预测罚分 – 巨大 。
注：编译器可以certificate元素v[0]到v[v.size()-2]将按照顺序引用，而不pipe它们包含的值如何。 这将允许编译器在这种情况下生成代码，无条件地加载除vector的最后一个元素之外的所有代码。 v [v.size（） – 1]中向量的最后一个元素只能在循环的最后一个迭代中加载，并且只有在第一个条件为真时才加载。 因此，编译器可以为循环生成代码，直到最后一次迭代时短路分支，然后在最后一次迭代中使用与短路分支不同的代码 – 这将要求编译器知道数据是随机的，分支预测是无用的因此值得一提的是编译器并不那么复杂。
为了避免由逻辑与（&&）生成的条件分支，避免将内存位置加载到局部variables中，我们可以将逻辑与运算符更改为按位与代码片段 ，当数据是随机的时候，结果快4倍
int f2() { int n = 0; for (int i = 1; i < v.size()-1; ++i) n += (v[i-1] < v[i]) & (v[i] < v[i+1]); // Bitwise AND return n; }
产量
3.642443ms min 3.779982ms median Result: 166634 3.725968ms min 3.870808ms median Result: 166634 1.052786ms min 1.081085ms median Result: 166634 done
在gcc 5.3上的结果快了8倍（ 这里住在Coliru ）
g++ --version g++ -std=c++14 -O3 -Wall -Wextra -pedantic -pthread -pedantic-errors main.cpp -lm && ./a.out g++ (GCC) 5.3.0 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 3.761290ms min 4.025739ms median Result: 166634 3.823133ms min 4.050742ms median Result: 166634 0.459393ms min 0.505011ms median Result: 166634 done
您可能想知道编译器如何在不生成条件分支的情况下评估比较v[i-1] < v[i] 。 答案取决于目标，对于x86，这可能是因为SETcc指令，根据EFLAGS寄存器中的条件产生一个1字节的结果，0或1，与条件分支中可能使用的条件相同，但没有分支。 在由@deniss给出的生成代码中，可以看到生成的setl ，如果符合前面的比较指令评估的条件“小于”，则将结果设置为1：
cmp edx, edi ; a < b ? setl r10b ; r10b = a < b ? 1 : 0 mov ecx, dword ptr [r8 + 4*rsi + 4] ; c = v[i+1] lea rsi, [rsi + 1] ; ++i cmp edi, ecx ; b < c ? setl dl ; dl = b < c ? 1 : 0 and dl, r10b ; dl &= r10b movzx edx, dl ; edx = zero extended dl add eax, edx ; n += edx
f0和f1在语义上是不同的。
x() && y()在我们所知的x（）为假的情况下包含一个短路。 这意味着如果x（）是假的，那么y（） 不能被评估。
这可以防止预取数据，以评估y（）和（至less在clang）导致插入的条件跳转，这是导致分支预测失误。
再加两个testingcertificate了这一点。
#include <algorithm> #include <chrono> #include <random> #include <iomanip> #include <iostream> #include <vector> using namespace std; using namespace std::chrono; vector<int> v(1'000'000); int f0() { int n = 0; for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } return n; } int f1() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n; return n; } int f2() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { auto t1 = v[i-1] < v[i]; auto t2 = v[i] < v[i+1]; if (t1 && t2) ++n; } return n; } int f3() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { n += 1 * (v[i-1] < v[i]) * (v[i] < v[i+1]); } return n; } int main() { auto benchmark = [](int (*f)()) { const int N = 100; volatile long long result = 0; vector<long long> timings(N); for (int i = 0; i < N; ++i) { auto t0 = high_resolution_clock::now(); result += f(); auto t1 = high_resolution_clock::now(); timings[i] = duration_cast<nanoseconds>(t1-t0).count(); } sort(timings.begin(), timings.end()); cout << fixed << setprecision(6) << timings.front()/1'000'000.0 << "ms min\n"; cout << timings[timings.size()/2]/1'000'000.0 << "ms median\n" << "Result: " << result/N << "\n\n"; }; mt19937 generator (31415); // deterministic seed uniform_int_distribution<> distribution(0, 1023); for (auto& e: v) e = distribution(generator); benchmark(f0); benchmark(f1); benchmark(f2); benchmark(f3); cout << "\ndone\n"; return 0; }
结果（苹果铛，-O2）：
1.233948ms min 1.320545ms median Result: 166850 3.366751ms min 3.493069ms median Result: 166850 1.261948ms min 1.361748ms median Result: 166850 1.251434ms min 1.353653ms median Result: 166850
迄今没有一个答案给出了f()的版本，gcc或clang可以完全优化。 它们都产生了两个比较每个迭代的asm。 在Godbolt编译器资源pipe理器中查看带有asm输出的代码 。 （有关从asm输出中预测性能的重要背景知识： Agner Fog的微体系结构指南以及x86标记wiki上的其他链接。与往常一样，通常最好使用性能计数器进行configuration以查找停顿。
当我们评估v[i] < v[i+1]时， v[i-1] < v[i]是我们已经做过的最后一次迭代的工作。 理论上，帮助编译器可以让它更好地优化（见f3() ）。 实际上，在某些情况下，最终会导致自动向量化的失败，而gcc甚至在使用-mtune=core2下也会发出部分寄存器停滞的代码，这是一个巨大的问题。
手动将v.size() - 1从循环上限检查中提取出来似乎有所帮助。 OP的f0和f1实际上并不是从v的开始/结束指针重新计算v.size() ，但是它在某种程度上仍然比在计算循环外部时size_t upper = v.size() - 1 （ f2()和f4() ）。
一个单独的问题是，使用size_t上限的int循环计数器意味着循环可能是无限的。 我不确定这对其他优化有多大的影响。
底线：编译器是复杂的野兽 。 预测哪个版本能够很好地优化并不明显或简单。
在Core 2 E6600（Merom / Conroe微体系结构）上的64位Ubuntu 15.10上的结果。
clang++-3.8 -O3 -march=core2 | g++ 5.2 -O3 -march=core2 | gcc 5.2 -O2 (default -mtune=generic) f0 1.825ms min(1.858 med) | 5.008ms min(5.048 med) | 5.000 min(5.028 med) f1 4.637ms min(4.673 med) | 4.899ms min(4.952 med) | 4.894 min(4.931 med) f2 1.292ms min(1.323 med) | 1.058ms min(1.088 med) (autovec) | 4.888 min(4.912 med) f3 1.082ms min(1.117 med) | 2.426ms min(2.458 med) | 2.420 min(2.465 med) f4 1.291ms min(1.341 med) | 1.022ms min(1.052 med) (autovec) | 2.529 min(2.560 med)
Intel SnB系列硬件的结果会有所不同， IvyBridge和稍后将不会有部分寄存器放缓的地方。 Core2受慢速未alignment负载的限制，每个周期只有一个负载。 循环可能足够小，解码不是一个问题，但。
f0和f1 ：
gcc 5.2：OP的f0和f1都是分支循环，不会自动向量化。 然而， f0只使用一个分支，并且使用了一个奇怪的setl sil / sbb eax, -1 cmp sil, 1 / sbb eax, -1来进行短路比较的后半部分。 所以它在每次迭代中都进行了比较。
叮当3.8： f0 ：每次迭代只有一个负载，但它们将它们and它们进行比较。 f1 ：两个比较每个迭代，一个与分支保存C语义。 两次加载每次迭代。
int f2() { int n = 0; size_t upper = v.size()-1; // difference from f0: hoist upper bound and use size_t loop counter for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; if (a < b && b < c) ++n; } return n; }
gcc 5.2 -O3 ：自动vector化，用三个负载得到三个偏移向量，产生一个4比较结果的向量。 另外，在合并来自两个pcmpgtd指令的结果之后，将它们与一个全零的vector进行比较，然后掩码。 零已经是添加的标识元素，所以这真的很愚蠢。
铿锵声3.8 -O3 ：展开：每次迭代都会执行两个负载，三个cmp / setcc，两个s和两个add s。
int f4() { int n = 0; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; bool ab_lt = a < b; bool bc_lt = b < c; n += (ab_lt & bc_lt); // some really minor code-gen differences from f2: auto-vectorizes to better code that runs slightly faster even for this large problem size } return n; }
- gcc 5.2
-O3：自动pcmpeqd如f2，但没有额外的pcmpeqd。 - gcc 5.2
-O2：没有调查为什么这是f2两倍。 - 铛
-O3：与f2大致相同的代码。
尝试编译器手持
int f3() { int n = 0; int a = v[0], b = v[1]; // These happen before checking v.size, defeating the loop vectorizer or something bool ab_lt = a < b; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int c = v[i+1]; // only one load and compare inside the loop bool bc_lt = b < c; n += (ab_lt & bc_lt); ab_lt = bc_lt; a = b; // unused inside the loop, only the compare result is needed b = c; } return n; }
-
叮当3.8
-O3：在循环内部展开4个负载（当没有复杂的循环运行依赖时，叮当声通常喜欢展开4）。
4 cmp / setcc，4x和/ movzx，4x添加。 所以铿锵做到了我所希望的，并且做出了接近最优的标量代码。 这是最快的非vector化版本 ，并且（在movups未alignment加载速度较慢的core2上）与gcc的vector化版本一样快。 -
gcc 5.2
-O3：无法自动向量化。 我的理论是，访问循环外的数组混淆了自动向量化器。 也许是因为我们在检查v.size()之前做的，或者一般来说。编译为我们希望的标量代码，一个加载，一个cmp / setcc，以及一个
and每个迭代。 但是gcc创build了一个部分寄存器的停顿 ，即使是在-mtune=core2下，这也是一个巨大的问题（2到3个周期的停顿，在写入其中的一部分之后读取宽范围时插入一个合并的uop）。 （setcc只适用于8位操作数大小，这是AMD在deviseAMD64 ISA时应该改变的东西）。这是gcc代码运行速度比clang慢2.5倍的主要原因。
## the loop in f3(), from gcc 5.2 -O3 (same code with -O2) .L31: add rcx, 1 # i, mov edi, DWORD PTR [r10+rcx*4] # a, MEM[base: _19, index: i_13, step: 4, offset: 0] cmp edi, r8d # a, a # gcc's verbose-asm comments are a bit bogus here: one of these `a`s is from the last iteration, so this is really comparing c, b mov r8d, edi # a, a setg sil #, tmp124 and edx, esi # D.111089, tmp124 # PARTIAL-REG STALL: reading esi after writing sil movzx edx, dl # using movzx to widen sil to esi would have solved the problem, instead of doing it after the and add eax, edx # n, D.111085 # n += ... cmp r9, rcx # upper, i mov edx, esi # ab_lt, tmp124 jne .L31 #, ret
