Why is one of these sooooo much faster than the other?
<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>