将 32 位循环计数器替换为 64 位会在 Intel CPU 上使用_mm_popcnt_u64 引起疯狂的性能偏差

我一直在寻找最快的方法来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 次。我们计算弹出次数的时间。在大写情况下,内部循环变量是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 / 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 / s
  • uint64_t 41959360000 0.680954 秒15.3986 GB / s

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

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下降到20 GB/s ,因此用恒定值替换非恒定值会导致优化不足 。说真的,我不知道这是怎么回事!但是现在使用新版本的clang++

  • 未签名 41959360000 0.677009 秒15.4884 GB / s
  • uint64_t 41959360000 0.676909 秒15.4906 GB / s

等一下现在,两个版本的速度都降低到了 15 GB / s 的缓慢速度 。因此,在两种情况下,用常数替换非常数都会导致 Clang!代码缓慢。

我要求具有Ivy Bridge CPU 的同事来编译我的基准测试。他得到了类似的结果,因此似乎不是 Haswell。因为两个编译器在这里产生奇怪的结果,所以它似乎也不是编译器错误。我们这里没有 AMD CPU,因此只能在 Intel 上进行测试。

请更加疯狂!

以第一个示例(带有atol(argv[1])示例)为例,然后在变量前放置一个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

是的,另一种选择 。我们仍然有快 26 GB / s 的u32 ,但我们设法u64从 13 GB 至少 / S 到 20 GB / s 的版本! 在我 collegue 的 PC 中, u64版本成为速度甚至超过了u32的版本,产生所有的最快的结果。可悲的是,这仅适用于g++clang++似乎并不关心static

我的问题

您能解释这些结果吗?特别:

  • 哪有之间的这种差异u32u64
  • 如何用恒定的缓冲区大小替换非常数会触发次优代码
  • 插入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准备好后再执行。英特尔现已(现在)将这种错误依赖性记录为勘误表HSD146(Haswell)SKL029(Skylake)

Skylake 将其固定为lzcnttzcnt
坎农湖(和冰湖) popcnt修复为popcnt
bsf / bsr具有真正的输出依赖性:输入 = 0 时输出未修改。 (但是没有办法利用内在函数来利用它 - 只有 AMD 记录了它,编译器没有公开它。)

(是的,这些指令都在同一执行单元上运行)。


这种依赖关系不只是从单个循环迭代中容纳 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 / 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并不是最常用的指令。因此,主要的编译器可能会错过这样的内容,这并不奇怪。似乎也没有任何文档提到此问题。如果英特尔不公开,那么除非有人偶然碰到它,否则外界不会知道。

更新: 从 4.9.2 版开始 ,GCC 意识到了这种虚假依赖关系,并在启用优化后生成了代码以对其进行补偿。其他厂商的主要编译器,包括 Clang,MSVC 甚至是英特尔自己的 ICC,都尚未意识到此微体系结构勘误表,并且不会发出补偿它的代码。)

为什么 CPU 具有如此错误的依赖性?

我们可以推测:它运行相同的执行单元作为bsf / bsr确实有一个输出的依赖。 ( 如何在硬件中实现 POPCNT? )。对于这些指令,Intel 将 input = 0 的整数结果记录为 “未定义”(ZF = 1),但是 Intel 硬件实际上为避免破坏旧软件提供了更强的保证:输出未修改。 AMD 记录了这种行为。

可能不方便地为此执行单元的输出依赖于输出,而另一些则不然。

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 (假)依赖关系链中的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 位版本,即可在程序内部 popcount 循环中将所有 32 位指令 / 寄存器替换为 64 位版本。观察:代码与 32 位版本一样快!

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

然后,我从程序的 32 位版本复制了内部循环代码,将其修改为 64 位,并在寄存器中进行了修饰,以使其替换 64 位版本的内部循环。 此代码也可以与 32 位版本一样快地运行。

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

(注意:我搞砸了程序集,可能在不注意的情况下破坏了某些东西。我不这样认为。)

这不是答案,但是如果我将结果放入评论中则很难阅读。

我使用Mac ProWestmere 6 核Xeon 3.33 GHz)获得了这些结果。我用clang -O3 -msse4 -lstdc++ a.cpp -oa编译了它(-O2 得到了相同的结果)。

带有uint64_t size=atol(argv[1])<<20; 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 uint64_t size=1<<20;

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 位索引访问缓冲区。访问具有 64 位偏移量的指针需要专用的 64 位寄存器和地址,而您可以将 Instant 用于 32 位偏移量。这可能会使 32 位版本更快。

  • 指令仅在 64 位编译器上发出(即预取)。这使 64 位速度更快。

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

我无法给出权威性的答案,但会概述可能的原因。 该参考资料清楚地表明,对于循环主体中的指令,延迟和吞吐量之间的比例为 3:1。它还显示了多个调度的效果。由于现代 x86 处理器中有(允许或不采取)三个整数单元,因此通常每个周期可以调度三个指令。

因此,在高峰管道和多种调度性能以及这些机制的失败之间,我们的性能有六分之一。众所周知,x86 指令集的复杂性使得它很容易发生古怪的破坏。上面的文档有一个很好的例子:

奔腾 4 的 64 位右移性能确实很差。 64 位左移以及所有 32 位移都具有可接受的性能。看来从 ALU 的高 32 位到低 32 位的数据路径设计得不好。

我个人遇到了一个奇怪的情况,即热循环在四核芯片(如果我还记得的话,AMD)的特定核心上运行得相当慢。通过关闭该核心,我们实际上在映射减少计算上获得了更好的性能。

在这里,我的猜测是争用整数单位: popcnt ,循环计数器和地址计算都只能使用 32 位宽的计数器全速运行,但是 64 位计数器会引起争用和流水线停顿。因为每个循环体执行总共只有大约 12 个周期,可能有 4 个周期有多个调度,所以单个停顿可以合理地将运行时间影响 2 倍。

我猜想使用静态变量引起的更改会导致对指令进行较小的重新排序,这是 32 位代码处于竞争的临界点的另一个线索。

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

我使用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

您是否尝试过将-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];

您还会遇到一些奇怪的别名,但我不确定这是否符合严格的别名规则。

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:

首先,尝试评估最高性能 - 检查https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf ,尤其是附录 C。

在您的情况下,表 C-10 显示 POPCNT 指令的延迟 = 3 个时钟,吞吐量 = 1 个时钟。吞吐量以时钟为单位显示最大速率(如果乘以 popcnt64,则乘以核心频率和 8 个字节,以获得最大可能的带宽数量)。

现在检查编译器做了什么,并总结了循环中所有其他指令的吞吐量。这将为生成的代码提供最佳的估计。

最后,请看一下循环中指令之间的数据依赖性,因为它们将迫使等待时间变成较大的延迟而不是吞吐量—因此,拆分数据流链上单次迭代的指令并计算它们之间的等待时间,然后天真地从它们中获取最大的延迟。考虑到数据流的依赖关系,它将给出粗略的估计。

但是,对于您而言,仅以正确的方式编写代码将消除所有这些复杂性。与其累加到相同的计数变量,不如累加到不同的变量(如 count0,count1,... count8),然后将它们累加起来。甚至创建一个 counts [8] 数组并将其累加到其元素 - 甚至将其矢量化,您将获得更好的吞吐量。

PS,永远不要运行基准测试,首先要预热内核,然后运行循环至少 10 秒钟或更长时间(最好 100 秒钟)。否则,您将在硬件中测试电源管理固件和 DVFS 实现:)

PPS 我听到了关于基准测试应该运行多少时间的无休止的辩论。最聪明的人甚至都问为什么 10 秒不是 11 或 12。我应该承认这在理论上很有趣。实际上,您只需连续运行基准测试一百次并记录偏差。这有趣的。多数人确实会改变源头,并在一次 ONCE 之后跑台以获取新的性能记录。做正确的事。

还是不服气?只需使用 assp1r1n3( https://stackoverflow.com/a/37026212/9706746 )的基准 C 版本以上,然后在重试循环中尝试使用 100 而不是 10000。

我的 7960X 显示为 RETRY = 100:

计数:203182300 经过:0.008385 秒速度:12.505379 GB / s

计数:203182300 经过:0.011063 秒速度:9.478225 GB / s

计数:203182300 已用:0.011188 秒速度:9.372327 GB / s

计数:203182300 已用:0.010393 秒速度:10.089252 GB / s

计数:203182300 已用:0.009076 秒速度:11.553283 GB / 秒

RETRY = 10000 时:

计数:20318230000 经过:0.661791 秒速度:15.844519 GB / s

计数:20318230000 经过:0.665422 秒速度:15.758060 GB / s

计数:20318230000 经过:0.660983 秒速度:15.863888 GB / s

计数:20318230000 经过:0.665337 秒速度:15.760073 GB / s

计数:20318230000 经过:0.662138 秒速度:15.836215 GB / s

PPPS 最后,关于 “可接受的答案” 和其他含糊的说法;-)

让我们用 assp1r1n3 的答案 - 他有 2.5Ghz 的内核。 POPCNT 有 1 个时钟吞吐量,他的代码使用 64 位 popcnt。因此,对于他的设置,数学运算为 2.5Ghz * 1 时钟 * 8 字节 = 20 GB / s。他看到的速度为 25Gb / s,这可能是由于 Turbo 提升至 3Ghz 左右。

因此,请访问 ark.intel.com 并查找 i7-4870HQ: https ://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-?q = i7-4870HQ

该内核的硬件运行速度可高达 3.7Ghz,实际最大速率为 29.6 GB / s。那么另外还有 4GB / s?也许,它花费在每次迭代中的循环逻辑和其他周围的代码上。

现在这种虚假依赖在哪里 ?硬件几乎以峰值速率运行。也许我的数学不好,有时会发生:)

PPPPPS 仍然有人认为 HW 勘误是罪魁祸首,因此我遵循了建议并创建了内联 asm 示例,请参见下文。

在我的 7960X 上,第一个版本(单输出到 cnt0)的运行速度为 11MB / s,第二个版本(向 cnt0,cnt1,cnt2 和 cnt3 的输出输出)的速度为 33MB / s。有人会说 - 瞧!它是输出依赖性。

好的,也许,我的意思是写这样的代码没有意义,这不是输出依赖问题,而是愚蠢的代码生成。我们不是在测试硬件,而是在编写代码以释放最大性能。您可能希望 HW OOO 应该重命名并隐藏那些 “输出相关性”,但是,大胆地做对了正确的事情,就永远不会遇到任何谜团。

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}

好的,我想为 OP 提出的子问题之一提供一个小答案,而这些子问题似乎在现有问题中未得到解决。请注意,我没有做任何测试或代码生成,也没有反汇编,只是想与他人分享一个想法。

为什么static改变性能?

问题所在的行: uint64_t size = atol(argv[1])<<20;

简短答案

我将查看为访问size而生成的程序集,并查看非静态版本是否涉及指针间接访问的额外步骤。

长答案

由于变量只有一个副本(无论是否声明为static ,并且大小不变,因此我认为区别在于用于支持变量的内存位置以及代码中使用的位置再向下。

好了,首先显而易见,请记住,函数的所有局部变量(以及参数)都在堆栈上提供了用作存储的空间。现在,很明显,main()的堆栈框架永远不会清理,只会生成一次。好吧,将其static呢?好吧,在那种情况下,编译器知道在进程的全局数据空间中保留空间,因此无法通过除去堆栈帧来清除该位置。但是,我们只有一个位置,所以有什么区别?我怀疑这与如何引用堆栈上的内存位置有关。

当编译器生成符号表时,它只是为标签以及相关属性(例如大小等)创建一个条目。它知道它必须在内存中保留适当的空间,但实际上直到稍后才选择该位置。进行活动性分析并可能进行寄存器分配后的处理。然后,链接器如何知道要为最终汇编代码提供给机器代码的地址?它要么知道最终位置,要么知道如何到达该位置。对于堆栈,引用一个基于两个元素的位置非常简单,一个指向堆栈框架的指针,然后指向该框架的偏移量。这基本上是因为链接程序在运行时之前无法知道堆栈帧的位置。