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




将32位循环计数器替换为64位会导致疯狂的性能偏差 (7)

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

为什么要 static 改变性能?

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

简短答案

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

长答案

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

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

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

我一直在寻找最快的方法来 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

是的,另一种选择 。 使用 u64 时,我们仍然具有26 GB / s的快速速度,但是我们设法将 u64 至少从13 GB / s升级到20 GB / s! 在我同事的PC上, u64 版本变得比 u64 版本更快,产生了最快的结果。 可悲的是,这仅适用于 g++clang++ 似乎并不关心 static

我的问题

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

  • u64u64 之间 u64
  • 如何用恒定的缓冲区大小替换非常数会触发次 优代码
  • 插入 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 关键字所看到的那样,甚至缓冲区的存储类型也可以产生巨大的变化! 将来,在编写对系统性能至关重要的紧密而又热的循环时,我将始终在各种编译器上测试各种替代方案。

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


首先,尝试评估最高性能-检查 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具有如此错误的依赖性?

我们只能推测,但是很可能英特尔对许多双操作数指令具有相同的处理方式。 诸如 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 : 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




compiler-optimization