c++ - 将32-bit循环计数变量替换为64-bit引入了疯狂的性能偏差

  显示原文与译文双语对照的内容

我正在寻找最快的方法来处理大量的数据。 我遇到一个非常怪异影响: 将循环变量从 unsigned 更改为 uint64_t 使我的计算机上的性能下降 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 <<"unsignedt" <<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_tt" <<count <<'t' <<(duration/1.0E9) <<" sec t"
 <<(10000.0*size)/(duration) <<" GB/s" <<endl;
 }

 free(charbuffer);
}

如你所见,我们创建了一个随机数据缓冲区,大小为 x mb,其中 x 是从 命令行 读取的。 然后,我们迭代缓冲区并使用一个已经展开的x86 popcount 内部版本来执行 popcount 。 为了得到更精确的结果,我们执行 popcount 10,000次。 我们测量popcount的时间。 在上面的例子中,内部循环变量是 unsigned,在小写情况下,内部循环变量是 uint64_t 。 我认为这应该没有区别,但相反的情况。

( 绝对疯狂) 结果

我像这样编译( G++ 版本: Ubuntu 4.8.2 -19 ubuntu1 ):


g++ -O3 -march=native -std=c++11 test.cpp -o test

以下是我的Haswell内核 i7-4770K @ 3.50 GHz的结果,运行 test 1 ( 所以 1 MB随机数据):

  • 无符号的41959360000 0.401 554秒 26.113 gb/s
  • uint64_t 41959360000 0.759 822秒 13.8003 gb/s

如你所见的吞吐量是 uint64_t 版本只有一半的其中一个 unsigned 版本 ! 问题似乎是产生了不同的程序集,但是为什么? 首先,我想到了一个编译器 Bug,所以我尝试了 clang++ ( Ubuntu Clang 3.4 -1 ubuntu3 ):


clang++ -O3 -march=native -std=c++11 teest.cpp -o test

结果:test 1

  • 无符号 41959360000 0.398 293秒 26.3267 gb/s
  • uint64_t 41959360000 0.680 954秒 15.3986 gb/s

所以,它几乎是同样的结果,而且仍然是奇怪的。 ,但现在它变得异常奇怪。 保持稳定 1,所以我 change, 我代替那是input:中读取的缓冲区大小


uint64_t size = atol(argv[1]) <<20;


uint64_t size = 1 <<20;

因此,编译器现在知道编译时的缓冲区大小。 也许它可以添加一些优化 ! 以下是 g++的数字:

  • 无符号 41959360000 0.509 156秒 20.5944 gb/s
  • uint64_t 41959360000 0.508 673秒 20.6139 gb/s

现在,两个版本都同样快速。 然而,unsigned有甚至更慢 ! 它从 26 掉到 20 GB/s,从而替换一个由常数non-constant值导致一个 deoptimization 。 说真的,我不知道这里发生了什么 ! 但是现在使用新版本的clang++:

  • 无符号 41959360000 0.677 009秒 15.4884 gb/s
  • uint64_t 41959360000 0.676 909秒 15.4906 gb/s

等等什么现在,这两个版本的摔到 15数 gb/s 。 在同时 情况下由一个常数值,用于clang,因此,替换一个non-constant甚至导致缓慢的代码 !

我向一位同事请教了一个 Ivy Bridge CPU来编译我的基准测试。 他得到了类似的结果,所以似乎不是 Haswell 。 因为两个编译器在这里产生奇怪的结果,它似乎不是编译器 Bug 。 我们没有AMD处理器,所以我们只能通过英特尔测试。

更多的疯狂,请 !

在第一个示例中,i.e.: ( 带 atol(argv[1])的那个) 和前放置一个 static 变量


static uint64_t size=atol(argv[1])<<20;

以下是 G++ 中的结果:

  • 无符号 41959360000 0.396 728秒 26.4306 gb/s
  • uint64_t 41959360000 0.509 484秒 20.5811 gb/s

,还有一种方法给力 我们依然需要快速与 u32 26 gb/s,但我们设法搞来 u64 至少在 20从 13 gb/s 到 gb/s的版本 ! collegue的在我的电脑上全部的,u64 版本都变得远远快于 u32 版本,随之产生的最快的结果。 ,这只对 g++ 有效,clang++ 似乎不关心 static

我的问题

你能解释这些结果? 尤其是:

  • u32u64 之间有什么区别?
  • 如何用恒定的缓冲区大小触发 non-constant 的最佳代码?
  • static 关键字的插入如何使 u64 循环更快? 比我的collegue上的原始代码快得多 !

我知道优化是一个棘手的领地,但是,我从来都不敢想象这么小的变化可以导致一个 100%差异在小数据,比如一个常量缓冲区大小可以再次混合的执行时间和结果完全。 当然,我总是想要有能够 popcount 26 gb的版本。 我可以想到的唯一可靠的方法是复制这个案例的程序集并使用内联汇编。 这是我唯一能摆脱那些在小改动上发疯的编译器。 你认为如何是否有另一种方法来可靠地获取大多数性能?

反汇编

以下是各种结果的反汇编:

g++/u32/non-const 缓冲尺寸, 26 gb/s version:


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 缓冲尺寸, 13 gb/s version:


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 缓冲尺寸, 15 gb/s version:


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 version:


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 缓冲尺寸, 15 gb/s version:


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% 不同 ! 即使缓冲区的存储类型也会产生巨大的差异,因为我们在大小变量前面看到 static 关键字 ! 在将来,我将总是在编写非常紧密和热门的循环时测试各种编译器,这对于系统性能至关重要。

有趣的是,性能差异仍然如此高,尽管我已经展开了四次循环。 所以即使你展开了,你仍然会受到主要性能偏差的影响。 相当有趣。

时间:

罪魁祸首。受众数据依赖 ( 以及它的编译器不是还未意识到的)

在 sandy/ivy桥和Haswell处理器上,说明:

 
popcnt src, dest

 

似乎对目标寄存器 dest 有错误的依赖关系。 即使指令只写入它,指令也会等待,直到 dest 准备好执行。

这个依赖关系不只是在一个循环迭代中保存 4 popcnt 。 它可以跨越循环迭代,使得处理器无法并行化不同的循环迭代。

unsigned vs uint64_t 和其他调整不会直接影响问题。 但是它们影响寄存器分配器,寄存器分配器将寄存器分配给变量。

在你的情况下,速度是依赖于( 错误) 依赖关系链的直接结果,取决于寄存器分配器决定做什么。

  • 13 gb/s 有一个链: popcnt-add-popcnt-popcnt --> 下一次迭代
  • 15 gb/s 有一个链: popcnt-add-popcnt-add --> 下一次迭代
  • 20 gb/s 有一个链: popcnt-popcnt --> 下一次迭代
  • 26 gb/s 有一个链: popcnt-popcnt --> 下一次迭代

20 gb/s 和 26 gb之间的差异似乎是间接寻址的次要工件。 无论哪种方式,一旦达到这个速度,处理器就会开始碰到其他瓶颈。


为了测试这一点,我使用内联汇编绕过编译器,并得到完全的程序集。 我还分解了 count 变量,以打破可能会影响基准测试的所有其他依赖。

以下是结果:

Sandy桥 Xeon @ 3.5 GHz: ( 在底部可以找到完整的测试代码)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • 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 有这样一个错误的依赖。 然而,这些错误的依赖并不罕见。 这只是编译器是否知道它。

popcnt 不是最常用的指令。 因此,一个主要的编译器可能会错过这样的事情并不是一件意外。 似乎没有任何文档在任何地方提到这个问题。 如果英特尔没有透露它,那么任何人都不会知道,除非有人偶然进入它。

为什么CPU有这样一个错误的依赖?

我们只能推测,但是很可能英特尔对很多two-operand指令有相同的处理。 像 addsub 这样的通用指令,两个操作数都是输入。 所以,英特尔可能将 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 nt"
"add %4, %0 nt"
"popcnt %5, %5 nt"
"add %5, %1 nt"
"popcnt %6, %6 nt"
"add %6, %2 nt"
"popcnt %7, %7 nt"
"add %7, %3 nt"
 :"+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 Chaint" <<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 nt"
"add %%rax, %0 nt"
"popcnt %5, %%rax nt"
"add %%rax, %1 nt"
"popcnt %6, %%rax nt"
"add %%rax, %2 nt"
"popcnt %7, %%rax nt"
"add %%rax, %3 nt"
 :"+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 nt"//<--- Break the chain.
"popcnt %4, %%rax nt"
"add %%rax, %0 nt"
"popcnt %5, %%rax nt"
"add %%rax, %1 nt"
"popcnt %6, %%rax nt"
"add %%rax, %2 nt"
"popcnt %7, %%rax nt"
"add %%rax, %3 nt"
 :"+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 Chaint" <<count <<'t' <<(duration/1.0E9) <<" sec t"
 <<(10000.0*size)/(duration) <<" GB/s" <<endl;
 }

 free(charbuffer);
}


同样有趣的基准可以在这里找到: http://pastebin.com/kbzgL8si
在( 错误) 依赖chain,这个基准测试中存在不同 are. 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

我编写了一个等价的C 程序来进行实验,我可以确认这种奇怪的行为。 更重要的是,gcc 认为 64位 整数( 这可能是一个 size_t 。。) 更好,因为使用 uint_fast32_t 会导致gcc使用 64位 uint 。

我对程序集做了一些手脚:
在的内 popcount-loop program,只取 32位 版本,替换所有 32位 说明/注册这些 64位 老汇 观察,代码的是 32位 还幽默的版本

这显然是一个 hack,因为变量的大小不是真正的64位,因为程序的其他部分仍然使用 32位 版本,但是只要内部popcount-loop支配性能,这就是一个好的开始。

然后我从程序的32位 版本复制内部循环代码,将它 hacked 64位,摆弄寄存器使它的成为 64位 版本的内部循环。 这里代码的也与 32位 版本一样快。

我的结论是这是编译器的错误指令调度,而不是 32位 指令的实际速度/延迟优势。

( 警告:我黑进了程序集,没有注意到) 。 我不这么认为。

在comment,这是不可一个答案,但这是看不清楚如果我把结果

带有 MacPro 我得到这些 results. 我把它编译成 clang -O3 -msse4 -lstdc++ a.cpp -o a ( -O2得到相同的结果) 。

clang随以 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;的clang


unsigned 41950110000 0.623406 sec 16.8201 GB/s
uint64_t 41950110000 0.623685 sec 16.8126 GB/s

我还试图:

  1. 反转测试顺序,结果是相同的,这样就排除了缓存因子。
  2. 使 for 语句反向: for (uint64_t i=size/8;i>0;i-=4) ,这就把相同的结果,证明了该编译足够智能,能够不要被( 按预期) 面积由 8每个迭代。

这是我的猜测:

速度系数分为三个部分:

  • 代码缓存:uint64_t 版本的代码大小较大,但这对我的Xeon CPU没有影响。 这使得 64位 版本更慢。

  • 使用说明。注意不仅循环计数,而且在两个版本上使用 32位 和 64位 索引访问缓冲区。 于一个 32位 相关访问一个指针会显示 64位 偏移要求一个专用 offset, 64位 寄存器和寻址,而你可以使用放射显影 这可能会使 32位 版本更快。

  • 指令只在 64位 编译( 也就是说,预取) 上发出。 这使 64位 更快。

这三个因素与观察到的看似矛盾的结果相匹配。

我不能给出权威的答案,但提供一个可能原因的概述。 这里引用说明相当清楚,对于你的循环的正文中的说明有一个 3: 1 率无延迟和吞吐量。 它还显示了多个分派的效果。 因为现在有三个整数单元( give-or-take ) 在现代x86处理器,它通常是可能的,以派遣三个指令每个周期。

因此,在峰值管道和多个调度性能和故障之间,我们在性能上有六个因素。 于离奇破裂以occur,它是很有名的,它的复杂性相关x86指令集将使它的变得非常什么难 上面的文档有一个很好的例子:

于 64位 右偏移,就确实是poor,了奔腾相关 4 performance. 64位 左移位以及所有 32位 移位都具有可以接受的性能。 看来从上部到下部 32 32位数据通路位算术逻辑单元的设计都不是很

我个人遇到了一个奇怪的情况,在一个four-core芯片( 如果我记得的话)的特定内核上,热循环运行得相当慢。 我们在map-reduce计算上得到了更好的性能,它把核心关闭。

在这里我猜是对整数单元的争用: ,该值为 popcnt 。循环计数器和地址计算练习只是刚好全速奔驰出 32位 宽计数器,但 64位 计数器会导致争用和流水线迟延。 只因为现在有约 12周期总与多分派,从而可能 4循环,每次循环体内执行,单个失速完全可能影响运行时通过 2的一个因素。

在某个临界点为这些改变 contention,,使用静态变量中( 我猜只是导致一个小的指令重新排序所引发的是另一个标志表明该 32位 代码包是

我知道这并不是一个严格的分析,但这是这是可能的解释。

我用 Visual Studio 2013表示这个,使用指针代替了索引,这加快了进程的速度。 我怀疑这是因为地址是偏移+ 寄存器,而不是偏移量+ 寄存器+ ( 注册 <<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_tt" <<count <<'t' <<(duration/1.0E9) <<" sec t"
 <<(10000.0*size)/(duration) <<" GB/s" <<endl;
 }

程序集代码:r10 = bfrptr,r15 = bfrend,rsi = 计数,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

你尝试过通过 -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

是否尝试将缩小步骤移到循环之外? 现在你有一个真正不需要的数据依赖。

尝试以下方法:


 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];

还有一些奇怪的别名,我不确定是否符合严格的别名规则。

...