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

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

为什么要 static 改变性能？

有问题的行： uint64_t size = atol(argv[1])<<20;

简短答案

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

长答案

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

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

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

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