optimizing software in c++ an optimization guide for windows linux and mac platforms

首先，尝试评估最高性能-检查 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://.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 /秒

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 ://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 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;
}

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

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

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

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

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

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

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

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

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

我编写了一个等效的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位指令的实际速度/延迟优势。

（注意：我搞砸了程序集，可能在不注意的情况下破坏了某些东西。我不这样认为。）

罪魁祸首：错误的数据依赖关系 （并且编译器甚至没有意识到）

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

popcnt  src, dest

似乎对目标寄存器 dest 有错误的依赖性。 即使指令仅写入指令，指令也会等到 dest 准备好后再执行。

这种依赖关系不只是从单个循环迭代中容纳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具有如此错误的依赖性？

我们只能推测，但是很可能英特尔对许多双操作数指令具有相同的处理方式。 诸如 add ， sub 类的常见指令采用两个操作数，它们都是输入。 因此，英特尔可能 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 : 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