为什么在函数参数中改变`const ull`到`const ull&`会导致性能增益？ [英] Why does changing `const ull` to `const ull&` in function parameter result in performance gain?
问题描述
因此，使用以下代码，将 x 的类型从 const ull 更改为 const ull& （使用 typedef unsigned long long ull ）会导致大约25％ code> -O3 -std = c ++ 11 -g ，我不知道为什么会有这么大的区别。
So with the following code, changing the type of the parameter x from const ull to const ull& (with typedef unsigned long long ull) results in a roughly 25% speedup when compiled with gcc 4.7.2 and flags -O3 -std=c++11 -g, and I can't figure out why this would make such a big difference.
static void inline single_mult(const std::vector<ull>::iterator& data,
const std::vector<ull>::const_iterator& rbegin,
const std::vector<ull>::const_iterator& rend,
const ull x) {
ull tmp=0, carry=0, i=0;
for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
tmp = x*(*rhs_it) + data[i] + carry;
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
data[i++] = tmp;
}
data[i] += carry;
}
在以下函数中调用（用于教科书长乘法） p>
It is called in the following function (for doing schoolbook long multiplication)
static void naive(std::vector<ull>::iterator data,
std::vector<ull>::const_iterator cbegin,
std::vector<ull>::const_iterator cend ,
std::vector<ull>::const_iterator rbegin,
std::vector<ull>::const_iterator rend) {
for (auto data_it = cbegin;
data_it != cend; ++data_it) {
if (*data_it != 0) {
single_mult(data, rbegin, rend, *data_it);
}
++data;
}
}
时间是通过调用 clock（），以测量它需要多长时间。
The timing is done by calling clock() around a loop to measure how long it takes. Not the most accurate/precise way, but I figured a consistent 25% difference meant the difference was statistically significant.
完整的工作代码块：
#include <vector>
#include <limits>
#include <ctime>
#include <iostream>
typedef unsigned long long ull;
typedef unsigned int uint;
const ull numbits = (ull) std::numeric_limits<uint>::digits;
const ull imax = 1LL << numbits;
static void inline single_mult(const std::vector<ull>::iterator& data,
const std::vector<ull>::const_iterator& rbegin,
const std::vector<ull>::const_iterator& rend,
const ull x) {
ull tmp=0, carry=0, i=0;
for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
tmp = x*(*rhs_it) + data[i] + carry;
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
data[i++] = tmp;
}
data[i] += carry;
}
static void naive(std::vector<ull>::iterator data,
std::vector<ull>::const_iterator cbegin,
std::vector<ull>::const_iterator cend ,
std::vector<ull>::const_iterator rbegin,
std::vector<ull>::const_iterator rend) {
for (auto data_it = cbegin; data_it != cend; ++data_it) {
if (*data_it != 0) {
single_mult(data, rbegin, rend, *data_it);
}
++data;
}
}
int main() {
int N = 10000;
std::vector<ull> vec(N);
for (int i=0; i<N; ++i) {
vec[i] = i;
}
auto s1 = clock();
int num = 10;
std::vector<ull> result(2*N);
for (int i=0; i<num; ++i) {
//Need to zero out the vector or the result will be different.
std::fill(result.begin(), result.end(), 0);
naive(result.begin(), vec.cbegin(), vec.cend(), vec.cbegin(), vec.cend());
}
s1 = (clock() - s1);
std::cout << "Took " << float(s1)/CLOCKS_PER_SEC << "seconds total." << std::endl;
}
和运行时（我命名的文件传递值 value.cpp 和参考 reference.cpp ）
And runtimes (I named the file that passes the value value.cpp and reference reference.cpp)
$ g++ -O3 -std=c++11 -g -o reference reference.cpp
$ g++ -O3 -std=c++11 -g -o value value.cpp
$ ./reference
Took 1.05seconds total.
$ ./value
Took 1.83seconds total.
推荐答案
我能够重现你对加速的观察，它甚至更明显的我（1.75倍更快）。问题似乎是，当你通过值传递x它使编译器执行优化，否则不会做，这些优化反过来，他们显然在处理器中引入了意外的停顿。编译器生成几个条件移动，背靠背，而不是比较和分支。比较和分支运行速度比背靠背条件移动快得多。
I was able to reproduce your observation of the speedup, it was even more noticeable for me (1.75x faster). The problem seems to be when you pass x by value it enables the compiler to perform optimizations that it otherwise doesn't do, and these optimizations backfire, they apparently introduce an unintended stall in the processor. The compiler generates a couple of conditional moves, back to back, rather than compare and branch. The compare and branch runs much faster than the back-to-back conditional moves.
我能够通过简化编译器遇到的麻烦的代码来避免这种情况，即
I was able to avoid this by simplifying the code that the compiler had trouble with, namely this
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
可以减少到
carry = tmp >> numbits;
tmp &= imax - 1;
以下是我使用的gcc版本：
Here's the version of gcc I'm using
g++ --version
g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)
这些是我使用的命令， perf record 将配置您的代码和 perf
These are the commands I used, perf record will profile your code and perf report will annotate the source and disassembly with the results of the profile
g++ -std=gnu++0x -O3 -g single_mult.cpp -o single_mult
perf record ./single_mult
perf report
在perf报告中按在，然后选择主上输入 ，您将看到程序的反汇编和源代码以及分析器发现程序在函数中的每个指令处运行的时间百分比...实际上这些数字必须作为只有提示，通常你会看到大计数的指令，事实上，它是以前的指令被停滞，或错过了缓存，或有一个误预测的分支，等等。所以，当你看到一个大计数回头看看什么可能造成它。原因是该配置文件是统计的，它以恒定速率中断您的程序，并查看指令指针在哪里，并且通常当处理器由于高速缓存未命中或错误预测的分支或某些内部数据依赖。
Once in perf report press enter on main and select Annotate main, you'll see a disassembly of your program along with source code and the percent of the time the profiler found your program running at each instruction in the function... actually these numbers must be taken as a hint only, often you will see instructions with big counts when in fact it was the previous instruction that stalled, or missed in the cache, or there was a mis-predicted branch, etc. So when you see a big count look back to see what may have caused it. The reason is the profile is statistical, it interrupts your program at a constant rate and looks to see where the instruction pointer is, and often the interrupt happens while the processor is stalled due to a cache miss or a mis-predicted branch or some internal data dependency.
我增加了迭代次数以允许更多时间用于分析器。
I increased the number of iterations to allow more time for the profiler
int N = 20000;
当x传递值时， Took 11.58seconds total 这是我看到的，注意 cmovbe 说明
When x is passed by value it Took 11.58seconds total and this is what I see, notice the cmovbe instructions
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
11.10 : 400b40: 4c 89 c9 mov %r9,%rcx
0.00 : 400b43: 48 89 fa mov %rdi,%rdx
0.01 : 400b46: 48 03 14 c6 add (%rsi,%rax,8),%rdx
11.65 : 400b4a: 48 0f af 0c c3 imul (%rbx,%rax,8),%rcx
0.99 : 400b4f: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
2.25 : 400b52: 48 89 d7 mov %rdx,%rdi
: tmp &= imax - 1;
10.99 : 400b55: 48 89 d1 mov %rdx,%rcx
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.69 : 400b58: 48 c1 ef 20 shr $0x20,%rdi
: tmp &= imax - 1;
9.54 : 400b5c: 83 e1 ff and $0xffffffff,%ecx
9.05 : 400b5f: 4c 39 c2 cmp %r8,%rdx
10.78 : 400b62: 49 0f 46 fb cmovbe %r11,%rdi
: } else {
: carry = 0;
: }
: data[i++] = tmp;
20.73 : 400b66: 48 83 c0 01 add $0x1,%rax
0.02 : 400b6a: 4c 39 c2 cmp %r8,%rdx
0.17 : 400b6d: 48 0f 46 ca cmovbe %rdx,%rcx
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
11.47 : 400b71: 4c 39 d0 cmp %r10,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.01 : 400b74: 48 89 4c c6 f8 mov %rcx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b79: 75 c5 jne 400b40 <main+0x250>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b7b: 4a 01 3c d6 add %rdi,(%rsi,%r10,8)
0.01 : 400b7f: 48 83 c5 08 add $0x8,%rbp
当x通过引用传递时， Took总共6.59秒我看到
When x is passed by reference it Took 6.59seconds total, this is what I see
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
20.90 : 400b30: 48 8b 17 mov (%rdi),%rdx
: tmp = x*(*rhs_it) + data[i] + carry;
1.38 : 400b33: 49 0f af 14 c1 imul (%r9,%rax,8),%rdx
4.82 : 400b38: 48 03 0c c6 add (%rsi,%rax,8),%rcx
22.41 : 400b3c: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
2.95 : 400b3f: 31 c9 xor %ecx,%ecx
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
0.23 : 400b41: 4c 39 d2 cmp %r10,%rdx
0.00 : 400b44: 76 0a jbe 400b50 <main+0x260>
: carry = tmp >> numbits;
2.27 : 400b46: 48 89 d1 mov %rdx,%rcx
: tmp &= imax - 1;
1.29 : 400b49: 83 e2 ff and $0xffffffff,%edx
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.26 : 400b4c: 48 c1 e9 20 shr $0x20,%rcx
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
19.67 : 400b50: 48 83 c0 01 add $0x1,%rax
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b54: 4c 39 c0 cmp %r8,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.39 : 400b57: 48 89 54 c6 f8 mov %rdx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
22.91 : 400b5c: 75 d2 jne 400b30 <main+0x240>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b5e: 4a 01 0c c6 add %rcx,(%rsi,%r8,8)
0.00 : 400b62: 48 83 c7 08 add $0x8,%rdi
这篇关于为什么在函数参数中改变`const ull`到`const ull&`会导致性能增益？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
