我正在寻找最快的方法来弹出大量数据。我遇到了一个非常奇怪的效果:将循环变量从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 << "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。为了得到更精确的结果,我们做了10000次popcount。我们为教皇计时。在大写情况下,内部循环变量是无符号的,在小写情况下,内循环变量是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下运行测试1(因此1 MB随机数据)的结果:

无符号41959360000 0.401554秒26.113 GB/suint64_t 41959360000 0.759822秒13.8003 GB/s

如您所见,uint64_t版本的吞吐量仅为未签名版本的一半!问题似乎是生成了不同的程序集,但为什么?首先,我想到了一个编译器错误,所以我尝试了clang++(Ubuntu clang版本3.4-1ubuntu3):

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

结果:测试1

无符号41959360000 0.398293秒26.3267 GB/suint64_t 41959360000 0.680954秒15.3986 GB/s

所以,这几乎是相同的结果,仍然很奇怪。但现在它变得超级奇怪。我将从输入读取的缓冲区大小替换为常量1,因此我更改:

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

to

uint64_t size = 1 << 20;

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

无符号41959360000 0.509156秒20.5944 GB/suint64_t 41959360000 0.508673秒20.6139 GB/s

现在,两个版本的速度都一样快。然而,未签名的变得更慢了!它从26 GB/s下降到20 GB/s,因此用常量值替换非常量会导致非优化。说真的,我不知道这里发生了什么!但现在,要用新版本发出叮当声:

无符号41959360000 0.677009秒15.4884 GB/suint64_t 41959360000 0.676909秒15.4906 GB/s

等等,什么?现在,两个版本都降到了15GB/s的速度。因此,用常量值替换非常量甚至会导致Clang在这两种情况下的代码变慢!

我请一位拥有Ivy Bridge CPU的同事来编译我的基准测试。他得到了类似的结果,所以似乎不是哈斯韦尔。因为两个编译器在这里产生了奇怪的结果,所以它似乎也不是编译器错误。我们这里没有AMD CPU,所以我们只能使用Intel进行测试。

请再疯狂一点!

以第一个示例(带有atol(argv[1])的示例)为例,在变量之前放置一个静态变量,即:

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

以下是我在g++中的结果:

无符号41959360000 0.396728秒26.4306 GB/suint64_t 41959360000 0.509484秒20.5811 GB/s

是的,又是另一种选择。我们仍然拥有u32的快速26GB/s,但我们设法获得了u64,至少从13GB/s到20GB/s版本!在我同事的电脑上,u64版本比u32版本更快,取得了最快的成绩。遗憾的是,这只适用于g++,clang++似乎不关心静态。

我的问题

你能解释一下这些结果吗?特别是:

u32和u64之间怎么会有这样的区别?用恒定缓冲区大小替换非常量如何触发更少的优化代码?静态关键字的插入如何使u64循环更快?甚至比我同事电脑上的原始代码还要快!

我知道优化是一个棘手的领域,然而,我从来没有想过这样的小变化会导致执行时间的100%差异,并且像恒定缓冲区大小这样的小因素会再次完全混合结果。当然,我总是希望有一个能够弹出26GB/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%的差异!即使缓冲区的存储类型也会产生巨大的差异,正如我们在大小变量前面插入静态关键字所看到的那样!将来,当编写对系统性能至关重要的非常紧凑和热循环时,我将始终在各种编译器上测试各种替代方案。

有趣的是,尽管我已经展开了四次循环,但性能差异仍然很大。因此,即使展开,仍可能会受到重大性能偏差的影响。很有趣。


当前回答

我在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=计数,rdi=缓冲区,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

其他回答

您是否尝试过将缩减步骤移出循环?现在您有一个真正不需要的数据依赖关系。

Try:

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

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

我编写了一个等效的C程序进行实验,我可以确认这种奇怪的行为。此外,gcc认为64位整数(无论如何可能是size_t…)会更好,因为使用uint_fast32_t会导致gcc使用64位uint。我在大会上做了一些手脚:只需取32位版本,在程序的内部popcount循环中用64位版本替换所有32位指令/寄存器。观察:代码与32位版本一样快!这显然是一个错误,因为变量的大小不是真正的64位,因为程序的其他部分仍然使用32位版本,但只要内部popcount循环控制性能,这是一个好的开始。然后,我从32位版本的程序中复制了内循环代码,将其修改为64位,并修改了寄存器,使其成为64位版本的内循环的替代品。此代码的运行速度也与32位版本一样快。我的结论是,这是编译器糟糕的指令调度,而不是32位指令的实际速度/延迟优势。(注意:我砍断了组件,可能在没有注意到的情况下打碎了一些东西。我不这么认为。)

这不是一个答案,但如果我把结果放在评论中,很难阅读。

我用Mac Pro(Westmere 6核Xeon 3.33 GHz)得到了这些结果。

clang with uint64_t size=环礁(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

我还试图:

颠倒测试顺序,结果相同,因此排除了缓存因子。使用相反的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位速度更快。

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

我在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=计数,rdi=缓冲区,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

我无法给出权威的答案,但提供了一个可能原因的概述。该参考非常清楚地表明,对于循环主体中的指令,延迟和吞吐量之间的比率为3:1。它还显示了多重调度的效果。由于在现代x86处理器中有三个整数单元,因此通常可以在每个周期中分配三个指令。

因此,在峰值流水线和多重调度性能以及这些机制的故障之间,我们有六倍的性能。众所周知,x86指令集的复杂性使得很容易发生奇怪的破坏。上面的文档有一个很好的例子:

奔腾4的64位右移性能非常差。64位左移位以及所有32位移位具有可接受的性能。从ALU的高位32位到低位32位的数据路径似乎设计得不好。

我个人遇到了一个奇怪的情况,在一个四核芯片(如果我记得的话,是AMD)的特定核心上,热循环运行得非常慢。实际上,通过关闭核心,我们在地图缩减计算上获得了更好的性能。

这里我的猜测是整数单位的争用:popcnt、循环计数器和地址计算都只能用32位宽的计数器以全速运行,但64位计数器会导致争用和管道暂停。由于每个循环体执行总共只有大约12个循环,可能有4个循环具有多个分派,因此单个暂停可以合理地影响运行时间2倍。

使用静态变量引起的变化(我猜这只是导致指令的轻微重新排序)是32位代码处于争用临界点的另一个线索。

我知道这不是一个严格的分析,但这是一个合理的解释。