我一直在寻找处理popcount大量数据的最快方法。我遇到了一个非常奇怪的效果：将循环变量从更改unsigned为uint64_t使我的 PC 上的性能下降了 50%。
popcount
unsigned
uint64_t
#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 unsigned for (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_t for (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内部函数的展开版本来执行 popcount。为了获得更精确的结果，我们执行 popcount 10,000 次。我们测量 popcount 的时间。在大写情况下，内部循环变量是unsigned，在小写情况下，内部循环变量是uint64_t。我认为这应该没有什么区别，但情况恰恰相反。
x
我这样编译它（g++版本：Ubuntu 4.8.2-19ubuntu1）：
g++ -O3 -march=native -std=c++11 test.cpp -o test
这是我的Haswell Core i7-4770K CPU @ 3.50 GHz 上运行的结果test 1（所以 1 MB 随机数据）：
test 1
如您所见，版本的吞吐量只有uint64_t版本的一半unsigned！问题似乎是生成了不同的程序集，但为什么呢？首先想到了一个编译器的bug，于是试了一下clang++（Ubuntu Clang version 3.4-1ubuntu3）：
clang++
clang++ -O3 -march=native -std=c++11 teest.cpp -o test
结果：test 1
所以，这几乎是相同的结果，但仍然很奇怪。但现在它变得超级奇怪。我用一个常量替换了从输入中读取的缓冲区大小1，所以我改变了：
1
uint64_t size = atol(argv[1]) << 20;
到
uint64_t size = 1 << 20;
因此，编译器现在在编译时就知道缓冲区大小。也许它可以添加一些优化！以下是 的数字g++：
g++
现在，两个版本都同样快。但是，unsigned 速度变得更慢了！它从 下降26到20 GB/s，因此用常数值替换非常数会导致去优化。说真的，我不知道这里发生了什么！但现在clang++有了新版本：
26
20 GB/s
等等，什么？现在，这两个版本都下降到了15 GB/s 的缓慢数字。因此，在Clang的两种情况下，用常数值替换非常数甚至会导致代码变慢！
我请一位使用Ivy Bridge CPU 的同事编译我的基准测试。他得到了类似的结果，所以似乎不是Haswell。因为两个编译器在这里产生了奇怪的结果，所以它似乎也不是编译器的错误。我们这里没有 AMD CPU，所以我们只能用 Intel 进行测试。
以第一个示例（带有 的示例atol(argv[1])）并将 a 放在static变量之前，即：
atol(argv[1])
static
static uint64_t size=atol(argv[1])<<20;
这是我在 g++ 中的结果：
是的，还有另一种选择。我们仍然拥有快速的 26 GB/s版本u32，但我们设法u64至少从 13 GB/s 到 20 GB/s 版本！在我同事的 PC 上，该u64版本变得比该u32版本更快，产生了最快的结果。可悲的是，这只适用于g++，clang++似乎并不关心static。
u32
u64
你能解释一下这些结果吗？尤其：
我知道优化是一个棘手的领域，但是，我从没想过如此小的变化会导致执行时间出现100% 的差异，并且像恒定缓冲区大小这样的小因素会再次完全混合结果。当然，我一直希望拥有能够popcount 26 GB/s 的版本。我能想到的唯一可靠的方法是复制粘贴这种情况下的程序集并使用内联程序集。这是我可以摆脱那些似乎对小改动发疯的编译器的唯一方法。你怎么看？还有另一种方法可以可靠地获得性能最高的代码吗？
以下是各种结果的反汇编：
来自g++ / u32 / non-const bufsize的 26 GB/s 版本：
0x400af8: lea 0x1(%rdx),%eax popcnt (%rbx,%rax,8),%r9 lea 0x2(%rdx),%edi popcnt (%rbx,%rcx,8),%rax lea 0x3(%rdx),%esi add %r9,%rax popcnt (%rbx,%rdi,8),%rcx add $0x4,%edx add %rcx,%rax popcnt (%rbx,%rsi,8),%rcx add %rcx,%rax mov %edx,%ecx add %rax,%r14 cmp %rbp,%rcx jb 0x400af8
来自g++ / u64 / non-const bufsize的 13 GB/s 版本：
0x400c00: popcnt 0x8(%rbx,%rdx,8),%rcx popcnt (%rbx,%rdx,8),%rax add %rcx,%rax popcnt 0x10(%rbx,%rdx,8),%rcx add %rcx,%rax popcnt 0x18(%rbx,%rdx,8),%rcx add $0x4,%rdx add %rcx,%rax add %rax,%r12 cmp %rbp,%rdx jb 0x400c00
来自clang++ / u64 / non-const bufsize的 15 GB/s 版本：
0x400e50: popcnt (%r15,%rcx,8),%rdx add %rbx,%rdx popcnt 0x8(%r15,%rcx,8),%rsi add %rdx,%rsi popcnt 0x10(%r15,%rcx,8),%rdx add %rsi,%rdx popcnt 0x18(%r15,%rcx,8),%rbx add %rdx,%rbx add $0x4,%rcx cmp %rbp,%rcx jb 0x400e50
来自g++ / u32&u64 / const bufsize的 20 GB/s 版本：
0x400a68: popcnt (%rbx,%rdx,1),%rax popcnt 0x8(%rbx,%rdx,1),%rcx add %rax,%rcx popcnt 0x10(%rbx,%rdx,1),%rax add %rax,%rcx popcnt 0x18(%rbx,%rdx,1),%rsi add $0x20,%rdx add %rsi,%rcx add %rcx,%rbp cmp $0x100000,%rdx jne 0x400a68
来自clang++ / u32&u64 / const bufsize的 15 GB/s 版本：
0x400dd0: popcnt (%r14,%rcx,8),%rdx add %rbx,%rdx popcnt 0x8(%r14,%rcx,8),%rsi add %rdx,%rsi popcnt 0x10(%r14,%rcx,8),%rdx add %rsi,%rdx popcnt 0x18(%r14,%rcx,8),%rbx add %rdx,%rbx add $0x4,%rcx cmp $0x20000,%rcx jb 0x400dd0
有趣的是，最快（26 GB/s）的版本也是最长的！它似乎是唯一使用lea. 有些版本用于jb跳转，有些版本使用jne. 但除此之外，所有版本似乎都具有可比性。我看不出 100% 的性能差距可能来自哪里，但我不太擅长破译汇编。最慢的 (13 GB/s) 版本看起来甚至非常短而且很好。谁能解释一下？
lea
jb
jne
不管这个问题的答案是什么；我了解到，在真正的热循环中，每个细节都很重要，即使是似乎与热代码没有任何关联的细节。我从来没有想过要为循环变量使用什么类型，但正如您所见，如此小的变化可以产生100%的不同！甚至缓冲区的存储类型也会产生巨大的差异，正如我们static在 size 变量前面插入关键字时看到的那样！将来，在编写对系统性能至关重要的非常紧且热的循环时，我将始终在各种编译器上测试各种替代方案。
有趣的是，尽管我已经展开了四次循环，但性能差异仍然如此之大。因此，即使展开，您仍然会受到主要性能偏差的影响。很有趣。
罪魁祸首：错误的数据依赖（编译器甚至没有意识到）
在 Sandy/Ivy Bridge 和 Haswell 处理器上，指令：
popcnt src, dest
似乎对目标寄存器有错误的依赖性dest。即使指令只写入它，指令也会等到dest准备好后再执行。这种错误的依赖关系（现在）被英特尔记录为 erratum HSD146 (Haswell)和SKL029 (Skylake)
dest
Skylake 为lzcnt和tzcnt修复了此问题。 大炮湖（和冰湖）修复了这个问题popcnt。bsf/bsr`具有真正的输出依赖性：输入=0 时未修改输出。（但没有办法利用内在函数来利用它——只有 AMD 记录了它，编译器不公开它。）
lzcnt
tzcnt修复了此问题。 大炮湖（和冰湖）修复了这个问题
。
/
这种依赖关系不仅仅阻止了popcnt单次循环迭代的 4 秒。它可以进行循环迭代，从而使处理器无法并行化不同的循环迭代。
popcnt
unsignedvs.和uint64_t其他调整不会直接影响问题。但是它们会影响将寄存器分配给变量的寄存器分配器。
在您的情况下，速度是卡在（错误）依赖链上的直接结果，具体取决于寄存器分配器决定做什么。
add
20 GB/s 和 26 GB/s 之间的差异似乎是间接寻址的次要伪影。无论哪种方式，一旦达到这个速度，处理器就会开始遇到其他瓶颈。
为了测试这一点，我使用内联汇编绕过编译器并得到我想要的汇编。我还拆分了count变量以打破所有其他可能与基准测试混淆的依赖项。
count
结果如下：
Sandy Bridge Xeon @ 3.5 GHz：（完整的测试代码可以在底部找到）
g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
不同的寄存器：18.6195 GB/s
.L4: movq (%rbx,%rax,8), %r8 movq 8(%rbx,%rax,8), %r9 movq 16(%rbx,%rax,8), %r10 movq 24(%rbx,%rax,8), %r11 addq $4, %rax popcnt %r8, %r8 add %r8, %rdx popcnt %r9, %r9 add %r9, %rcx popcnt %r10, %r10 add %r10, %rdi popcnt %r11, %r11 add %r11, %rsi cmpq $131072, %rax jne .L4
相同寄存器：8.49272 GB/s
.L9: movq (%rbx,%rdx,8), %r9 movq 8(%rbx,%rdx,8), %r10 movq 16(%rbx,%rdx,8), %r11 movq 24(%rbx,%rdx,8), %rbp addq $4, %rdx # This time reuse "rax" for all the popcnts. popcnt %r9, %rax add %rax, %rcx popcnt %r10, %rax add %rax, %rsi popcnt %r11, %rax add %rax, %r8 popcnt %rbp, %rax add %rax, %rdi cmpq $131072, %rdx jne .L9
具有断链的相同寄存器：17.8869 GB/s
.L14: movq (%rbx,%rdx,8), %r9 movq 8(%rbx,%rdx,8), %r10 movq 16(%rbx,%rdx,8), %r11 movq 24(%rbx,%rdx,8), %rbp addq $4, %rdx # Reuse "rax" for all the popcnts. xor %rax, %rax # Break the cross-iteration dependency by zeroing "rax". popcnt %r9, %rax add %rax, %rcx popcnt %r10, %rax add %rax, %rsi popcnt %r11, %rax add %rax, %r8 popcnt %rbp, %rax add %rax, %rdi cmpq $131072, %rdx jne .L14
那么编译器出了什么问题呢？
似乎 GCC 和 Visual Studio 都没有意识到popcnt有这样一个错误的依赖关系。然而，这些错误的依赖并不少见。这只是编译器是否意识到它的问题。
popcnt并不是最常用的指令。因此，一个主要的编译器可能会错过这样的事情并不奇怪。似乎也没有任何文件提到这个问题。如果英特尔不透露，那么外界不会知道，除非有人偶然碰到它。
（更新： 从 4.9.2 版开始，GCC 意识到了这种错误依赖，并在启用优化时生成代码来补偿它。其他供应商的主要编译器，包括 Clang、MSVC，甚至 Intel 自己的 ICC 还没有意识到这个微架构错误并且不会发出补偿它的代码。）
为什么 CPU 会有这种错误的依赖？
bsf我们可以推测：它运行在与/相同的执行单元上，bsr它确实具有输出依赖性。POPCNT如何在硬件中实现？。对于这些指令，英特尔将 input=0 的整数结果记录为“未定义”（ZF=1），但英特尔硬件实际上提供了更强大的保证来避免破坏旧软件：未修改输出。AMD 记录了这种行为。
bsf
bsr
据推测，让这个执行单元的一些微指令依赖于输出，而其他微指令不依赖于输出，这在某种程度上是不方便的。
AMD 处理器似乎没有这种错误的依赖性。
完整的测试代码如下供参考：
#include <iostream> #include <chrono> #include <x86intrin.h> int main(int argc, char* argv[]) { using namespace std; uint64_t size=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; { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "popcnt %4, %4 \n\t" "add %4, %0 \n\t" "popcnt %5, %5 \n\t" "add %5, %1 \n\t" "popcnt %6, %6 \n\t" "add %6, %2 \n\t" "popcnt %7, %7 \n\t" "add %7, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "popcnt %4, %%rax \n\t" "add %%rax, %0 \n\t" "popcnt %5, %%rax \n\t" "add %%rax, %1 \n\t" "popcnt %6, %%rax \n\t" "add %%rax, %2 \n\t" "popcnt %7, %%rax \n\t" "add %%rax, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) : "rax" ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "Chain 4 \t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "xor %%rax, %%rax \n\t" // <--- Break the chain. "popcnt %4, %%rax \n\t" "add %%rax, %0 \n\t" "popcnt %5, %%rax \n\t" "add %%rax, %1 \n\t" "popcnt %6, %%rax \n\t" "add %%rax, %2 \n\t" "popcnt %7, %%rax \n\t" "add %%rax, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) : "rax" ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "Broken Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } free(charbuffer); }
在这里可以找到一个同样有趣的基准：http: //pastebin.com/kbzgL8si 这个基准改变了popcnt（假）依赖链中的 s 的数量。
False Chain 0: 41959360000 0.57748 sec 18.1578 GB/s False Chain 1: 41959360000 0.585398 sec 17.9122 GB/s False Chain 2: 41959360000 0.645483 sec 16.2448 GB/s False Chain 3: 41959360000 0.929718 sec 11.2784 GB/s False Chain 4: 41959360000 1.23572 sec 8.48557 GB/s
