题 用64位替换32位循环计数器会引入疯狂的性能偏差


我一直在寻找最快捷的方式 popcount 大数据数据。我遇到了一个 很奇怪 效果:更改循环变量 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的内在函数。为了获得更精确的结果,我们做了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的  酷睿i7-4770K CPU @ 3.50 GHz,正在运行 test 1 (所以1 MB随机数据):

  • unsigned 41959360000 0.401554秒 26.113 GB / s的
  • uint64_t 41959360000 0.759822秒 13.8003 GB /秒

如你所见,吞吐量 uint64_t 版本是 只有一半 其中之一 unsigned 版!问题似乎是生成了不同的程序集,但为什么呢?首先,我想到了编译器错误,所以我尝试了 clang++ (Ubuntu的  版本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++

  • unsigned 41959360000 0.509156秒 20.5944 GB /秒
  • uint64_t 41959360000 0.508673秒 20.6139 GB /秒

现在,两个版本都同样快。但是,那 unsigned  变得更慢了!它从中掉了下来 26 至 20 GB/s因此用一个恒定值代替非常数导致a 去优化。说真的,我不知道这里发生了什么!但现在到了 clang++ 新版本:

  • unsigned 41959360000 0.677009秒 15.4884 GB /秒
  • uint64_t 41959360000 0.676909秒 15.4906 GB /秒

等等,什么? 现在,两个版本都降到了  数量为15 GB / s。因此,将非常数替换为常数值甚至会导致代码速度变慢  Clang的案例!

我问了一位同事 常春藤桥 CPU编译我的基准测试。他得到了类似的结果,所以它似乎不是哈斯威尔。因为这里有两个编译器产生奇怪的结果,所以它似乎也不是编译器错误。我们这里没有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版本! 在我的同事的PC上, u64 版本变得比速度更快 u32 版本,产生最快的结果。 可悲的是,这只适用于 g++clang++ 似乎并不关心 static

我的问题

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

  • 怎么会有这样的区别 u32 和 u64
  • 如何通过常量缓冲区大小触发器替换非常量 不太理想的代码
  • 如何插入 static 关键字make u64 循环更快?比同事的电脑上的原始代码还要快!

我知道优化是一个棘手的领域,然而,我从未想过这么小的变化会导致一个 100%的差异 在执行时间和小的因素,如恒定的缓冲区大小可以再次完全混合结果。当然,我总是想拥有能够突破26 GB / s的版本。我能想到的唯一可靠的方法是复制粘贴此案例的程序集并使用内联汇编。这是摆脱编码器的唯一方法,这些编译器似乎对小变化感到厌烦。你怎么看?还有另一种方法可靠地获得具有最佳性能的代码吗?

反汇编

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

26 GB / s版本 g ++ / u32 / non-const 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 / non-const bufsize

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 / non-const 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大小变量前面的关键字!将来,在编写对系统性能至关重要的真正紧密和热循环时,我将始终在各种编译器上测试各种替代方案。

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


1150
2017-08-01 10:33


起源


很多评论!您可以 在聊天中查看它们 如果你愿意,甚至可以留在那里,但请不要在这里添加! - Shog9♦
另见 GCC问题62011,popcnt指令中的错误数据依赖性。其他人提供了它,但似乎在清理过程中丢失了。 - jww


答案:


罪魁祸首:虚假数据依赖 (而且编译器甚至都不知道它)

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

popcnt  src, dest

似乎对目标寄存器具有错误依赖性 dest。即使指令只写入它,指令也会等到 dest 在执行之前准备就绪。

这种依赖性并不仅仅支撑着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 并不是最常用的指令。所以主要的编译器可能会错过这样的东西并不奇怪。在任何地方似乎都没有提到这个问题的文件。如果英特尔没有透露它,那么外面的任何人都不会知道,直到有人碰到它。

更新:  从版本4.9.2开始,GCC知道这种错误依赖,并生成代码以在启用优化时对其进行补偿。来自其他供应商的主要编译器,包括Clang,MSVC,甚至是英特尔自己的ICC,都还没有意识到这种微体系结构的错误,并且不会发出补偿它的代码。)

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

我们只能推测,但很可能英特尔对很多双操作数指令的处理方式相同。常见说明如 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  \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在(假)依赖链中的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

1311
2017-08-01 22:41



嗨伙计!这里有很多过去的评论;请在离开新的之前 查看存档。 - Shog9♦
这仍然在铿锵声中重现。我提交了一个错误: bugs.llvm.org/show_bug.cgi?id=34936。 - Justin L.


我编写了一个等效的C程序进行实验,我可以证实这种奇怪的行为。更重要的是, gcc 相信64位整数(应该是一个 size_t 无论如何...)更好,如使用 uint_fast32_t 导致gcc使用64位uint。

我对装配做了一些讨论:
只需使用32位版本,将所有32位指令/寄存器替换为程序内部popcount-loop中的64位版本。观察:代码是 和32位版本一样快!

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

然后我从32位版本的程序中复制了内部循环代码,将其破解为64位,使用寄存器进行调整,使其成为64位版本内部循环的替代品。 此代码的运行速度与32位版本一样快。

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

 (警告:我破坏了装配,可能在没有注意的情况下破坏了一些东西。我不这么认为。)


47
2017-08-01 22:55





这不是一个答案,但如果我将结果置于评论中,则难以阅读。

我得到这些结果 Mac Pro (的Westmere 6-芯 至强 3.33千兆赫)。我编译了它 clang -O3 -msse4 -lstdc++ a.cpp -o a (-O2得到相同的结果)。

铿锵有笑 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

我也试过:

  1. 反转测试顺序,结果相同,因此它排除了缓存因子。
  2. 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位更快。

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


24
2017-08-01 11:04



有意思,你能添加编译器版本和编译器标志吗? 最好的是,在你的机器上,结果会被转换,即使用u64更快。到现在为止,我从未想过我的循环变量有哪种类型,但似乎我下次要三思而后:)。 - gexicide
@gexicide:我不打算从16.8201跳到16.8126让它“更快”。 - Mehrdad
@Mehrdad:我的意思是跳跃之间的跳跃 12.9 和 16.8所以 unsigned 在这里更快。在我的基准测试中,情况恰恰相反,即26 unsigned,15 uint64_t - gexicide
@gexicide您是否注意到缓冲区[i]的区别? - Non-maskable Interrupt
@Calvin:不,你是什么意思? - gexicide


我不能给出权威的答案,但提供可能原因的概述。 这个参考 很清楚地表明,对于循环体中的指令,延迟和吞吐量之间的比率为3:1。它还显示了多次发送的效果。由于在现代x86处理器中存在(给 - 取)三个整数单元,因此通常可以在每个周期发送三个指令。

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

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

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

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

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

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


10
2017-08-01 20:12



不幸的是,从那以后(Core 2?),除了乘法/除法之外,32位和64位整数运算之间几乎没有性能差异 - 这在此代码中不存在。 - Mysticial
@Gene:请注意 所有 versions将大小存储在寄存器中,并且永远不会从循环中的堆栈中读取它。因此,地址计算不能混合,至少不在循环内。 - gexicide
@Gene:确实有趣的解释!但它没有解释WTF的主要观点:由于管道失速,64位比32位慢。但如果是这种情况,不应该是64位版本 可靠 比32bit慢?相反,当使用编译时常量缓冲区大小时,三个不同的编译器甚至为32位版本发出慢速代码;将缓冲区大小更改为静态会再次完全改变。在我的同事机器上(以及在Calvin的答案中)甚至有一个案例,64位版本的速度要快得多!这似乎是绝对不可预测的.. - gexicide
@Mysticial这是我的观点。当IU,总线时间等争用为零时,没有峰值性能差异。参考文献清楚地表明了这一点。争用使一切变得不同。以下是英特尔酷睿文献中的一个例子:“设计中包含的一项新技术是Macro-Ops Fusion,它将两个x86指令组合成一个微操作。例如,一个常见的代码序列,如比较后跟条件跳转将成为一个单一的微操作。不幸的是,这种技术在64位模式下不起作用。“所以我们的执行速度比为2:1。 - Gene
@gexicide我看到你在说什么,但你推断的比我的意思更多。我说运行速度最快的代码是保持管道和调度队列满。这种情况很脆弱。对总数据流和指令重新排序添加32位等微小变化足以打破它。简而言之,OP的断言,即摆弄和测试是前进的唯一方法是正确的。 - Gene


你试过传球吗? -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

9
2017-08-04 15:37



但是,你的结果仍然很奇怪(首先是unsigned更快,然后uint64_t更快)因为展开不能解决false依赖的主要问题。 - gexicide


我试过这个 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

9
2017-08-02 03:48





您是否尝试过在循环外移动还原步骤?现在你有一个真正不需要的数据依赖。

尝试:

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

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


7
2017-08-01 18:33



这是我读完这个问题后我做的第一件事。打破依赖链。事实证明,性能差异并没有改变(至少在我的电脑上 - 英特尔Haswell与GCC 4.7.3)。 - Nils Pipenbrinck
@BenVoigt:它符合严格的别名。 void* 和 char* 两种类型可能是别名,因为它们被认为是“指向一些内存块的指针”!您对数据依赖性删除的想法很适合优化,但它没有回答这个问题。并且,正如@NilsPipenbrinck所说,它似乎没有改变任何东西。 - gexicide
@gexicide:严格别名规则不对称。您可以使用 char* 访问一个 T[]。您 不能 安全地使用 T* 访问一个 char[],你的代码似乎做后者。 - Ben Voigt
@BenVoigt:那你永远不会拯救 malloc malloc返回时的任何数组 void* 你把它解释为 T[]。而且我很确定 void* 和 char* 有关严格别名的语义相同。但是,我觉得这里非常偏僻:) - gexicide
我个人认为正确的方法是 uint64_t* buffer = new uint64_t[size/8]; /* type is clearly uint64_t[] */ char* charbuffer=reinterpret_cast<char*>(buffer); /* aliasing a uint64_t[] with char* is safe */ - Ben Voigt


TL; DR:使用 __builtin 反而是内在的。

我能够做到 gcc 4.8.4(甚至gcc.godbolt.org上的4.7.3)通过使用生成最佳代码 __builtin_popcountll它使用相同的汇编指令,但没有那个错误依赖性错误。

我不是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:

5
2018-05-04 11:14



这只是好运 -funroll-loops 碰巧使代码不会产生由循环传承的依赖链创建的瓶颈 popcnt是假的。使用不了解错误依赖关系的旧编译器版本是一种风险。没有 -funroll-loops,gcc 4.8.5的循环将成为popcnt延迟而不是吞吐量的瓶颈, 因为它计入了 rdx。相同的代码, 由gcc 4.9.3编译 添加一个 xor edx,edx 打破依赖链。 - Peter Cordes
对于旧编译器,您的代码仍然容易受到OP所经历的完全相同的性能变化的影响:看似微不足道的更改可能会使gcc变慢,因为它不知道它会导致问题。 在旧编译器上找到在一个案例中正常工作的东西是 不 这个问题。 - Peter Cordes
作为记录, x86intrin.h的 _mm_popcnt_* 在GCC上运作 是强行内联包装的 __builtin_popcount*;内联应该使一个完全等同于另一个。我非常怀疑你会看到它们之间切换可能造成的任何差异。 - ShadowRanger