用64位替换32位循环计数器会导致英特尔CPU上_mm_popcnt_u64的疯狂性能偏差
我正在寻找popcount大型数据数组的最快方法。我遇到了非常奇怪效果：将循环变量从unsigned更改为uint64_t使我的PC性能下降了50%。
基准
#include <iostream>#include <chrono>#include <x86intrin.h>
int main(int argc, char* argv[]) {
using namespace std;if (argc != 2) {cerr << "usage: array_size in MB" << endl;return -1;}
uint64_t size = atol(argv[1])<<20;uint64_t* buffer = new uint64_t[size/8];char* charbuffer = reinterpret_cast<char*>(buffer);for (unsigned i=0; i<size; ++i)charbuffer[i] = rand()%256;
uint64_t count,duration;chrono::time_point<chrono::system_clock> startP,endP;{startP = chrono::system_clock::now();count = 0;for( unsigned k = 0; k < 10000; k++){// Tight unrolled loop with unsignedfor (unsigned i=0; i<size/8; i+=4) {count += _mm_popcnt_u64(buffer[i]);count += _mm_popcnt_u64(buffer[i+1]);count += _mm_popcnt_u64(buffer[i+2]);count += _mm_popcnt_u64(buffer[i+3]);}}endP = chrono::system_clock::now();duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"<< (10000.0*size)/(duration) << " GB/s" << endl;}{startP = chrono::system_clock::now();count=0;for( unsigned k = 0; k < 10000; k++){// Tight unrolled loop with uint64_tfor (uint64_t i=0;i<size/8;i+=4) {count += _mm_popcnt_u64(buffer[i]);count += _mm_popcnt_u64(buffer[i+1]);count += _mm_popcnt_u64(buffer[i+2]);count += _mm_popcnt_u64(buffer[i+3]);}}endP = chrono::system_clock::now();duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();cout << "uint64_t\t" << count << '\t' << (duration/1.0E9) << " sec \t"<< (10000.0*size)/(duration) << " GB/s" << endl;}
free(charbuffer);}如你所见，我们创建了一个随机数据缓冲区，大小为x兆字节，从命令行读取x。之后，我们迭代缓冲区，并使用x86popcount内部的展开版本来执行popcoun。为了得到更精确的结果，我们做了10,000次popcoun。我们测量popcoun的时间。在大写情况下，内循环变量是unsigned，在小写情况下，内循环变量是uint64_t。我认为这应该没有区别，但情况恰恰相反。
（绝对疯狂的）结果
我这样编译（g++版本：Ubuntu 4.8.2-19ubuntu1）：
g++ -O3 -march=native -std=c++11 test.cpp -o test以下是我的HaswellCore i7-4770K CPU@3.50 GHz的结果，运行test 1（所以1 MB随机数据）：
- 无符号419593600000.401554 sec26.113 GB/s
- uint64_t419593600000.759822秒13.8003 GB/s
如你所见，uint64_t版本的吞吐量是只有一半unsigned版本的吞吐量！问题似乎是生成了不同的程序集，但为什么呢？首先，我想到了一个编译器bug，所以我尝试了clang++（UbuntuClang版本3.4-1ubuntu3）：
clang++ -O3 -march=native -std=c++11 teest.cpp -o test结果：test 1
- 无符号419593600000.398293 sec26.3267 GB/s
- uint64_t419593600000.680954秒15.3986 GB/s
但现在它变得超级奇怪。我用常量1替换从输入读取的缓冲区大小，所以我改变了：
uint64_t size = atol(argv[1]) << 20;来
uint64_t size = 1 << 20;因此，编译器现在在编译时知道缓冲区大小。也许它可以添加一些优化！
- 无符号419593600000.509156秒20.5944 GB/s
- uint64_t419593600000.508673秒20.6139 GB/s
现在，两个版本都同样快。然而，unsigned变得更慢！它从26下降到20 GB/s，因此用常量值替换非常量导致去优化。说真的，我不知道这里发生了什么！但现在到新版本的clang++：
- 无符号419593600000.677009 sec15.4884 GB/s
- uint64_t419593600000.676909秒15.4906 GB/s
等等，什么？现在，两个版本都降至15 GB/s的缓慢数字。因此，用常量值替换非常量甚至会导致Clang的两者情况下代码速度慢！
我请一位CPU常春藤桥的同事编译我的基准测试。他得到了类似的结果，所以似乎不是Haswell。因为两个编译器在这里产生奇怪的结果，所以它似乎也不是编译器bug。我们这里没有AMD CPU，所以我们只能用英特尔进行测试。
更多的疯狂，请！
以第一个例子（带有atol(argv[1])的那个）为例，在变量之前放一个static，即：
static uint64_t size=atol(argv[1])<<20;以下是我在g++中的结果：
- 无符号419593600000.396728 sec26.4306 GB/s
- uint64_t419593600000.509484秒20.5811 GB/s
耶，又一个选择。我们仍然有u32的快速26 GB/s，但我们设法至少从13 GB/s到20 GB/s版本获得了u64！在我同事的PC上，#1版本变得比#0版本更快，产生了最快的结果。可悲的是，这只适用于g++，clang++似乎并不关心static。
我的问题
你能解释一下这些结果吗？特别是：
u32和u64之间怎么会有这样的区别？- 如何用常量缓冲区大小触发器次优代码替换非常量？
- 插入
static关键字如何使u64循环更快？甚至比我同事电脑上的原始代码还要快！
我知道优化是一个棘手的领域，然而，我从未想过如此小的更改会导致执行时间100%的差异，并且像恒定的缓冲区大小这样的小因素会再次完全混合结果。当然，我一直希望拥有能够弹出26 GB/s的版本。我能想到的唯一可靠的方法是针对这种情况复制粘贴程序集并使用内联汇编。这是我摆脱似乎在小更改上疯狂的编译器的唯一方法。你觉得呢？有没有其他方法可以可靠地获得性能最高的代码？
的拆解
以下是对各种结果的分解：
来自g++/u32/un-const bufsize自定义函数的26 GB/s版本：
0x400af8:lea 0x1(%rdx),%eaxpopcnt (%rbx,%rax,8),%r9lea 0x2(%rdx),%edipopcnt (%rbx,%rcx,8),%raxlea 0x3(%rdx),%esiadd %r9,%raxpopcnt (%rbx,%rdi,8),%rcxadd $0x4,%edxadd %rcx,%raxpopcnt (%rbx,%rsi,8),%rcxadd %rcx,%raxmov %edx,%ecxadd %rax,%r14cmp %rbp,%rcxjb 0x400af813 GB/s版本从g++u64/un-const bufsize自定义函数：
0x400c00:popcnt 0x8(%rbx,%rdx,8),%rcxpopcnt (%rbx,%rdx,8),%raxadd %rcx,%raxpopcnt 0x10(%rbx,%rdx,8),%rcxadd %rcx,%raxpopcnt 0x18(%rbx,%rdx,8),%rcxadd $0x4,%rdxadd %rcx,%raxadd %rax,%r12cmp %rbp,%rdxjb 0x400c0015 GB/s版本从clang++/u64/un-const bufsize核心组件配置：
0x400e50:popcnt (%r15,%rcx,8),%rdxadd %rbx,%rdxpopcnt 0x8(%r15,%rcx,8),%rsiadd %rdx,%rsipopcnt 0x10(%r15,%rcx,8),%rdxadd %rsi,%rdxpopcnt 0x18(%r15,%rcx,8),%rbxadd %rdx,%rbxadd $0x4,%rcxcmp %rbp,%rcxjb 0x400e5020 GB/s版本从g++/u32&u64/const bufsize自定义参数：
0x400a68:popcnt (%rbx,%rdx,1),%raxpopcnt 0x8(%rbx,%rdx,1),%rcxadd %rax,%rcxpopcnt 0x10(%rbx,%rdx,1),%raxadd %rax,%rcxpopcnt 0x18(%rbx,%rdx,1),%rsiadd $0x20,%rdxadd %rsi,%rcxadd %rcx,%rbpcmp $0x100000,%rdxjne 0x400a6815 GB/s版本从：
0x400dd0:popcnt (%r14,%rcx,8),%rdxadd %rbx,%rdxpopcnt 0x8(%r14,%rcx,8),%rsiadd %rdx,%rsipopcnt 0x10(%r14,%rcx,8),%rdxadd %rsi,%rdxpopcnt 0x18(%r14,%rcx,8),%rbxadd %rdx,%rbxadd $0x4,%rcxcmp $0x20000,%rcxjb 0x400dd0有趣的是，最快的（26 GB/s）版本也是最长的！它似乎是唯一使用lea的解决方案。有些版本使用jb跳转，有些版本使用jne。但除此之外，所有版本似乎都具有可比性。我不知道100%的性能差距是从哪里来的，但我不太擅长破译汇编。最慢的（13 GB/s）版本看起来甚至很短，很好。有人能解释一下吗？
吸取的教训
不管这个问题的答案是什么；我已经了解到，在真正的热循环中每细节可能很重要，甚至看起来与热代码没有任何关联的细节。我从来没有想过要为循环变量使用什么类型，但是正如你所看到的那样，这样的微小变化可以产生百分之百的差异！即使是缓冲区的存储类型也可以产生巨大的差异，正如我们在大小变量前面插入static关键字所看到的那样！将来，当编写对系统性能至关重要的真正紧密和热循环时，我将始终在各种编译器上测试各种替代方案。
有趣的是，尽管我已经展开了四次循环，但性能差异仍然很高。所以即使你展开，你仍然会受到主要性能偏差的影响。非常有趣。
最佳答案