用64位代替32位循环计数variables引入了疯狂的性能偏差
我正在寻找最快的方式来popcount大量的数据。 我遇到了一个非常奇怪的结果：将循环variables从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); }
如您所见，我们创build了一个随机数据的缓冲区，大小为x兆字节，其中x从命令行读取。 之后，我们遍历缓冲区并使用x86 popcount内在的展开版本来执行popcount。 为了得到更精确的结果，我们做了10,000次的帐户。 我们衡量的时间为popcount。 在大写的情况下，内部循环variables是unsigned ，在小写的情况下，内部循环variables是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随机数据）的结果：
- 无符号41959360000 0.401554秒26.113 GB / s
- uint64_t 41959360000 0.759822秒13.8003 GB / s
如您所见， uint64_t版本的吞吐量只是 unsigned版本的一半 。 问题似乎是不同的程序集生成，但为什么？ 首先，我想到了一个编译器错误，所以我尝试了clang++ （Ubuntu Clang版本3.4-1ubuntu3）：
clang++ -O3 -march=native -std=c++11 teest.cpp -o test
结果： test 1
- 无符号41959360000 0.398293秒26.3267 GB /秒
- uint64_t 41959360000 0.680954秒15.3986 GB / s
所以，几乎是一样的结果，仍然是奇怪的。 但现在它变得非常奇怪。 我用常数1replace从input读取的缓冲区大小，所以我改变了：
uint64_t size = atol(argv[1]) << 20;
至
uint64_t size = 1 << 20;
因此，编译器现在知道编译时的缓冲区大小。 也许它可以添加一些优化！ 这是g++的数字：
- 无符号41959360000 0.509156秒20.5944 GB / s
- uint64_t 41959360000 0.508673秒20.6139 GB / s
现在，两个版本同样快速。 但是， unsigned 更慢了 ！ 它从26下降到20 GB/s ，因此用一个不变的值代替非常数会导致去最优化 。 说真的，我不知道这里发生了什么事情！ 但是现在用新版clang++ ：
- 无符号41959360000 0.677009秒15.4884 GB / s
- uint64_t 41959360000 0.676909秒15.4906 GB / s
等等，什么？ 现在，两个版本都下降到15 GB / s的慢速 。 因此，用一个常量replace一个非常量，在两种情况下都会导致代码变慢。
我问一个有Ivy Bridge CPU的同事来编译我的基准。 他得到了类似的结果，所以它似乎不是Haswell。 由于两个编译器在这里产生了奇怪的结果，它似乎也不是一个编译器错误。 我们这里没有AMD CPU，所以我们只能用英特尔testing。
请更疯狂！
拿第一个例子（带atol(argv[1])例子），并在variables之前加上一个static ，例如：
static uint64_t size=atol(argv[1])<<20;
这是我在g ++中的结果：
- 无符号41959360000 0.396728秒26.4306 GB / s
- uint64_t 41959360000 0.509484秒20.5811 GB / s
是的，又一个select 。 我们的u64速度仍然很快，但是我们至less能够从13 GB / s到20 GB / s的版本获得u64 。 在我的同事的电脑上， u64版本比u64版本更快，产生了最快的结果。 可悲的是，这只适用于g++ ， clang++似乎并不关心static 。
我的问题
你能解释这些结果吗？ 特别：
-
u64和u64之间有什么区别？ - 如何用常量缓冲区大小replace非常量触发不太理想的代码 ？
- 如何插入
static关键字使u64循环更快？ 甚至比我的同事电脑上的原始代码还要快！
我知道优化是一个棘手的领域，但是，我从来没有想过，这样的小改变可以导致100％的执行时间的差异 ，而像恒定的缓冲区大小的小因素可以再次混合结果。 当然，我总是希望拥有能够突破26 GB /秒的版本。 我能想到的唯一可靠的方法就是复制粘贴这个案例的程序集并使用内联程序集。 这是我可以摆脱编译器的唯一方法，这些编译器似乎对于小的变化而生气。 你怎么看？ 有另一种方法可靠地获得最高性能的代码？
拆卸
以下是对各种结果的反汇编：
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
15 GB / s的版本从铿锵++ / u64 /非常量bufsize ：
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中的 20 GB / s版本bufsize ：
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 /秒）版本也是最长的！ 这似乎是使用lea的唯一解决scheme。 有些版本使用jb跳转，其他使用jne 。 但除此之外，所有版本似乎都是可比的。 我没有看到100％的performance差距可能来自哪里，但我并不擅长破译集会。 最慢的（13 GB /秒）版本看起来非常短暂和好。 任何人都可以解释吗？
得到教训
不pipe这个问题的答案是什么， 我已经了解到，在真正的热门循环中， 每个细节都可能很重要， 即使是与热门代码没有任何关联的细节也是如此 。 我从来没有想过用什么types的循环variables，但正如你看到这样一个小的变化可以使100％的差异！ 即使缓冲区的存储types也可以产生巨大的差异，正如我们在staticvariables前插入static关键字所看到的那样！ 将来，在编写对系统性能至关重要的严格和热循环时，我总是会在各种编译器上testing各种替代scheme。
有趣的是，虽然我已经展开了四次循环，但性能差异仍然如此之高。 所以，即使你展开，你仍然可以受到主要performance偏差的打击。 很有趣。
罪魁祸首：错误的数据依赖 （和编译器甚至没有意识到）
在Sandy / Ivy Bridge和Haswell处理器上，指令如下：
popcnt src, dest
似乎对目标寄存器dest有一个错误的依赖关系。 即使指令只写入指令，指令也会等待，直到dest准备就绪，然后执行。
这种依赖性不会从一个循环迭代中保留4个popcnt 。 它可以进行循环迭代，使得处理器不可能并行化不同的循环迭代。
unsigned与uint64_t和其他调整不直接影响问题。 但是它们会影响将寄存器赋值给variables的寄存器分配器。
在你的情况下，速度是根据寄存器分配器决定做什么而被（虚拟）依赖关系链卡住的直接结果。
- 13 GB / s有一个链：
popcnt–add–popcnt–popcnt→下一个迭代 - 15 GB / s有一个链：
popcnt–add–popcnt–add– next迭代 - 20 GB / s有一个链：
popcnt–popcnt→下一个迭代 - 26 GB / s有一个链：
popcnt–popcnt→下一个迭代
20 GB /秒和26 GB /秒之间的差别似乎是间接寻址的次要人为因素。 无论哪种方式，一旦你达到这个速度，处理器开始遇到其他瓶颈。
为了testing这个，我使用内联汇编绕过编译器，并得到我想要的程序集。 我也分裂了countvariables来打破可能混淆基准的所有其他依赖。
结果如下：
Sandy Bridge Xeon @ 3.5 GHz：（完整的testing代码可以在底部find）
- GCC 4.6.3：
g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native - Ubuntu 12
不同的寄存器： 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有这样一个错误的依赖关系。 不过，这些错误的依赖并不less见。 这只是编译器是否知道它的问题。
popcnt并不是最常用的指令。 所以一个主要的编译器可能会错过这样的内容并不令人吃惊。 似乎没有任何文件提到这个问题。 如果英特尔没有透露，那么除非有人偶然遇到这个问题，否则外面的人都不会知道。
（ 更新： 从版本4.9.2开始 ，GCC意识到这种错误依赖性，并在启用优化时生成代码来对其进行补偿。来自其他供应商（包括Clang，MSVC，甚至Intel自己的ICC）的主要编译器还不知道这个微架构错误，并不会发出代码补偿它。）
为什么CPU有这种错误的依赖？
我们只能推测，但是对于大量的双操作指令来说，英特尔可能也有相同的处理方式。 像add ， add这样的通用指令需要两个操作数，这两个操作数都是input。 因此，英特尔可能popcnt推向相同的类别，以保持处理器devise的简单性。
AMD处理器似乎没有这种错误的依赖。
完整的testing代码在下面供参考：
#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); }
一个同样有趣的基准可以在这里find： 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位版本，用程序的内部popup窗口循环中的64位版本replace所有的32位指令/寄存器。 观察：代码与32位版本一样快！
这显然是一个黑客，因为variables的大小不是真的64位，因为程序的其他部分仍然使用32位版本，但只要内部popup式循环支配性能，这是一个很好的开始。
然后，我从32位版本的程序中复制了内部循环代码，将其破译为64位，与寄存器混杂在一起，使其成为64位版本内部循环的替代品。 该代码的运行速度也与32位版本一样快。
我的结论是，这是编译器的错误指令调度，而不是32位指令的实际速度/延迟优势。
（警告：我捣乱了集会，可能没有注意到就打破了一些东西，我不这么认为）
这不是一个答案，但如果我把结果发表评论，则很难阅读。
我用Mac Pro （ Westmere 6-Cores Xeon 3.33 GHz）得到了这些结果。 我用clang -O3 -msse4 -lstdc++ a.cpp -oa编译clang -O3 -msse4 -lstdc++ a.cpp -oa （-O2得到相同的结果）。
clang with 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/s
铿锵与uint64_t size=1<<20;
unsigned 41950110000 0.623406 sec 16.8201 GB/s uint64_t 41950110000 0.623685 sec 16.8126 GB/s
我也试图：
- 颠倒testing顺序，结果是一样的，所以它排除了caching因素。
- 有
for语句反向：for (uint64_t i=size/8;i>0;i-=4)。 这给出了相同的结果，并certificate编译足够聪明，不会每次迭代（按预期）将大小除以8。
这是我疯狂的猜测：
速度因素分三部分：
-
代码caching：
uint64_t版本具有较大的代码大小，但是这对我的Xeon CPU没有影响。 这使得64位版本变慢。 -
使用说明。 不仅要注意循环次数，而且还要在两个版本上使用32位和64位索引来访问缓冲区。 访问一个64位偏移量的指针会请求专用的64位寄存器和地址，而32位偏移量则可以使用立即数。 这可能会使32位版本更快。
-
指令仅在64位编译时发出（即预取）。 这使得64位更快。
这三个因素一起与观察到的看似矛盾的结果相匹配。
我不能给出一个权威的答案，但提供一个可能的原因概述。 这个参考很清楚地表明，对于循环体中的指令，延迟和吞吐量之间有3：1的比例。 它也显示了多次调度的效果。 由于在现代x86处理器中有三个整数单元，所以通常可以在每个周期分派三个指令。
因此，在峰值stream水线和多个调度性能和这些机制的失败之间，我们有六个性能因素。 众所周知，x86指令集的复杂性使其非常容易发生奇怪的破坏。 上面的文档有一个很好的例子：
64位右移的Pentium 4性能非常差。 64位左移以及所有32位移位都具有可接受的性能。 看来ALU的高32位到低32位的数据pathdevise不好。
我个人遇到了一个奇怪的例子，一个四核芯片的特定核心（AMD，如果我记得）热循环运行速度相当慢。 实际上，通过closures核心，我们在地图缩减计算上获得了更好的性能。
在这里，我猜测的是整数单元的争用：对于popcnt计数器， popcnt ，循环计数器和地址计算都可以全速运行，但是64位计数器会导致争用和stream水线延迟。 由于总共只有大约12个周期，潜在的4个周期和多个调度，每个循环体执行，单个失速可以合理地影响运行时间2倍。
使用一个静态variables引起的变化，我猜测只是导致对指令的一个小的重新sorting，另一个线索是32位代码处于争用的某个临界点。
我知道这不是一个严格的分析，但这是一个合理的解释。
你有没有尝试传递-funroll-loops -fprefetch-loop-arrays到GCC？
我通过这些附加优化获得了以下结果：
[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1 model name : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz [1829] /tmp/so_25078285 $ g++ --version|head -n1 g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3 [1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3 [1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11 test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays [1829] /tmp/so_25078285 $ ./test_o3 1 unsigned 41959360000 0.595 sec 17.6231 GB/s uint64_t 41959360000 0.898626 sec 11.6687 GB/s [1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1 unsigned 41959360000 0.618222 sec 16.9612 GB/s uint64_t 41959360000 0.407304 sec 25.7443 GB/s
我试图用Visual Studio 2013 Express ，使用指针，而不是索引，这加快了一点点的过程。 我怀疑这是因为寻址是偏移+寄存器，而不是偏移+寄存器+（寄存器<< 3）。 C ++代码。
uint64_t* bfrend = buffer+(size/8); uint64_t* bfrptr; // ... { startP = chrono::system_clock::now(); count = 0; for (unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with uint64_t for (bfrptr = buffer; bfrptr < bfrend;){ count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); } } 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; }
汇编代码：r10 = bfrptr，r15 = bfrend，rsi = count，rdi = buffer，r13 = k：
$LL5@main: mov r10, rdi cmp rdi, r15 jae SHORT $LN4@main npad 4 $LL2@main: mov rax, QWORD PTR [r10+24] mov rcx, QWORD PTR [r10+16] mov r8, QWORD PTR [r10+8] mov r9, QWORD PTR [r10] popcnt rdx, rax popcnt rax, rcx add rdx, rax popcnt rax, r8 add r10, 32 add rdx, rax popcnt rax, r9 add rsi, rax add rsi, rdx cmp r10, r15 jb SHORT $LL2@main $LN4@main: dec r13 jne SHORT $LL5@main
你有没有尝试移动循环外的减less步骤？ 现在你有一个真正不需要的数据依赖。
尝试：
uint64_t subset_counts[4] = {}; for( unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with unsigned unsigned i=0; while (i < size/8) { subset_counts[0] += _mm_popcnt_u64(buffer[i]); subset_counts[1] += _mm_popcnt_u64(buffer[i+1]); subset_counts[2] += _mm_popcnt_u64(buffer[i+2]); subset_counts[3] += _mm_popcnt_u64(buffer[i+3]); i += 4; } } count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];
你也有一些奇怪的锯齿，我不确定是否遵守严格的锯齿规则。
TL; DR：使用__builtin内在函数。
我能够通过使用__builtin_popcountll使用相同的汇编指令，但没有错误的依赖错误，使得gcc 4.8.4（甚至gcc.godbolt.org上的4.7.3）为此产生最佳代码。
我不是100％确定我的基准代码，但objdump输出似乎分享我的看法。 我使用了一些其他的技巧（ ++i vs i++ ），让编译器在没有任何movl指令的情况下展开循环（奇怪的行为，我必须说）。
结果：
Count: 20318230000 Elapsed: 0.411156 seconds Speed: 25.503118 GB/s
基准代码：
#include <stdint.h> #include <stddef.h> #include <time.h> #include <stdio.h> #include <stdlib.h> uint64_t builtin_popcnt(const uint64_t* buf, size_t len){ uint64_t cnt = 0; for(size_t i = 0; i < len; ++i){ cnt += __builtin_popcountll(buf[i]); } return cnt; } int main(int argc, char** argv){ if(argc != 2){ printf("Usage: %s <buffer size in MB>\n", argv[0]); return -1; } uint64_t size = atol(argv[1]) << 20; uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer)); // Spoil copy-on-write memory allocation on *nix for (size_t i = 0; i < (size / 8); i++) { buffer[i] = random(); } uint64_t count = 0; clock_t tic = clock(); for(size_t i = 0; i < 10000; ++i){ count += builtin_popcnt(buffer, size/8); } clock_t toc = clock(); printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC))); return 0; }
编译选项：
gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench
GCC版本：
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
Linux内核版本：
3.19.0-58-generic
CPU信息：
processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 70 model name : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz stepping : 1 microcode : 0xf cpu MHz : 2494.226 cache size : 6144 KB physical id : 0 siblings : 1 core id : 0 cpu cores : 1 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt bugs : bogomips : 4988.45 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management:
