title: Why is one of these sooooo much faster than the other?
body: <p>I'm writing C++ code to find the first byte in memory that is non 0xFF.  To exploit bitscanforward, I had written an inline assembly code that I like very much.  But for "readability" as well as future proofing (i.e. SIMD vectorization) I thought I would give g++ optimizer a chance.  g++ didn't vectorize, but it did get to nearly the same non-SIMD solution I did.  But for some reason, it's version runs much slower, 260000x slower (i.e. I have to loop my version 260,000x more to get to the same execution time).  I excepted some difference but not THAT much!  Can some point out why it might be?  I just want to know so as to make a mistake in future inline assembly codes.</p>
  
  <p>The C++ starting point is following, (in terms of counting accuracy, there is a bug in this code, but I've simplified it for this speed test):</p>
  
  <pre><code>uint64_t count3 (const void *data, uint64_t const &amp;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 &lt; nBytes );
  done:
        return (count&gt;nBytes ? nBytes : count);
  }
  </code></pre>
  
  <p>The assembly code g++ came up with is:</p>
  
  <pre><code>_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
  </code></pre>
  
  <p>My inline assembly is</p>
  
  <pre><code>_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
  </code></pre>
  
  <p>As far as I can see, it is substantially identical, except for the method by which it compare the data byte against 0xFF.  But I cannot believe this would cause a great difference in computation time. </p>
  
  <p>It's conceivable my test method is causing the error, but all I do is change the function name and iteration length in the following, simple for-loop shown below: (when N is 1&lt;&lt;20, and all bytes of 'a' except the last byte is 0xFF)</p>
  
  <p>test 1</p>
  
  <pre><code>   for (uint64_t i=0; i &lt; ((uint64_t)1&lt;&lt;15); i++) {
        n = count3(a,N);
     }
  </code></pre>
  
  <p>test 2</p>
  
  <pre><code>   for (uint64_t i=0; i &lt; ((uint64_t)1&lt;&lt;33); i++) {
        n = count2(a,N);
     }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>Here are my real inline assembly codes with SSE <code>count1()</code>, x64-64 <code>count()</code> and then plain-old-c++ versions <code>count0()</code> and <code>count3()</code>.  I fell down this rabbit hole hoping that I could get g++ to take my <code>count0()</code> and arrive, on it's own, to my <code>count1()</code> or even <code>count2()</code>.  But alas it did nothing, absolutely no optmization :(    I should add that my platform doesn't have AVX2, which is why I was hoping to get g++ to automatically vectorize, so that the code would automatically update when I update my platform.</p>
  
  <p>In terms of the explicit register use in the inline assembly, if I didn't make them explicitly, g++ would reuse the same registers for <code>nBytes</code> and <code>count</code>.  </p>
  
  <p>In terms of speedup, between XMM and QWORD, I found the real benefit is simply the "loop-unroll" effect, which I replicate in <code>count2()</code>. </p>
  
  <pre><code>uint32_t count0(const uint8_t *data, uint64_t const &amp;nBytes) {
  
    for (int i=0; i&lt;nBytes; i++)
      if (data[i] != 0xFF) return i;
  
    return nBytes;
  }
  uint32_t count1(const void *data, uint64_t const &amp;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 &amp; tzcnt negated r9
      " add     %[count], 16       \n" // else inc
      " cmp     %[count], %[nBytes] \n"
      " jl    .ctxff_next_block_%=  \n" // while count &lt; 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 &amp;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"  // &lt;--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 &amp;qword) {
    uint64_t tzc;
    asm("tzcnt %0, %1" : "=r" (tzc) : "r" (qword) );
    return tzc;
  };
  
  uint64_t count3 (const void *data, uint64_t const &amp;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 &lt; nBytes );
  done:
        return (count&gt;nBytes ? nBytes : count);
  }
  
  uint32_t N = 1&lt;&lt;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 &lt; ((uint64_t)1&lt;&lt;18); i++) {
        n += count2(a,N);
     }
  
   printf("\n\n %x %x %x\n",N, n, 0);   
    return n;
  }
  </code></pre>