c++ - 用 64 位替换 32 位循环计数器会在 Intel CPU 上使用 _mm_popcnt_u64 引入疯狂的性能偏差

Question

我正在寻找最快的方式 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 随机数据):

未签名 41959360000 0.401554 秒 26.113 GB/秒

uint64_t 41959360000 0.759822 秒 13.8003 GB/秒

如您所见， uint64_t 的吞吐量版本是 只有一半 unsigned之一版本!问题似乎是生成了不同的程序集，但为什么呢？首先，我想到了一个编译器的bug，所以我尝试了 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/秒

所以，这几乎是相同的结果，仍然很奇怪。但现在它变得非常奇怪。我用常量 1 替换从输入中读取的缓冲区大小，所以我改变:

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

到

uint64_t size = 1 << 20;

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

未签名 41959360000 0.509156 秒 20.5944 GB/秒

uint64_t 41959360000 0.508673 秒 20.6139 GB/秒

现在，两个版本都同样快。然而， unsigned 变得更慢 !它从 26 下降至 20 GB/s ，因此用常数值替换非常量会导致 去优化 .说真的，我不知道这里发生了什么!但现在到 clang++使用新版本:

未签名 41959360000 0.677009 秒 15.4884 GB/秒

uint64_t 41959360000 0.676909 秒 15.4906 GB/秒

等等，什么？现在，两个版本都下降到 慢 15 GB/s 的数量。因此，用常数值替换非常量甚至会导致 中的代码变慢。两者 Clang 的案例!

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

更疯狂，拜托!

以第一个例子(带有 atol(argv[1]) 的例子)并放一个 static在变量之前，即:

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

这是我在 g++ 中的结果:

未签名 41959360000 0.396728 秒 26.4306 GB/秒

uint64_t 41959360000 0.509484 秒 20.5811 GB/秒

是的，还有另一种选择。我们仍然拥有快速的 26 GB/s u32 ，但我们设法得到 u64至少从 13 GB/s 到 20 GB/s 版本! 在我同事的 PC 上，u64版本变得比 u32 更快版本，产生最快的结果。 遗憾的是，这只适用于 g++ , clang++好像不在意 static .

我的问题

你能解释一下这些结果吗？尤其:

u32怎么会有​​这种差别和 u64 ?

用恒定缓冲区大小替换非常量如何触发不太理想的代码？

怎么能插入static关键字使 u64循环更快？甚至比我同事电脑上的原始代码还要快!

我知道优化是一个棘手的领域，但是，我从没想过这么小的变化会导致 100% 差异 在执行时间和诸如恒定缓冲区大小之类的小因素可以再次完全混合结果。当然，我一直希望拥有能够达到 26 GB/s 的版本。我能想到的唯一可靠的方法是复制粘贴这种情况下的程序集并使用内联程序集。这是我摆脱那些似乎因小改动而发疯的编译器的唯一方法。你怎么认为？有没有另一种方法可以可靠地获得性能最高的代码？

拆卸

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

来自 的 26 GB/s 版本g++/u32/非常量 bufsize :

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

来自 的 13 GB/s 版本g++/u64/非常量缓冲区大小 :

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 版本clang++/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

来自 的 20 GB/s 版本g++/u32&u64/const 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

来自 的 15 GB/s 版本clang++/u32&u64/const bufsize :

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 时看到的那样。大小变量前面的关键字!将来，在编写对系统性能至关重要的非常紧且热的循环时，我将始终在各种编译器上测试各种替代方案。

有趣的是，尽管我已经展开了四次循环，但性能差异仍然如此之大。因此，即使您展开，您仍然会受到主要性能偏差的影响。挺有意思。

Answer 1

罪魁祸首:错误的数据依赖 (编译器甚至不知道)

在 Sandy/Ivy Bridge 和 Haswell 处理器上，指令:

popcnt  src, dest

似乎对目标寄存器 dest 有错误的依赖性。即使指令只写入它，指令也会等到 dest 准备好后再执行。这种错误的依赖(现在)被英特尔记录为勘误表 HSD146 (Haswell) 和 SKL029 (Skylake)

Skylake fixed this for lzcnt and tzcnt 。
Cannon Lake(和 Ice Lake)为 popcnt 修复了这个问题。 bsf/ bsr 具有真正的输出依赖性:输入=0 时输出未修改。 (但是 no way to take advantage of that with intrinsics - 只有 AMD 记录它并且编译器不公开它。)

(是的，这些指令都运行 on the same execution unit )。

这种依赖不仅仅支持来自单个循环迭代的 4 个 popcnt 。它可以进行循环迭代，使处理器无法并行化不同的循环迭代。
unsigned 与 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/s 之间的差异似乎是间接寻址的小瑕疵。无论哪种方式，一旦您达到此速度，处理器就会开始遇到其他瓶颈。

为了测试这一点，我使用了内联程序集来绕过编译器并获得我想要的程序集。我还拆分了 count 变量以打破所有其他可能与基准测试困惑的依赖关系。

结果如下:

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

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 有这样一个错误的依赖关系。然而，这些错误的依赖并不少见。这只是编译器是否意识到这一点的问题。
popcnt 并不是最常用的指令。因此，主要编译器可能会错过这样的事情并不奇怪。似乎也没有任何地方提到这个问题的文档。如果英特尔不公开它，那么除非有人偶然遇到，否则外界不会知道。

( 更新: As of version 4.9.2 ，GCC 意识到这种错误的依赖关系，并在启用优化时生成代码来补偿它。来自其他供应商的主要编译器，包括 Clang、MSVC，甚至英特尔自己的 ICC 还没有意识到这种微架构错误并且不会发出补偿它的代码。)

CPU为什么会有这种虚假的依赖？

我们可以推测:它与 bsf/ bsr 运行在相同的执行单元上，而 popcnt/ojit_code 确实具有输出依赖性。 ( How is POPCNT implemented in hardware? )。对于这些指令，英特尔将 input=0 的整数结果记录为“未定义”(ZF=1)，但英特尔硬件实际上提供了更强大的保证，以避免破坏旧软件:输出未修改。 AMD 记录了这种行为。

据推测，让这个执行单元的一些 uops 依赖于输出而其他的则不方便。

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

此基准测试会改变(假)依赖链中 ojit_code 的数量。

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