c++ - 为什么其中一个比另一个快得多？

Question

我正在编写C++代码以查找内存中的第一个非0xFF字节。为了利用bitscanforward，我编写了非常喜欢的内联汇编代码。但是为了“可读性”以及将来的证明(即SIMD矢量化)，我想我会给g++优化器一个机会。 g++没有向量化，但是它确实达到了与我相同的非SIMD解决方案。但是由于某种原因，它的版本运行速度要慢得多，速度要慢260000倍(即我必须循环260,000倍才能获得相同的执行时间)。我除了有一些区别，但没有那么多!可以指出为什么会这样吗？我只是想知道，以免在将来的内联汇编代码中出错。

接下来是C++的起点(就计数准确性而言，此代码中有一个错误，但是为了进行速度测试，我已经对其进行了简化):

uint64_t count3 (const void *data, uint64_t const &nBytes) {
      uint64_t count = 0;
      uint64_t block;
      do {
         block = *(uint64_t*)(data+count);
         if ( block != (uint64_t)-1 ) {
/*       count += __builtin_ctz(~block);   ignore this for speed test*/
            goto done;
          };
        count += sizeof(block);
      } while ( count < nBytes );
done:
      return (count>nBytes ? nBytes : count);
}

g++提出的汇编代码是:

_Z6count3PKvRKm:
.LFB33:
    .cfi_startproc
    mov rdx, QWORD PTR [rsi]
    xor eax, eax
    jmp .L19
    .p2align 4,,10
    .p2align 3
.L21:
    add rax, 8
    cmp rax, rdx
    jnb .L18
.L19:
    cmp QWORD PTR [rdi+rax], -1
    je  .L21
.L18:
    cmp rax, rdx
    cmova   rax, rdx
    ret
    .cfi_endproc

我的内联程序集是

_Z6count2PKvRKm:
.LFB32:
    .cfi_startproc
    push    rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    mov rbx, QWORD PTR [rsi]

    # count trailing bytes of 0xFF 
    xor     rax, rax  
.ctxff_loop_69:          
    mov     r9,  QWORD PTR [rdi+rax] 
    xor     r9, -1          
    jnz   .ctxff_final_69    
    add     rax, 8     
    cmp     rax, rbx 
    jl    .ctxff_loop_69    
.ctxff_final_69:         
    cmp     rax,rbx  
    cmova   rax,rbx  
    pop rbx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc

据我所知，除了将数据字节与0xFF进行比较的方法外，它基本上是相同的。但是我无法相信这会导致计算时间的巨大差异。

可以想见我的测试方法导致了错误，但是我要做的就是在下面的简单for循环中更改函数名称和迭代长度，如下所示:(当N为1 << 20，并且'a'的所有字节除外最后一个字节是0xFF)

测试1

   for (uint64_t i=0; i < ((uint64_t)1<<15); i++) {
      n = count3(a,N);
   }

测试2

   for (uint64_t i=0; i < ((uint64_t)1<<33); i++) {
      n = count2(a,N);
   }

编辑:

这是我真正的内联汇编代码，其中包含SSE count1()，x64-64 count()，然后是普通的C++版本 count0()和 count3()。我掉进了这个兔子洞，希望我可以让g++拿起自己的 count0()并独自到达 count1()甚至 count2()。但是可惜它什么也没做，绝对没有优化:(我应该补充一点，我的平台没有AVX2，这就是为什么我希望让g++自动矢量化，以便代码在我更新平台时自动更新。

就内联汇编中显式寄存器的使用而言，如果我没有显式地使用它们，则g++将为 nBytes和 count重用相同的寄存器。

在加速方面，我发现真正的好处仅仅是在XMM和QWORD之间的“循环展开”效果，我可以在 count2()中复制该效果。

uint32_t count0(const uint8_t *data, uint64_t const &nBytes) {

  for (int i=0; i<nBytes; i++)
    if (data[i] != 0xFF) return i;

  return nBytes;
}
uint32_t count1(const void *data, uint64_t const &nBytes) {
  uint64_t count;
  __asm__("# count trailing bytes of 0xFF \n"
    "   xor     %[count], %[count]  \n"
    " vpcmpeqb  xmm0, xmm0, xmm0  \n" // make array of 0xFF

    ".ctxff_next_block_%=:        \n"
    " vpcmpeqb  xmm1, xmm0, XMMWORD PTR [%[data]+%[count]]  \n"
    " vpmovmskb r9, xmm1         \n"
    " xor     r9, 0xFFFF       \n" // test if all match (bonus negate r9)
    " jnz   .ctxff_tzc_%=        \n" // if !=0, STOP & tzcnt negated r9
    " add     %[count], 16       \n" // else inc
    " cmp     %[count], %[nBytes] \n"
    " jl    .ctxff_next_block_%=  \n" // while count < nBytes, loop
    " jmp   .ctxff_done_%=      \n" // else done + ALL bytes were 0xFF

    ".ctxff_tzc_%=:           \n"
    " tzcnt   r9, r9          \n" // count bytes up to non-0xFF
    " add     %[count], r9    \n"

    ".ctxff_done_%=:          \n" // more than 'nBytes' could be tested,
    " cmp     %[count],%[nBytes]  \n" // find minimum
    " cmova   %[count],%[nBytes]  "
    : [count] "=a" (count)
    : [nBytes] "b" (nBytes), [data] "d" (data)
    : "r9", "xmm0", "xmm1"
  );
  return count;
};

uint64_t count2 (const void *data, uint64_t const &nBytes) {
    uint64_t count;
  __asm__("# count trailing bytes of 0xFF \n"
    "    xor     %[count], %[count]  \n"

    ".ctxff_loop_%=:          \n"
    "    mov     r9,  QWORD PTR [%[data]+%[count]] \n"
    "    xor     r9, -1          \n" 
    "    jnz   .ctxff_final_%=    \n"
    "    add     %[count], 8     \n" 
    "    mov     r9,  QWORD PTR [%[data]+%[count]] \n"  // <--loop-unroll
    "    xor     r9, -1          \n" 
    "    jnz   .ctxff_final_%=    \n"
    "    add     %[count], 8     \n" 
    "    cmp     %[count], %[nBytes] \n"
    "    jl    .ctxff_loop_%=    \n"
    "    jmp   .ctxff_done_%=   \n" 

    ".ctxff_final_%=:            \n"
    "    bsf   r9,  r9           \n" // do tz count on r9 (either of first QWORD bits or XMM bytes)
    "    shr     r9,  3          \n" // scale BSF count accordiningly
    "    add     %[count], r9    \n"
    ".ctxff_done_%=:          \n" // more than 'nBytes' bytes could have been tested,
    "    cmp     %[count],%[nBytes]  \n" // find minimum of count and nBytes
    "    cmova   %[count],%[nBytes]  "
    : [count] "=a" (count)
    : [nBytes] "b" (nBytes), [data] "D" (data)
    : "r9"
  );
  return count;
}

inline static uint32_t tzcount(uint64_t const &qword) {
  uint64_t tzc;
  asm("tzcnt %0, %1" : "=r" (tzc) : "r" (qword) );
  return tzc;
};

uint64_t count3 (const void *data, uint64_t const &nBytes) {
      uint64_t count = 0;
      uint64_t block;
      do {
        block = *(uint64_t*)(data+count);
         if ( block != (uint64_t)-1 ) {
           count += tzcount(~block);
            goto done;
          };
        count += sizeof(block);
      } while ( count < nBytes );
done:
      return (count>nBytes ? nBytes : count);
}

uint32_t N = 1<<20;

int main(int argc, char **argv) {

  unsigned char a[N];
  __builtin_memset(a,0xFF,N);

  uint64_t n = 0, j;
   for (uint64_t i=0; i < ((uint64_t)1<<18); i++) {
      n += count2(a,N);
   }

 printf("\n\n %x %x %x\n",N, n, 0);   
  return n;
}

Answer 1

回答问题标题
现在，您已经发布了完整的代码:，对count2(a,N)的调用已从main 中的循环中吊起了。循环次数(例如1<<18)仍然会稍微增加执行时间，但循环所要做的只是一个add。编译器对其进行了优化，使其看起来更像此源:

uint64_t hoisted_count = count2(a,N);
for (uint64_t i=0; i < ((uint64_t)1<<18); i++) {
   n += hoisted_count;   // doesn't optimize to a multiply
}

没有寄存器冲突: %rax保留从 count2内联的asm语句的结果。然后将其用作微小循环中的源操作数，通过重复加法将其乘以 n。
(请参阅 Godbolt Compiler Explorer上的asm，并注意有关 void* s上算术的所有编译器警告:clang拒绝编译您的代码):

## the for() loop in main, when using count2()
.L23:
    addq    %rax, %r12
    subq    $1, %rdx
    jne     .L23

%rdx是这里的循环计数器， %r12是保存 n的累加器。 IDK为什么gcc不能将其优化为恒定时间乘法。
大概慢了260k的版本无法使整个 count2脱离循环。从gcc的角度来看，内联的asm版本要简单得多:asm语句被视为其输入的纯函数，而gcc甚至不知道它与内存有关的任何信息。 C版本占用大量内存，要证明它可以被吊起则要复杂得多。
在asm语句中使用 "memory" clobber确实可以防止在我检查Godbolt时将其吊起。您可以从 vector 块之前的 main中判断是否存在分支目标。
但是无论如何， 的运行时间将类似于n + rep_count与n * rep_count 。 asm语句不使用 "memory"破坏符或任何内存输入来告诉gcc它读取了输入指针指向的内存。 可能会发生错误的优化，例如被悬卡在修改数组元素的循环之外。 (有关使用虚拟匿名 struct内存输入而不是毯子 "memory" Clobber的示例，请参阅 Clobbers section in the manual。不幸的是，当内存块没有编译时常数时，我认为这种方法不可用。)
我认为 -fno-inline阻止了提升，因为该函数未标记 __attribute__((const))或 __attribute__((pure))稍弱，以指示没有副作用。内联后，优化器可以在asm语句中看到这一点。

count0并未针对任何好的进行优化，因为gcc和clang无法自动向量化循环，而循环在开始时就不知道迭代次数。也就是说，即使他们被告知可以安全地访问超出搜索循环结束点的末尾(例如使用 strlen作为函数arg)，也可以安全地访问 memchr或 char buf[static 512]之类的东西，或者通常是搜索循环。

针对您的asm代码的优化:
就像我对这个问题的评论一样，与 xor reg, 0xFFFF/ jnz相比，使用 cmp reg, 0xFFFF/ jnz是愚蠢的，因为cmp/jcc可以将宏融合到一个比较分支的uop中。 cmp reg, mem/ jne也可以进行宏熔合，因此执行加载/异或运算的标量版本每次比较使用3倍的微指令。 (当然，如果不使用索引寻址模式，Sandybridge只能对其进行微熔合。此外，SnB只能对每个解码块进行一对宏熔合，但是您可能会得到第一个cmp/jcc和无论如何， xor是一个坏主意。最好只在 xor之前添加 tzcnt，因为将uops保存在循环中比代码大小或uops total更重要。
您的标量循环是9个融合域微指令，每2个时钟一次迭代就发出了太多。 (SnB是一个4倍宽的管道，对于微小的循环，它实际上可以维持这种状态。

在问题的第一个版本中缩进代码，使 count += __builtin_ctz与 if处于同一级别，这使我认为您正在计算不匹配块，而不仅仅是找到第一个。
不幸的是，我为该答案的第一个版本编写的asm代码无法解决与OP更新和更清晰的代码相同的问题。对于SSE2 asm，请参见此答案的旧版本，该版本使用pcmpeqb/paddb来计数0xFF字节，并使用psadbw来计算水平和以避免环绕。

使用SSE2(或AVX)加快速度:
分支到 pcmpeq的结果比分支到 cmp的花费更多。如果我们的搜索数组很大，我们可以使用一个循环来一次测试多个 vector ，然后找出中断循环后哪个字节被我们命中了。
此优化也适用于AVX2。
这是我的尝试，将GNU C内联汇编与 -masm=intel语法一起使用。 (尤其是当进行内联时，内部函数可能会产生更好的结果，因为编译器了解内部函数，因此可以通过内部函数进行常量传播，诸如此类。OTOH，如果您了解交易，通常可以使用手写asm击败编译器。 -offs和您所针对的微体系结构。此外，如果您可以安全地做出一些假设，但是您无法轻松地将它们传达给编译器。)

#include <stdint.h>
#include <immintrin.h>

// compile with -masm=intel
// len must be a multiple of 32  (TODO: cleanup loop)
// buf should be 16B-aligned for best performance
size_t find_first_zero_bit_avx1(const char *bitmap, size_t len) {
    // return size_t not uint64_t.  This same code works in 32bit mode, and in the x32 ABI where pointers are 32bit

    __m128i pattern, vtmp1, vtmp2;
    const char *result_pos;
    int tmpi;

    const char *bitmap_start = bitmap;

    asm (  // modifies the bitmap pointer, but we're inside a wrapper function
      "vpcmpeqw   %[pat], %[pat],%[pat]\n\t"          // all-ones

      ".p2align 4\n\t"   // force 16B loop alignment, for the benefit of CPUs without a loop buffer
      //IACA_START  // See the godbolt link for the macro definition
      ".Lcount_loop%=:\n\t"
//      "  movdqu    %[v1], [ %[p] ]\n\t"
//      "  pcmpeqb   %[v1], %[pat]\n\t"        // for AVX: fold the load into vpcmpeqb, making sure to still use a one-register addressing mode so it can micro-fuse
//      "  movdqu    %[v2], [ %[p] + 16 ]\n\t"
//      "  pcmpeqb   %[v2], %[pat]\n\t"

      "  vpcmpeqb  %[v1], %[pat], [ %[p] ]\n\t"  // Actually use AVX, to get a big speedup over the OP's scalar code on his SnB CPU
      "  vpcmpeqb  %[v2], %[pat], [ %[p] + 16 ]\n\t"

      "  vpand     %[v2], %[v2], %[v1]\n\t"         // combine the two results from this iteration
      "  vpmovmskb  %k[result], %[v2]\n\t"
      "  cmp       %k[result], 0xFFFF\n\t"          // k modifier: eax instead of rax
      "  jne     .Lfound%=\n\t"

      "  add       %[p], 32\n\t"
      "  cmp       %[p], %[endp]\n\t"              // this is only 2 uops after the previous cmp/jcc.  We could re-arrange the loop and put the branches farther apart if needed.  (e.g. start with a vpcmpeqb outside the loop, so each iteration actually sets up for the next)
      "  jb     .Lcount_loop%=\n\t"
      //IACA_END

      // any necessary code for the not-found case, e.g. bitmap = endp
      "  mov     %[result], %[endp]\n\t"
      "  jmp    .Lend%=\n\t"

      ".Lfound%=:\n\t"                       // we have to figure out which vector the first non-match was in, based on v1 and (v2&v1)
                                  // We could just search the bytes over again, but we don't have to.
                                  // we could also check v1 first and branch, instead of checking both and using a branchless check.
      "  xor       %k[result], 0xFFFF\n\t"
      "  tzcnt     %k[result], %k[result]\n\t"  // runs as bsf on older CPUs: same result for non-zero inputs, but different flags.  Faster than bsf on AMD
      "  add       %k[result], 16\n\t"          // result = byte count in case v1 is all-ones.  In that case, v2&v1 = v2

      "  vpmovmskb %k[tmp], %[v1]\n\t"
      "  xor       %k[tmp], 0xFFFF\n\t"
      "  bsf       %k[tmp], %k[tmp]\n\t"        // bsf sets ZF if its *input* was zero.  tzcnt's flag results are based on its output.  For AMD, it would be faster to use more insns (or a branchy strategy) and avoid bsf, but Intel has fast bsf.
      "  cmovnz    %k[result], %k[tmp]\n\t"     // if there was a non-match in v1, use it instead of tzcnt(v2)+16

      "  add       %[result], %[p]\n\t"         // If we needed to force 64bit, we could use %q[p].  But size_t should be 32bit in the x32 ABI, where pointers are 32bit.  This is one advantage to using size_t over uint64_t
      ".Lend%=:\n\t"
      : [result] "=&a" (result_pos),   // force compiler to pic eax/rax to save a couple bytes of code-size from the special cmp eax, imm32  and xor eax,imm32 encodings
        [p] "+&r" (bitmap),
        // throw-away outputs to let the compiler allocate registers.  All early-clobbered so they aren't put in the same reg as an input
        [tmp] "=&r" (tmpi),
        [pat] "=&x" (pattern),
        [v1] "=&x" (vtmp1), [v2] "=&x" (vtmp2)
      : [endp] "r" (bitmap+len)
        // doesn't compile: len isn't a compile-time constant
        // , "m" ( ({ struct { char x[len]; } *dummy = (typeof(dummy))bitmap ; *dummy; }) )  // tell the compiler *which* memory is an input.
      : "memory" // we read from data pointed to by bitmap, but bitmap[0..len] isn't an input, only the pointer.
    );

    return result_pos - bitmap_start;
}

这个 actually compiles and assembles到asm看起来像我期望的那样，但是我没有对其进行测试。请注意，它将所有寄存器分配留给编译器，因此更加内联。即使没有内联，它也不会强制使用必须保存/恢复的保留 call 的寄存器(例如，使用 "b"约束)。
未完成:用于处理最后一个sub-32B数据块的标量代码。
基于 Agner Fog's guides / tables的Intel SnB系列CPU的静态性能分析。另请参见 x86标签Wiki。 我假设我们不存在缓存吞吐量的瓶颈，因此该分析仅在L2缓存中的数据很热或者仅L1缓存足够快时才适用。
该循环可以每2个时钟以一次迭代(两个 vector )从前端发出，因为它是7个融合域对象。 (以4组为一组的前端问题)。 (如果两个cmp/jcc对在同一个块中进行解码，则实际上可能是8uops。Haswell和更高版本可以对每个解码组进行两次宏融合，但是以前的CPU只能对第一个宏进行融合。我们可以进行软件流水线化。循环，因此优先分支比p 所有这些融合域uops都包含ALU uop，因此瓶颈将在ALU执行端口上。 Haswell添加了第四个ALU单元，该单元可以处理简单的非 vector 运算(包括分支)，因此可以每2个时钟循环一次(每个时钟16B)运行此循环。您的i5-2550k(在注释中提到)是SnB CPU。
我使用 IACA来计算每个端口的uops，因为手工操作非常耗时。 IACA愚蠢，认为除了循环计数器外，还有某种迭代间的依赖关系，所以我不得不使用 -no_interiteration:

g++ -masm=intel -Wall -Wextra -O3 -mtune=haswell find-first-zero-bit.cpp -c -DIACA_MARKS
iaca -64 -arch IVB -no_interiteration find-first-zero-bit.o

Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - find-first-zero-bit.o
Binary Format - 64Bit
Architecture  - SNB
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 2.50 Cycles       Throughput Bottleneck: Port1, Port5

Port Binding In Cycles Per Iteration:
-------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |
-------------------------------------------------------------------------
| Cycles | 2.0    0.0  | 2.5  | 1.0    1.0  | 1.0    1.0  | 0.0  | 2.5  |
-------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis

| Num Of |              Ports pressure in cycles               |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |    |
---------------------------------------------------------------------
|   2^   |           | 1.0 | 1.0   1.0 |           |     |     | CP | vpcmpeqb xmm1, xmm0, xmmword ptr [rdx]
|   2^   |           | 0.6 |           | 1.0   1.0 |     | 0.4 | CP | vpcmpeqb xmm2, xmm0, xmmword ptr [rdx+0x10]
|   1    | 0.9       | 0.1 |           |           |     | 0.1 | CP | vpand xmm2, xmm2, xmm1
|   1    | 1.0       |     |           |           |     |     |    | vpmovmskb eax, xmm2
|   1    |           |     |           |           |     | 1.0 | CP | cmp eax, 0xffff
|   0F   |           |     |           |           |     |     |    | jnz 0x18
|   1    | 0.1       | 0.9 |           |           |     |     | CP | add rdx, 0x20
|   1    |           |     |           |           |     | 1.0 | CP | cmp rdx, rsi
|   0F   |           |     |           |           |     |     |    | jb 0xffffffffffffffe1

在SnB上: pcmpeqb可以在p1/p5上运行。融合的比较分支只能在p5上运行。非融合的 cmp可以在p015上运行。无论如何，如果分支之一没有宏熔丝，则循环可以每8/3 = 2.666个循环进行一次迭代。使用宏融合时，最佳情况是7/3 = 2.333个周期。 (IACA并没有尝试完全按照硬件动态做出决定的方式来模拟将uops分配到端口。但是，我们也不能期望从硬件中获得完美的调度，因此每2.5个周期2个 vector 对于两个宏都可能是合理的可能会使用port0的Uop有时会窃取port1或port5，从而降低吞吐量。)
如我之前所说，Haswell可以更好地处理此循环。 IACA认为，HSW可以每1.75c一次循环运行循环，但这显然是错误的，因为采用的循环分支结束了问题组。它将以重复的4,3 uop模式发出。但是执行单元比该循环的前端处理更多的吞吐量，因此它确实应该能够跟上Haswell/Broadwell/Skylake上的前端并每2个时钟运行一次迭代。
每个 vector 进一步展开更多 vpcmpeqb/ vpand仅为2 uops(或3而不使用AVX，我们将其加载到暂存器中，然后将其用作pcmpeqb的目的地。)因此，有了足够的展开，我们应该能够做2每个时钟 vector 负载。没有AVX，没有 PAND技巧是不可能的，因为 vector load/compare/movmsk/test-and-branch为4 oups。展开次数更大，需要更多的工作来解码找到匹配项的最终位置:一旦进入该区域，基于scalt cmp的清理循环可能是一个好主意。您可能会使用相同的标量循环来清除非32B大小。
如果使用SSE和 movdqu/ pcmpeqb xmm,xmm，我们可以使用索引寻址模式，而不会花费我们的成本，因为 movdqu负载始终是单个负载uop，而与寻址模式无关。 (与商店不同，它不需要对任何东西进行微熔合)。这使我们可以使用指向数组末尾的基本指针以及从零开始递增的索引来节省一小段循环开销。例如当索引为负数时， add %[idx], 32/ js循环。
但是，使用AVX，我们可以通过 using a single-register addressing mode节省2微克，因此 vpcmpeqb %[v1], %[pat], [ %[p] + 16 ]可以微熔断。这意味着我们需要在示例中使用的add/cmp/jcc循环结构。 AVX2也是如此。