用64位替换32位循环计数器会导致英特尔CPU上_mm_popcnt_u64的性能偏差

我正在寻找最快的方法来弹出大量数据。我遇到了一个非常奇怪的效果：将循环变量从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;

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

2014-08-02 03:48:08

其他回答

这不是一个答案，而是2021少数编译器的反馈。在Intel CoffeeLake 9900k上。

使用Microsoft编译器（VS2019），工具集v142：

无符号209695540000 1.8322秒28.6152 GB/suint64_t 209695540000 3.08764秒16.9802 GB/s

使用Intel编译器2021：

无符号209695540000 1.70845秒30.688 GB/suint64_t 209695540000 1.57956秒33.1921 GB/s

根据Mysticial的回答，英特尔编译器知道虚假数据依赖性，但不知道微软编译器。

对于英特尔编译器，我使用了/QxHost（优化CPU的架构，即主机的架构）/Oi（启用内部函数）和#include<nmmintrin.h>，而不是#include<immintrin.h>。

完整编译命令：/GS/W3/QxHost/Gy/Zi/O2/D“NDEBUG”/D“_CONSOLE”/D”_UNICODE“/D”UNICODE“/Qipo/Zc:forScope/Oi/MD/Fa“x64 \ Release \”/EHsc/nologo/Fo“x64 \ Release\”//fprofile instr use“x64 \ Release\”/Fp“x64 \发布\ Benchmark.pch”。

ICC的反编译（IDA 7.5）程序集：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v6; // er13
  _BYTE *v8; // rsi
  unsigned int v9; // edi
  unsigned __int64 i; // rbx
  unsigned __int64 v11; // rdi
  int v12; // ebp
  __int64 v13; // r14
  __int64 v14; // rbx
  unsigned int v15; // eax
  unsigned __int64 v16; // rcx
  unsigned int v17; // eax
  unsigned __int64 v18; // rcx
  __int64 v19; // rdx
  unsigned int v20; // eax
  int result; // eax
  std::ostream *v23; // rbx
  char v24; // dl
  std::ostream *v33; // rbx
  std::ostream *v41; // rbx
  __int64 v42; // rdx
  unsigned int v43; // eax
  int v44; // ebp
  __int64 v45; // r14
  __int64 v46; // rbx
  unsigned __int64 v47; // rax
  unsigned __int64 v48; // rax
  std::ostream *v50; // rdi
  char v51; // dl
  std::ostream *v58; // rdi
  std::ostream *v60; // rdi
  __int64 v61; // rdx
  unsigned int v62; // eax

  __asm
  {
    vmovdqa [rsp+98h+var_58], xmm8
    vmovapd [rsp+98h+var_68], xmm7
    vmovapd [rsp+98h+var_78], xmm6
  }
  if ( argc == 2 )
  {
    v6 = atol(argv[1]) << 20;
    _R15 = v6;
    v8 = operator new[](v6);
    if ( v6 )
    {
      v9 = 1;
      for ( i = 0i64; i < v6; i = v9++ )
        v8[i] = rand();
    }
    v11 = (unsigned __int64)v6 >> 3;
    v12 = 0;
    v13 = Xtime_get_ticks_0();
    v14 = 0i64;
    do
    {
      if ( v6 )
      {
        v15 = 4;
        v16 = 0i64;
        do
        {
          v14 += __popcnt(*(_QWORD *)&v8[8 * v16])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 24])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 16])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 8]);
          v16 = v15;
          v15 += 4;
        }
        while ( v11 > v16 );
        v17 = 4;
        v18 = 0i64;
        do
        {
          v14 += __popcnt(*(_QWORD *)&v8[8 * v18])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 24])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 16])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 8]);
          v18 = v17;
          v17 += 4;
        }
        while ( v11 > v18 );
      }
      v12 += 2;
    }
    while ( v12 != 10000 );
    _RBP = 100 * (Xtime_get_ticks_0() - v13);
    std::operator___std::char_traits_char___(std::cout, "unsigned\t");
    v23 = (std::ostream *)std::ostream::operator<<(std::cout, v14);
    std::operator___std::char_traits_char____0(v23, v24);
    __asm
    {
      vmovq   xmm0, rbp
      vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000
      vpunpckldq xmm0, xmm0, xmm8
      vmovapd xmm7, cs:__xmm@45300000000000004330000000000000
      vsubpd  xmm0, xmm0, xmm7
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm6, xmm1, xmm0
      vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
    }
    v33 = (std::ostream *)std::ostream::operator<<(v23);
    std::operator___std::char_traits_char___(v33, " sec \t");
    __asm
    {
      vmovq   xmm0, r15
      vpunpckldq xmm0, xmm0, xmm8
      vsubpd  xmm0, xmm0, xmm7
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm0, xmm1, xmm0
      vmulsd  xmm7, xmm0, cs:__real@40c3880000000000
      vdivsd  xmm1, xmm7, xmm6
    }
    v41 = (std::ostream *)std::ostream::operator<<(v33);
    std::operator___std::char_traits_char___(v41, " GB/s");
    LOBYTE(v42) = 10;
    v43 = std::ios::widen((char *)v41 + *(int *)(*(_QWORD *)v41 + 4i64), v42);
    std::ostream::put(v41, v43);
    std::ostream::flush(v41);
    v44 = 0;
    v45 = Xtime_get_ticks_0();
    v46 = 0i64;
    do
    {
      if ( v6 )
      {
        v47 = 0i64;
        do
        {
          v46 += __popcnt(*(_QWORD *)&v8[8 * v47])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 8])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 16])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 24]);
          v47 += 4i64;
        }
        while ( v47 < v11 );
        v48 = 0i64;
        do
        {
          v46 += __popcnt(*(_QWORD *)&v8[8 * v48])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 8])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 16])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 24]);
          v48 += 4i64;
        }
        while ( v48 < v11 );
      }
      v44 += 2;
    }
    while ( v44 != 10000 );
    _RBP = 100 * (Xtime_get_ticks_0() - v45);
    std::operator___std::char_traits_char___(std::cout, "uint64_t\t");
    v50 = (std::ostream *)std::ostream::operator<<(std::cout, v46);
    std::operator___std::char_traits_char____0(v50, v51);
    __asm
    {
      vmovq   xmm0, rbp
      vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000
      vsubpd  xmm0, xmm0, cs:__xmm@45300000000000004330000000000000
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm6, xmm1, xmm0
      vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
    }
    v58 = (std::ostream *)std::ostream::operator<<(v50);
    std::operator___std::char_traits_char___(v58, " sec \t");
    __asm { vdivsd  xmm1, xmm7, xmm6 }
    v60 = (std::ostream *)std::ostream::operator<<(v58);
    std::operator___std::char_traits_char___(v60, " GB/s");
    LOBYTE(v61) = 10;
    v62 = std::ios::widen((char *)v60 + *(int *)(*(_QWORD *)v60 + 4i64), v61);
    std::ostream::put(v60, v62);
    std::ostream::flush(v60);
    free(v8);
    result = 0;
  }
  else
  {
    std::operator___std::char_traits_char___(std::cerr, "usage: array_size in MB");
    LOBYTE(v19) = 10;
    v20 = std::ios::widen((char *)&std::cerr + *((int *)std::cerr + 1), v19);
    std::ostream::put(std::cerr, v20);
    std::ostream::flush(std::cerr);
    result = -1;
  }
  __asm
  {
    vmovaps xmm6, [rsp+98h+var_78]
    vmovaps xmm7, [rsp+98h+var_68]
    vmovaps xmm8, [rsp+98h+var_58]
  }
  return result;
}

和主管道的拆卸：

.text:0140001000    .686p
.text:0140001000    .mmx
.text:0140001000    .model flat
.text:0140001000
.text:0140001000 ; ===========================================================================
.text:0140001000
.text:0140001000 ; Segment type: Pure code
.text:0140001000 ; Segment permissions: Read/Execute
.text:0140001000 _text           segment para public 'CODE' use64
.text:0140001000    assume cs:_text
.text:0140001000    ;org 140001000h
.text:0140001000    assume es:nothing, ss:nothing, ds:_data, fs:nothing, gs:nothing
.text:0140001000
.text:0140001000 ; =============== S U B R O U T I N E =======================================
.text:0140001000
.text:0140001000
.text:0140001000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:0140001000 main            proc near      ; CODE XREF: __scrt_common_main_seh+107↓p
.text:0140001000      ; DATA XREF: .pdata:ExceptionDir↓o
.text:0140001000
.text:0140001000 var_78          = xmmword ptr -78h
.text:0140001000 var_68          = xmmword ptr -68h
.text:0140001000 var_58          = xmmword ptr -58h
.text:0140001000
.text:0140001000    push    r15
.text:0140001002    push    r14
.text:0140001004    push    r13
.text:0140001006    push    r12
.text:0140001008    push    rsi
.text:0140001009    push    rdi
.text:014000100A    push    rbp
.text:014000100B    push    rbx
.text:014000100C    sub     rsp, 58h
.text:0140001010    vmovdqa [rsp+98h+var_58], xmm8
.text:0140001016    vmovapd [rsp+98h+var_68], xmm7
.text:014000101C    vmovapd [rsp+98h+var_78], xmm6
.text:0140001022    cmp     ecx, 2
.text:0140001025    jnz     loc_14000113E
.text:014000102B    mov     rcx, [rdx+8]    ; String
.text:014000102F    call    cs:__imp_atol
.text:0140001035    mov     r13d, eax
.text:0140001038    shl     r13d, 14h
.text:014000103C    movsxd  r15, r13d
.text:014000103F    mov     rcx, r15        ; size
.text:0140001042    call    ??_U@YAPEAX_K@Z ; operator new[](unsigned __int64)
.text:0140001047    mov     rsi, rax
.text:014000104A    test    r15d, r15d
.text:014000104D    jz      short loc_14000106E
.text:014000104F    mov     edi, 1
.text:0140001054    xor     ebx, ebx
.text:0140001056    mov     rbp, cs:__imp_rand
.text:014000105D    nop     dword ptr [rax]
.text:0140001060
.text:0140001060 loc_140001060:    ; CODE XREF: main+6C↓j
.text:0140001060    call    rbp ; __imp_rand
.text:0140001062    mov     [rsi+rbx], al
.text:0140001065    mov     ebx, edi
.text:0140001067    inc     edi
.text:0140001069    cmp     rbx, r15
.text:014000106C    jb      short loc_140001060
.text:014000106E
.text:014000106E loc_14000106E:    ; CODE XREF: main+4D↑j
.text:014000106E    mov     rdi, r15
.text:0140001071    shr     rdi, 3
.text:0140001075    xor     ebp, ebp
.text:0140001077    call    _Xtime_get_ticks_0
.text:014000107C    mov     r14, rax
.text:014000107F    xor     ebx, ebx
.text:0140001081    jmp     short loc_14000109F
.text:0140001081 ; ---------------------------------------------------------------------------
.text:0140001083    align 10h
.text:0140001090
.text:0140001090 loc_140001090:    ; CODE XREF: main+A2↓j
.text:0140001090      ; main+EC↓j ...
.text:0140001090    add     ebp, 2
.text:0140001093    cmp     ebp, 2710h
.text:0140001099    jz      loc_140001184
.text:014000109F
.text:014000109F loc_14000109F:    ; CODE XREF: main+81↑j
.text:014000109F    test    r13d, r13d
.text:01400010A2    jz      short loc_140001090
.text:01400010A4    mov     eax, 4
.text:01400010A9    xor     ecx, ecx
.text:01400010AB    nop     dword ptr [rax+rax+00h]
.text:01400010B0
.text:01400010B0 loc_1400010B0:    ; CODE XREF: main+E7↓j
.text:01400010B0    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:01400010B6    add     rcx, rbx
.text:01400010B9    lea     edx, [rax-3]
.text:01400010BC    popcnt  rdx, qword ptr [rsi+rdx*8]
.text:01400010C2    add     rdx, rcx
.text:01400010C5    lea     ecx, [rax-2]
.text:01400010C8    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:01400010CE    add     rcx, rdx
.text:01400010D1    lea     edx, [rax-1]
.text:01400010D4    xor     ebx, ebx
.text:01400010D6    popcnt  rbx, qword ptr [rsi+rdx*8]
.text:01400010DC    add     rbx, rcx
.text:01400010DF    mov     ecx, eax
.text:01400010E1    add     eax, 4
.text:01400010E4    cmp     rdi, rcx
.text:01400010E7    ja      short loc_1400010B0
.text:01400010E9    test    r13d, r13d
.text:01400010EC    jz      short loc_140001090
.text:01400010EE    mov     eax, 4
.text:01400010F3    xor     ecx, ecx
.text:01400010F5    db      2Eh
.text:01400010F5    nop     word ptr [rax+rax+00000000h]
.text:01400010FF    nop
.text:0140001100
.text:0140001100 loc_140001100:    ; CODE XREF: main+137↓j
.text:0140001100    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:0140001106    add     rcx, rbx
.text:0140001109    lea     edx, [rax-3]
.text:014000110C    popcnt  rdx, qword ptr [rsi+rdx*8]
.text:0140001112    add     rdx, rcx
.text:0140001115    lea     ecx, [rax-2]
.text:0140001118    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:014000111E    add     rcx, rdx
.text:0140001121    lea     edx, [rax-1]
.text:0140001124    xor     ebx, ebx
.text:0140001126    popcnt  rbx, qword ptr [rsi+rdx*8]
.text:014000112C    add     rbx, rcx
.text:014000112F    mov     ecx, eax
.text:0140001131    add     eax, 4
.text:0140001134    cmp     rdi, rcx
.text:0140001137    ja      short loc_140001100
.text:0140001139    jmp     loc_140001090
.text:014000113E ; ---------------------------------------------------------------------------
.text:014000113E
.text:014000113E loc_14000113E:    ; CODE XREF: main+25↑j
.text:014000113E    mov     rsi, cs:__imp_?cerr@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cerr
.text:0140001145    lea     rdx, aUsageArraySize ; "usage: array_size in MB"
.text:014000114C    mov     rcx, rsi        ; std::ostream *
.text:014000114F    call    std__operator___std__char_traits_char___
.text:0140001154    mov     rax, [rsi]
.text:0140001157    movsxd  rcx, dword ptr [rax+4]
.text:014000115B    add     rcx, rsi
.text:014000115E    mov     dl, 0Ah
.text:0140001160    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:0140001166    mov     rcx, rsi
.text:0140001169    mov     edx, eax
.text:014000116B    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:0140001171    mov     rcx, rsi
.text:0140001174    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:014000117A    mov     eax, 0FFFFFFFFh
.text:014000117F    jmp     loc_1400013E2
.text:0140001184 ; ---------------------------------------------------------------------------
.text:0140001184
.text:0140001184 loc_140001184:    ; CODE XREF: main+99↑j
.text:0140001184    call    _Xtime_get_ticks_0
.text:0140001189    sub     rax, r14
.text:014000118C    imul    rbp, rax, 64h ; 'd'
.text:0140001190    mov     r14, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout
.text:0140001197    lea     rdx, aUnsigned  ; "unsigned\t"
.text:014000119E    mov     rcx, r14        ; std::ostream *
.text:01400011A1    call    std__operator___std__char_traits_char___
.text:01400011A6    mov     rcx, r14
.text:01400011A9    mov     rdx, rbx
.text:01400011AC    call    cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64)
.text:01400011B2    mov     rbx, rax
.text:01400011B5    mov     rcx, rax        ; std::ostream *
.text:01400011B8    call    std__operator___std__char_traits_char____0
.text:01400011BD    vmovq   xmm0, rbp
.text:01400011C2    vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000
.text:01400011CA    vpunpckldq xmm0, xmm0, xmm8
.text:01400011CF    vmovapd xmm7, cs:__xmm@45300000000000004330000000000000
.text:01400011D7    vsubpd  xmm0, xmm0, xmm7
.text:01400011DB    vpermilpd xmm1, xmm0, 1
.text:01400011E1    vaddsd  xmm6, xmm1, xmm0
.text:01400011E5    vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
.text:01400011ED    mov     r12, cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@N@Z ; std::ostream::operator<<(double)
.text:01400011F4    mov     rcx, rbx
.text:01400011F7    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:01400011FA    mov     rbx, rax
.text:01400011FD    lea     rdx, aSec       ; " sec \t"
.text:0140001204    mov     rcx, rax        ; std::ostream *
.text:0140001207    call    std__operator___std__char_traits_char___
.text:014000120C    vmovq   xmm0, r15
.text:0140001211    vpunpckldq xmm0, xmm0, xmm8
.text:0140001216    vsubpd  xmm0, xmm0, xmm7
.text:014000121A    vpermilpd xmm1, xmm0, 1
.text:0140001220    vaddsd  xmm0, xmm1, xmm0
.text:0140001224    vmulsd  xmm7, xmm0, cs:__real@40c3880000000000
.text:014000122C    vdivsd  xmm1, xmm7, xmm6
.text:0140001230    mov     rcx, rbx
.text:0140001233    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:0140001236    mov     rbx, rax
.text:0140001239    lea     rdx, aGbS       ; " GB/s"
.text:0140001240    mov     rcx, rax        ; std::ostream *
.text:0140001243    call    std__operator___std__char_traits_char___
.text:0140001248    mov     rax, [rbx]
.text:014000124B    movsxd  rcx, dword ptr [rax+4]
.text:014000124F    add     rcx, rbx
.text:0140001252    mov     dl, 0Ah
.text:0140001254    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:014000125A    mov     rcx, rbx
.text:014000125D    mov     edx, eax
.text:014000125F    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:0140001265    mov     rcx, rbx
.text:0140001268    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:014000126E    xor     ebp, ebp
.text:0140001270    call    _Xtime_get_ticks_0
.text:0140001275    mov     r14, rax
.text:0140001278    xor     ebx, ebx
.text:014000127A    jmp     short loc_14000128F
.text:014000127A ; ---------------------------------------------------------------------------
.text:014000127C    align 20h
.text:0140001280
.text:0140001280 loc_140001280:    ; CODE XREF: main+292↓j
.text:0140001280      ; main+2DB↓j ...
.text:0140001280    add     ebp, 2
.text:0140001283    cmp     ebp, 2710h
.text:0140001289    jz      loc_14000131D
.text:014000128F
.text:014000128F loc_14000128F:    ; CODE XREF: main+27A↑j
.text:014000128F    test    r13d, r13d
.text:0140001292    jz      short loc_140001280
.text:0140001294    xor     eax, eax
.text:0140001296    db      2Eh
.text:0140001296    nop     word ptr [rax+rax+00000000h]
.text:01400012A0
.text:01400012A0 loc_1400012A0:    ; CODE XREF: main+2D6↓j
.text:01400012A0    xor     ecx, ecx
.text:01400012A2    popcnt  rcx, qword ptr [rsi+rax*8]
.text:01400012A8    add     rcx, rbx
.text:01400012AB    xor     edx, edx
.text:01400012AD    popcnt  rdx, qword ptr [rsi+rax*8+8]
.text:01400012B4    add     rdx, rcx
.text:01400012B7    xor     ecx, ecx
.text:01400012B9    popcnt  rcx, qword ptr [rsi+rax*8+10h]
.text:01400012C0    add     rcx, rdx
.text:01400012C3    xor     ebx, ebx
.text:01400012C5    popcnt  rbx, qword ptr [rsi+rax*8+18h]
.text:01400012CC    add     rbx, rcx
.text:01400012CF    add     rax, 4
.text:01400012D3    cmp     rax, rdi
.text:01400012D6    jb      short loc_1400012A0
.text:01400012D8    test    r13d, r13d
.text:01400012DB    jz      short loc_140001280
.text:01400012DD    xor     eax, eax
.text:01400012DF    nop
.text:01400012E0
.text:01400012E0 loc_1400012E0:    ; CODE XREF: main+316↓j
.text:01400012E0    xor     ecx, ecx
.text:01400012E2    popcnt  rcx, qword ptr [rsi+rax*8]
.text:01400012E8    add     rcx, rbx
.text:01400012EB    xor     edx, edx
.text:01400012ED    popcnt  rdx, qword ptr [rsi+rax*8+8]
.text:01400012F4    add     rdx, rcx
.text:01400012F7    xor     ecx, ecx
.text:01400012F9    popcnt  rcx, qword ptr [rsi+rax*8+10h]
.text:0140001300    add     rcx, rdx
.text:0140001303    xor     ebx, ebx
.text:0140001305    popcnt  rbx, qword ptr [rsi+rax*8+18h]
.text:014000130C    add     rbx, rcx
.text:014000130F    add     rax, 4
.text:0140001313    cmp     rax, rdi
.text:0140001316    jb      short loc_1400012E0
.text:0140001318    jmp     loc_140001280
.text:014000131D ; ---------------------------------------------------------------------------
.text:014000131D
.text:014000131D loc_14000131D:    ; CODE XREF: main+289↑j
.text:014000131D    call    _Xtime_get_ticks_0
.text:0140001322    sub     rax, r14
.text:0140001325    imul    rbp, rax, 64h ; 'd'
.text:0140001329    mov     rdi, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout
.text:0140001330    lea     rdx, aUint64T   ; "uint64_t\t"
.text:0140001337    mov     rcx, rdi        ; std::ostream *
.text:014000133A    call    std__operator___std__char_traits_char___
.text:014000133F    mov     rcx, rdi
.text:0140001342    mov     rdx, rbx
.text:0140001345    call    cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64)
.text:014000134B    mov     rdi, rax
.text:014000134E    mov     rcx, rax        ; std::ostream *
.text:0140001351    call    std__operator___std__char_traits_char____0
.text:0140001356    vmovq   xmm0, rbp
.text:014000135B    vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000
.text:0140001363    vsubpd  xmm0, xmm0, cs:__xmm@45300000000000004330000000000000
.text:014000136B    vpermilpd xmm1, xmm0, 1
.text:0140001371    vaddsd  xmm6, xmm1, xmm0
.text:0140001375    vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
.text:014000137D    mov     rcx, rdi
.text:0140001380    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:0140001383    mov     rdi, rax
.text:0140001386    lea     rdx, aSec       ; " sec \t"
.text:014000138D    mov     rcx, rax        ; std::ostream *
.text:0140001390    call    std__operator___std__char_traits_char___
.text:0140001395    vdivsd  xmm1, xmm7, xmm6
.text:0140001399    mov     rcx, rdi
.text:014000139C    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:014000139F    mov     rdi, rax
.text:01400013A2    lea     rdx, aGbS       ; " GB/s"
.text:01400013A9    mov     rcx, rax        ; std::ostream *
.text:01400013AC    call    std__operator___std__char_traits_char___
.text:01400013B1    mov     rax, [rdi]
.text:01400013B4    movsxd  rcx, dword ptr [rax+4]
.text:01400013B8    add     rcx, rdi
.text:01400013BB    mov     dl, 0Ah
.text:01400013BD    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:01400013C3    mov     rcx, rdi
.text:01400013C6    mov     edx, eax
.text:01400013C8    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:01400013CE    mov     rcx, rdi
.text:01400013D1    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:01400013D7    mov     rcx, rsi        ; Block
.text:01400013DA    call    cs:__imp_free
.text:01400013E0    xor     eax, eax
.text:01400013E2
.text:01400013E2 loc_1400013E2:    ; CODE XREF: main+17F↑j
.text:01400013E2    vmovaps xmm6, [rsp+98h+var_78]
.text:01400013E8    vmovaps xmm7, [rsp+98h+var_68]
.text:01400013EE    vmovaps xmm8, [rsp+98h+var_58]
.text:01400013F4    add     rsp, 58h
.text:01400013F8    pop     rbx
.text:01400013F9    pop     rbp
.text:01400013FA    pop     rdi
.text:01400013FB    pop     rsi
.text:01400013FC    pop     r12
.text:01400013FE    pop     r13
.text:0140001400    pop     r14
.text:0140001402    pop     r15
.text:0140001404    retn
.text:0140001404 main            endp

咖啡湖规范更新“POPCNT指令执行时间可能比预期更长”。

2021-01-30 02:44:14

缺点：虚假数据依赖性（编译器甚至不知道）

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

popcnt  src, dest

似乎对目标寄存器dest有错误的依赖性。即使该指令只向其写入数据，该指令仍将等待dest就绪后再执行。这种错误的依赖性（现在）被Intel记录为勘误表HSD146（Haswell）和SKL029（Skylake）

Skylake为lzcnt和tzcnt修复了此问题。Cannon Lake（和Ice Lake）为popcnt修复了这个问题。bsf/bsr具有真正的输出依赖性：对于输入=0，输出未修改。（但无法利用内部函数的优势——只有AMD记录了它，编译器不会公开它。）

（是的，这些指令都在同一个执行单元上运行）。

这种依赖性不仅仅支持单个循环迭代中的4个popcnt。它可以跨循环迭代，使得处理器无法并行化不同的循环迭代。

无符号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=本地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是如何在硬件中实现的？）。对于这些指令，英特尔将input=0的整数结果记录为“undefined”（ZF=1），但英特尔硬件实际上提供了更有力的保证，以避免损坏旧软件：未修改输出。AMD记录了这种行为。

大概是不方便让这个执行单元的一些uop依赖于输出，但其他的不依赖于输出。

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该基准会改变（false）依赖链中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

2014-08-01 22:41:20

首先，尝试估计峰值性能-检查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），并在最后将它们相加。或者甚至创建一个计数数组[8]并累积到其元素中——也许，它甚至会被矢量化，您将获得更好的吞吐量。

P.S.，永远不要运行基准测试一秒钟，先预热核心，然后运行循环至少10秒或更好的100秒。否则，您将在硬件中测试电源管理固件和DVFS实现：）

P.P.S.我听到了关于基准测试应该运行多长时间的无尽争论。最聪明的人甚至会问为什么10秒不是11秒或12秒。我应该承认这在理论上很有趣。在实践中，您只需连续运行基准测试100次并记录偏差。这很有趣。大多数人都会更改源代码，并在这之后运行测试台一次，以获取新的性能记录。做正确的事情。

还不相信？只需通过assp1r1n3使用高于C版本的基准测试(https://stackoverflow.com/a/37026212/9706746)在重试循环中尝试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/s

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

每分钟。最后，关于“接受的答案”和其他错误；-）

让我们用assp1r1n3的答案——他有2.5Ghz的核心。POPCNT有1个时钟输出，他的代码使用64位POPCNT。因此，对于他的设置，数学是2.5Ghz*1时钟*8字节=20GB/s。他看到的是25Gb/s，可能是由于涡轮增压到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-4870小时

该内核可以运行到3.7Ghz，其硬件的实际最大速率为29.6GB/s。那么，另一个4GB/s在哪里？也许，它花费在每个迭代中的循环逻辑和其他周围代码上。

现在，这种错误依赖关系在哪里？硬件几乎以峰值速率运行。也许我的数学不好，有时会这样：）

P.P.P.P.S.仍然有人认为硬件错误是罪魁祸首，所以我遵循建议，创建了内联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;
}

2018-10-23 20:45:00

   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

2014-08-02 03:48:08

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

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

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

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

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

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

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

2014-08-01 20:12:53

用64位替换32位循环计数器会导致英特尔CPU上_mm_popcnt_u64的性能偏差

推荐文章

最新文章

标签