我在寻找到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	" << count << '	' << (duration/1.0E9) << " sec 	"
             << (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	"  << count << '	' << (duration/1.0E9) << " sec 	"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

正如您看到的我们正在其中x从命令行读取x兆字节大小创建随机的数据的缓冲区。然后,循环访问该缓冲区和使用展开的 x86 版本popcount内部执行 popcount。若要获得更精确的结果,我们做 popcount 10000 次。我们测量 popcount 的时间。以大写形式中,内部循环变量没有unsigned,在较低的情况下,内部循环变量uint64_t我认为,这应该没有区别,但相反的是这种情况。

(绝对是不可思议的) 结果

编译此类 (g + + 版本︰ Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

下面是结果上我Haswell CPU核心 i7-4770 K @ 3.50 g h z,运行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,因而常量值替换非常数导致deoptimization老实说,我还不知道这怎么回事这里 !但现在到clang++的新版本︰

  • 无符号 41959360000 0.677009 秒15.4884 GB/s
  • uint64_t 41959360000 0.676909 秒15.4906 GB/s

等待什么?现在,这两个版本丢弃于数 15 GB/s。因此,由常量值甚至领导为 Clang 慢速两种情况下的代码替换非常量 !

我问一个常青藤桥CPU 来编译我的基准测试与同事。因此它似乎不是 Haswell,他是类似的结果。因为两个编译器产生奇怪的结果,它也似乎不是一个编译器错误。我们没有 AMD CPU,因此我们无法只测试英特尔® 台式机主板。

更多疯狂,请 !

采用第一个示例 (即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

Yay,但另一种选择我们仍然会快速 26 GB/s 的u32,但我们设法获得u64至少 13 GB/s 为 20 GB/s 的版本 !在我的 collegue PC 上, u64版本变得甚至比u32版本,生成的所有结果最快。不幸的是,这仅适用于g++clang++似乎不关心static.

我的问题

您可以解释这些结果吗?特别是︰

  • 如何可以有u32u64之间的这种差异?
  • 如何按固定缓冲区大小触发器代码较少获得最佳更换非常数?
  • 如何插入static关键字使u64循环更快?在我的 collegue 计算机上甚至比原始代码 !

我知道,优化是一个复杂的地区,但是,我从不认为这种很小的更改可能会导致执行时间100%差异,小的因素,如固定缓冲区大小可以再次混合结果完全。当然,我始终希望能够 popcount 版本 26 GB/s。我可以想到的只有可靠方法是复制粘贴此用例和使用内联程序集的程序集。这是唯一的方法我可以除去似乎在很小的更改上转悲伤的编译器。你觉得怎么样?是否有另一种方法可靠地获得大多数性能的代码?

反汇编

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

从 26 GB/s 机型g + + / u32 / 非 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 / 非 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 / 非 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关键字大小变量的前面插入,即使缓冲区存储类型可以带来巨大的不同 !在将来,我将始终测试各种替代方法在各个编译器上的编写系统性能至关重要的真正紧密和热循环时。

一个有趣的问题是还性能差异仍如此之高虽然我有已打开循环四倍。因此,即使您取消,则可以仍然受到主要性能偏差。相当有趣。

2014-08-01 10:33:29
问题评论:

您似乎命中了一个电源优化管道很多启发而强硬坏情况。但是是什么以及位于何处是难于说而不查看程序集的代码中,您可以添加它吗?

好了,这样一些变化的代码生成标志 (尤其是-mtune=core-avx2,它生成适用于处理器,但调整适用于 Haswell 型处理器的代码)、 我除掉多余预取指令,和结果是 [+ /-几位小数] 相同两个款式。但那是上而不是旧的 AMD 处理器,所以不真的很奇怪。在我处理器上,clang + + 还会生成相同的速度代码。

所有我可以说是 WTF。有一点有趣的发展顺序添加和 popcounts。缓慢的所有版本都都添加/popcount 完全交错。快速的不交错,或者只能部分地交错分布。此外,可能有假的输入依赖项在 popcount 的输出寄存器。不管怎样,我有约会,因此我不会再看一段时间。(它在 Windows/VS2013/Haswell repros。没有任何区别上 Windows/VS2013/Piledriver。)

@AdrianMcCarthy︰ 它可能是,但是两个循环使用相同的缓冲区,因此一个正在快速和一个速度慢不能解释的。此外,我很确信我 malloc does 8 字节对齐。我也尝试过使用memalign没有任何区别。似乎确实是只有生成不同的程序集指令。

@gexicide 确切地说,证据似乎表明它只是性能 pothole 在英特尔处理器上。他们通常不将它们记录下来。

回答:

罪魁祸首︰ 假数据相关性(和编译器不会提到它)

Sandy/常青藤桥接器和 Haswell 处理器,该指令︰

popcnt src, dest

似乎有假从属关系的目标注册dest即使对它只写入指令,指令将等到dest执行之前已准备就绪。

这种依赖关系不只是占用了 4 popcnts 从单个循环迭代。它可以使得处理器并行化不同的循环迭代的循环迭代中执行。

unsigneduint64_t和其他的调整并不直接影响问题。但是,这些影响将寄存器赋给变量的寄存器分配。

在您的情况下,速度是什么粘在根据不同的寄存器分配器决定执行 (false) 依赖链的直接结果。

  • 13 GB/s 具有链︰ popcnt-添加-popcnt-popcnt--> 下一次迭代
  • 15 GB/s 具有链︰ popcnt-添加-popcnt-添加--> 下一次迭代
  • 20 GB/s 具有链︰ popcnt popcnt--> 下一次迭代
  • 26 GB/s 具有链︰ popcnt popcnt--> 下一次迭代

20 GB/s 和 26 GB/s 的区别似乎是次要项目的间接寻址。无论如何,处理器开始击中其他瓶颈,一旦达到此速度。


若要测试这一点,我使用内联程序集来绕过编译器并得到我想要的程序集完全。我也会分裂count变量中断其他可能乱动基准测试的所有依赖项。

下面是结果︰

@ 3.5 g h z 的 Sandy Bridge 至强︰(在底部可以找到完整的测试代码)

  • 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并不是完全的最常用的指令。因此,它并不是主要的编译器可能错过类似意外情况发生。也似乎没有文档任何地方提及此问题。英特尔不会披露,如果,外人会知道直到有人的可能性为它运行。

CPU 为什么有这种假的相关性?

我们只可以推测,但它可能是英特尔已对两个操作数的说明很多的相同处理。addsub等的通用指令采取这两种是输入的两个操作数。因此英特尔可能 shoved 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  
	"
                "add %4, %0     
	"
                "popcnt %5, %5  
	"
                "add %5, %1     
	"
                "popcnt %6, %6  
	"
                "add %6, %2     
	"
                "popcnt %7, %7  
	"
                "add %7, %3     
	"
                : "+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	" << count << '	' << (duration/1.0E9) << " sec 	"
            << (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   
	"
                "add %%rax, %0      
	"
                "popcnt %5, %%rax   
	"
                "add %%rax, %1      
	"
                "popcnt %6, %%rax   
	"
                "add %%rax, %2      
	"
                "popcnt %7, %%rax   
	"
                "add %%rax, %3      
	"
                : "+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   	"  << count << '	' << (duration/1.0E9) << " sec 	"
            << (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   
	"   // <--- Break the chain.
                "popcnt %4, %%rax   
	"
                "add %%rax, %0      
	"
                "popcnt %5, %%rax   
	"
                "add %%rax, %1      
	"
                "popcnt %6, %%rax   
	"
                "add %%rax, %2      
	"
                "popcnt %7, %%rax   
	"
                "add %%rax, %3      
	"
                : "+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	"  << count << '	' << (duration/1.0E9) << " sec 	"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

同样有趣的准则可以在以下位置找到︰ http://pastebin.com/kbzgL8si
此基准各不相同 (false) 依赖关系链中的popcnts 的数。

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

那么,有没有地方可以归档 bug 报告英特尔的处理器的地方吗?

@C.R。或相反 GCC 和 MSVC bug。它是硬件的容易更新来解决大量的已发布比编译器。因为解决办法非常简单 (xor reg reg),我不希望英特尔要"解决"这个问题不久。如果它是一个正确的问题,它需要进行修复。在这种情况下它是只罕见指令上的中等性能下降。

@gexicide gnasher729 是上发现的。xor不进行一次迭代速度较快,但它允许下一次迭代中,以第一次迭代完成之前开始。rax依赖强制进行 sequentialized 的迭代。一旦中断使用xor的相关性,处理器将能够并行运行的多个迭代。您还可以将 xor 之前每个popcnt,但以来已经找到办法采用并行迭代中使用所有这些执行单元处理器不提供许多其他的加速。

这意味着,实际的解决方法是使用 AMD 处理器;-)

报告为 GCC bug,有人将肯定修复/工作在其周围。

我向上等效 C 程序进行试验,编码的我可以确认此奇怪的行为。更重要的是, gcc认为 (它可能应size_t吗...) 的 64 位整数来会更好,为使用uint_fast32_t原因 gcc 使用 64 位 uint。

我做了一些与程序集来︰
只需采用 32 位版本,替换所有 32-位说明/寄存器中内部的 popcount 循环的程序的 64 位版本。观察︰ 代码是只是尽可能快的 32 位版本 !

这显然是黑客攻击,如变量的大小不是真正 64 位程序的其他部分仍使用 32 位版本,但是,只要内部 popcount 循环主宰的性能,这是一个不错的起点。

然后我从 32 位版本的程序中复制内部循环代码,黑客攻击它最多是 64 位,fiddled 使用的寄存器,使其内部循环的 64 位版本的替代。此代码还可以运行 32 位版本作为快速。

我的结论是这种错误指令由编译器,不是实际的速度滞后利用 32 位指导计划。

(注意︰ 我黑了程序集,可能破坏了一些没有注意到。我不想这样。

这不是答案,但很难阅读是否将结果放在注释中。

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

与 clang 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

与 clang 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版具有较大的代码大小,但这并没有影响我的至强 CPU。这样速度较慢的 64 位版本。

  • 使用说明。请注意不仅循环计数,但缓冲区中的两个版本的 32 位和 64 位索引的访问。访问与 64 位对方的请求专用 64 位寄存器的指针和寻址,虽然可以使用直接的 32 位偏移量。这可能会更快地使 32 位版本。

  • 在 64 位编译只发出指令 (即预取)。这使得 64 位速度更快。

三个因素在一起的观察一些似乎矛盾的结果匹配。

令人感兴趣,可以添加编译器版本和编译器标志?最好的做法是,在您的计算机上结果转向,即,使用 u64 速度更快到目前为止,我永远不会想到关于哪种类型我循环变量都有,但似乎我需要思考下一次两次:)。

@gexicide︰ 我不会对跳转从 16.8201 16.8126 更"快"。

@Mehrdad: 跳转,我的意思是12.916.8,之间因此unsigned较快这里。在我的准则,相反是这种情况,即为unsigned的 26, uint64_t的 15

@gexicide 让您请注意解决缓冲区 [i] 的差异吗?

@Calvin︰ 不,您什么意思?

我试图与 Visual Studio 2013 明示,而不索引,更加快了流程中使用指针。我怀疑这是因为偏移量 + 寄存器,而不是偏移量 + 登记的地址是 + (注册 << 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	"  << count << '	' << (duration/1.0E9) << " sec 	"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

程序集代码︰ r10 = bfrptr,r15 = bfrend,rsi = count,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

我无法给出权威的回答,但概述了可能的原因。此引用显示十分明白,对于循环正文中的说明进行操作有延迟和吞吐量之间比例为 3:1。它还显示了多个派单的效果。因为有 (授予-或-带) 三个整数单位在现代 x86 处理器,它通常是可能的调度每个周期的三个指令。

所以,之间峰值管道和多个调度性能和这些机制的失败,我们有六性能的因素。它具有很好知道答案的 x86 指令集便于相当古怪的破损发生的复杂性。上述文档具有极好的示例︰

64 位右移位的奔腾 4 性能是真的很差。64 位左的移,以及所有 32-位倒班具有可接受的性能。似乎不很好地设计数据路径高 32 位 ALU 低 32 位。

我亲自到奇怪的用例,其中热循环运行得较慢的四核芯片 (如果我记得 AMD) 特定核心运行。我们实际上获得性能更好的地图减少计算通过关闭该核心。

我猜测这是争夺整数单位︰ popcnt、 循环计数器和地址计算可以全速与 32 位通用计数器,几乎所有运行,但 64 位计数器会导致争用,管线停滞。由于仅有大约 12 周期总,可能 4 周期,通过多个派单,每执行循环正文,单隔栏将无法合理地影响运行时间的 2 倍。

通过使用一个静态变量,我猜只是导致次要重新排序的指令,导致的更改是 32 位代码是在争夺一些引爆点的另一个线索。

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

遗憾的是,以往以来 (酷睿 2?) 有几乎没有 32 位和 64 位整数操作除了乘/除-此代码中不存在之间的性能差异。

@Gene︰ 注意所有版本都存储寄存器中,而绝不会的大小从循环中的堆栈中阅读。因此,地址计算不能组合,至少不在循环中。

@Gene︰ 有趣的解释,确实 !但它没有解释 WTF 要点︰ 此 64 位速度低于由于管道隔 32 位是一回事。但如果出现这种情况,不应的 64 位版本是可靠地低于 32 位之一?相反,三个不同的编译器发出的 32 位版本甚至效率低下的代码时使用编译时常数缓冲区大小;将缓冲区的大小更改为静态再次完全改变的事情。即使是在情况下我的同事的计算机上 (和 Calvin 的答案) 的 64 位版本速度更快 !它似乎是绝对不可预知。

是我点的 @Mysticial。IU,总线时间等零争夺时没有峰值性能差异。该引用清楚地显示。争用使所有不同的内容。下面是一个示例与英特尔核心宣传:"在设计中包含的一种新技术是宏操作融合,用于组合两个 x86 为单个微操作的说明。例如,通用的代码序列像跟一个条件跳转的比较将变为单个微 op.遗憾的是,这项技术无法在 64 位模式下。"我们有比例为 2:1 的执行速度。

我看到你所说,@gexicide,但您我意味着更推断。我并说的代码的运行速度最快的保持完全的管道和调度队列。这种情况是脆弱的。类似于总数据流量和指令重新排序添加 32 位次要更改是足以破坏它。简单地说,调整和测试是仅方式正向 OP 断言是正确的。

请输入您的翻译

Replacing a 32-bit loop count variable with 64-bit introduces crazy performance deviations

确认取消