我一直在寻找快速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 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从命令行读取。之后，我们遍历缓冲区并使用 x86 popcount内在的展开版本来执行 popcount。为了获得更精确的结果，我们做了 10,000 次 popcount。我们测量 popcount 的时间。在大写的情况下，内部循环变量是unsigned ，在小写的情况下，内部循环变量是uint64_t 。我认为这应该没有区别，但事实恰恰相反。
我像这样编译它（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 随机数据）：
如您所见， uint64_t版本的吞吐量仅为 unsigned版本的一半 ！问题似乎是生成了不同的程序集，但为什么呢？首先，我想到了编译器错误，所以我尝试了clang++ （Ubuntu Clang版本 3.4-1ubuntu3）：
clang++ -O3 -march=native -std=c++11 teest.cpp -o test结果： test 1
所以，它几乎是相同的结果，仍然很奇怪。 但现在它变得非常奇怪。我用常量1替换从输入读取的缓冲区大小，所以我改变：
uint64_t size = atol(argv[1]) << 20;至
uint64_t size = 1 << 20;因此，编译器现在知道编译时的缓冲区大小。也许它可以添加一些优化！以下是g++的数字：
现在，两个版本都同样快。然而， unsigned 变得更慢 ！它从26降至20 GB/s ，因此将非常数替换为常数值会导致去优化 。说真的，我不知道这里发生了什么！但现在要用新版clang++ ：
等等，什么？现在，两个版本的速度都降至 15 GB / s。因此，对于 Clang 来说，将两个非常数替换为常数值甚至会导致代码速度变慢！
我问一位有Ivy Bridge CPU 的同事来编译我的基准测试。他得到了类似的结果，所以它似乎不是哈斯威尔。因为这里有两个编译器产生奇怪的结果，所以它似乎也不是编译器错误。我们这里没有 AMD CPU，所以我们只能用 Intel 测试。
以第一个示例（带有atol(argv[1])示例）并在变量之前放置一个static ，即：
static uint64_t size=atol(argv[1])<<20;以下是我在 g ++ 中的结果：
是的，还有另一种选择 。我们仍然有快 26 GB / s 的u32 ，但我们设法u64从 13 GB / s 的至少 20 GB / s 的版本！ 在我 collegue 的 PC 中， u64版本变得比更快u32版本，产生所有的最快的结果。可悲的是，这只适用于g++ ， clang++似乎并不关心static 。
你能解释一下这些结果吗？特别：
u32和u64 ？ static关键字使u64循环更快？甚至比同事电脑上的原始代码还要快！ 我知道优化是一个棘手的领域，但是，我从未想过这么小的变化会导致执行时间的100％差异 ，并且像缓冲区大小一样的小因素可以再次完全混合结果。当然，我总是想拥有能够突破 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）版本看起来甚至非常简短。有谁能解释一下？
无论这个问题的答案是什么; 我已经了解到，在非常热的循环中， 每个细节都很重要， 甚至细节似乎与热代码没有任何关联 。我从来没有想过用于循环变量的类型，但正如您所看到的那样，这种微小的变化可以产生100％的差异！即使是缓冲区的存储类型也会产生巨大的差异，正如我们在 size 变量前面插入static关键字所看到的那样！将来，在编写对系统性能至关重要的真正紧密和热循环时，我将始终在各种编译器上测试各种替代方案。
有趣的是，尽管我已经将循环展开了四次，但性能差异仍然很高。因此，即使您展开，您仍然会受到主要性能偏差的影响。很有趣。
罪魁祸首：虚假数据依赖 （并且编译器甚至不知道它）
在 Sandy / Ivy Bridge 和 Haswell 处理器上，指令：
popcnt src, dest似乎对目标寄存器dest具有错误的依赖性。即使指令只写入它，指令也会等到dest准备好后再执行。
这种依赖性不仅仅会阻止单个循环迭代中的 4 个popcnt 。它可以进行循环迭代，使得处理器不可能并行化不同的循环迭代。
unsigned与uint64_t和其他调整不会直接影响问题。但它们影响寄存器分配器，它将寄存器分配给变量。
在您的情况下，速度是固定（假）依赖链的直接结果，具体取决于寄存器分配器决定做什么。
popcnt - add - popcnt - popcnt →下一次迭代popcnt - add - popcnt - add →next iteration popcnt - popcnt →下一次迭代popcnt - popcnt →下一次迭代20 GB / s 和 26 GB / s 之间的差异似乎是间接寻址的一个小工件。无论哪种方式，一旦达到此速度，处理器就会开始遇到其他瓶颈。
为了测试这个，我使用内联汇编绕过编译器并获得我想要的精确程序集。我还拆分了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，甚至是英特尔自己的 ICC，还不知道这个微体系结构的错误，不会发出补偿它的代码。）
为什么 CPU 有这样的错误依赖？
我们只能推测，但英特尔对很多双操作数指令的处理可能相同。像add ， sub这样的常用指令带有两个操作数，这两个操作数都是输入。因此，英特尔可能popcnt推入同一类别，以保持处理器设计的简单性。
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数。
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我编写了一个等效的 C 程序进行实验，我可以证实这种奇怪的行为。更重要的是， gcc认为 64 位整数（无论如何应该是size_t ......）更好，因为使用uint_fast32_t会导致 gcc 使用 64 位 uint。
我对装配做了一些讨论：
只需使用 32 位版本，将所有 32 位指令 / 寄存器替换为程序内部 popcount-loop 中的 64 位版本。观察：代码和 32 位版本一样快！
这显然是一个 hack，因为变量的大小不是真正的 64 位，因为程序的其他部分仍然使用 32 位版本，但只要内部 popcount-loop 主导性能，这是一个好的开始。
然后我从 32 位版本的程序中复制了内部循环代码，将其破解为 64 位，使用寄存器进行调整，使其成为 64 位版本内部循环的替代品。 此代码的运行速度与 32 位版本一样快。
我的结论是，这是编译器的错误指令调度，而不是 32 位指令的实际速度 / 延迟优势。
（警告：我破坏了装配，可能在没有注意的情况下破坏了一些东西。我不这么认为。）
这不是答案，但如果我将结果置于评论中，则很难理解。
我用Mac Pro （ Westmere 6-Cores Xeon 3.33 GHz）获得了这些结果。我用clang -O3 -msse4 -lstdc++ a.cpp -oa编译它（-O2 得到相同的结果）。
uint64_t size=atol(argv[1])<<20; unsigned 41950110000 0.811198 sec 12.9263 GB/s
uint64_t 41950110000 0.622884 sec 16.8342 GB/suint64_t size=1<<20; unsigned 41950110000 0.623406 sec 16.8201 GB/s
uint64_t 41950110000 0.623685 sec 16.8126 GB/s我也试过：
for语句： for (uint64_t i=size/8;i>0;i-=4) 。这给出了相同的结果，并证明编译足够聪明，不会在每次迭代时将大小除以 8（如预期的那样）。 这是我疯狂的猜测：
速度因素分为三个部分：
代码缓存： uint64_t版本具有更大的代码大小，但这对我的 Xeon CPU 没有影响。这使得 64 位版本变慢。
使用说明。不仅要注意循环计数，还要在两个版本上使用 32 位和 64 位索引访问缓冲区。访问具有 64 位偏移量的指针会请求专用的 64 位寄存器和寻址，而您可以立即使用 32 位偏移量。这可能会使 32 位版本更快。
指令仅在 64 位编译（即预取）上发出。这使得 64 位更快。
这三个因素共同与观察到的看似相互矛盾的结果相匹配。