Pau*_*zak 61 c++ optimization performance
在这段代码中,我正在比较两个功能相同的循环的性能:
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:的许多不同C++编译器中,第一个运行速度明显慢于第二个编译器:
我很困惑,现代C++优化器在处理这种情况时遇到了问题.任何线索为什么？我是否必须编写丑陋的代码而不使用临时变量才能获得最佳性能？
现在,使用临时变量可以使代码更快,有时甚至更快.到底是怎么回事？
我正在使用的完整代码如下:
#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;
}
小智 50
似乎编译器缺乏关于std::vector<>::size()内部向量缓冲区大小之间关系的知识.考虑std::vector成为我们的自定义bugged_vector矢量类对象,有轻微的错误 - 它::size()有时可能比内部缓冲区大小多一个n,但只有这样v[n-2] >= v[n-1].
然后两个片段再次具有不同的语义:第一个具有未定义的行为,因为我们访问元素v[v.size() - 1].然而,第二个没有:由于短路性质&&,我们从未读过v[v.size() - 1]最后一次迭代.
因此,如果编译器无法证明我们v不是a bugged_vector,它必须短路,这会在机器代码中引入额外的跳转.
通过查看汇编输出clang,我们可以看到它确实发生了.
从Godbolt Compiler Explorer中,使用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优化代码的工作做得更好.所有三个编译器都无法证明v[i + 1]在第二个示例中比较之前读取是安全的(或者选择不是),但只能clang设法使用读取v[i + 1]有效或UB 的附加信息来优化第一个示例.
可以通过不同顺序或某些指令的选择来解释2%的性能差异可以忽略不计.
amd*_*mdn 40
以下是对@deniss答案进行扩展的更多见解,该答案正确地诊断了该问题.
顺便提一下,这与有史以来最流行的C++问答有关"为什么处理排序的数组比未排序的数组更快？" .
主要问题是编译器必须遵守逻辑AND运算符(&&)而不从v [i + 1]加载,除非第一个条件为真.这是逻辑AND运算符的语义以及C++ 11引入的紧缩内存模型语义的结果,标准草案中的相关条款是
5.14逻辑AND运算符[expr.log.and]
与&不同,&&保证从左到右的评估:如果第一个操作数为假,则不评估第二个操作数.
ISO C++ 14标准(草案N3797)
对于推测性读取
1.10多线程执行和数据竞争[intro.multithread]
23 [ 注意:引入潜在共享内存位置的推测性读取的转换可能无法保留本标准中定义的C++程序的语义,因为它们可能会引入数据争用.但是,它们通常在优化编译器的上下文中有效,该编译器针对具有明确定义的数据争用语义的特定计算机.对于不能容忍比赛或提供硬件竞赛检测的假想机器,它们无效.- 尾注 ]
ISO C++ 14标准(草案N3797)
我的猜测是优化器发挥其安全性,并且当前选择不向可能共享的内存发出推测性负载而不是每个目标处理器的特殊情况,无论推测性负载是否可能为该目标引入可检测的数据竞争.
为了实现这一点,编译器生成条件分支.通常这并不明显,因为现代处理器具有非常复杂的分支预测,并且误预测率通常非常低.然而,这里的数据是随机的 - 这会导致分支预测.错误预测的成本是10到20个CPU周期,考虑到CPU通常每个周期停用2个指令,这相当于20到40个指令.如果预测率为50%(随机),那么每次迭代都会产生相当于10到20条指令的错误预测惩罚 - 巨大.
注:编译器可以证明元素v[0]来v[v.size()-2]将引用的顺序,无论它们所包含的值.这将允许编译器在这种情况下生成无条件地加载除向量的最后一个元素之外的所有元素的代码.向量的最后一个元素,在v [v.size() - 1],只能在循环的最后一次迭代中加载,并且只有在第一个条件为真时才加载.因此,编译器可以为循环生成代码而不需要短路分支,直到最后一次迭代,然后在最后一次迭代时使用不同的代码和短路分支 - 这将要求编译器知道数据是随机的并且分支预测是无用的因此值得为此烦恼 - 编译器并不那么复杂 - 但是.
为了避免Logical AND(&&)生成的条件分支并避免将内存位置加载到局部变量中,我们可以将逻辑AND运算符更改为此处的Bitwise AND 代码片段,当数据随机时,结果几乎快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指令产生一个字节的结果,0或1,这取决于EFLAGS寄存器中的条件,条件分支中可以使用的相同条件,但是没有分支.在@deniss给出的生成代码中,您可以看到setlgenerate,如果满足条件"小于",则将结果设置为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()为false,则不能计算y().
这可以防止预取数据以便评估y()和(至少在clang上)导致插入条件跳转,这导致分支预测器未命中.
添加另外两个测试证明了这一点.
#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