title: Bubble sort slower with -O3 than -O2 with GCC
body: <p>I made a <a href="https://en.wikipedia.org/wiki/Bubble_sort" rel="noreferrer">bubble sort</a> implementation in C, and was testing its performance when I noticed that the <code>-O3</code> flag made it run even slower than no flags at all! Meanwhile <code>-O2</code> was making it run a lot faster as expected.</p>
  <p>Without optimisations:</p>
  <pre class="lang-none prettyprint-override"><code>time ./sort 30000
  
  ./sort 30000  1.82s user 0.00s system 99% cpu 1.816 total
  </code></pre>
  <p><code>-O2</code>:</p>
  <pre class="lang-none prettyprint-override"><code>time ./sort 30000
  
  ./sort 30000  1.00s user 0.00s system 99% cpu 1.005 total
  </code></pre>
  <p><code>-O3</code>:</p>
  <pre class="lang-none prettyprint-override"><code>time ./sort 30000
  
  ./sort 30000  2.01s user 0.00s system 99% cpu 2.007 total
  </code></pre>
  <p>The code:</p>
  <pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdbool.h&gt;
  #include &lt;time.h&gt;
  
  int n;
  
  void bubblesort(int *buf)
  {
      bool changed = true;
      for (int i = n; changed == true; i--) { /* will always move at least one element to its rightful place at the end, so can shorten the search by 1 each iteration */
          changed = false;
  
          for (int x = 0; x &lt; i-1; x++) {
              if (buf[x] &gt; buf[x+1]) {
                  /* swap */
                  int tmp = buf[x+1];
                  buf[x+1] = buf[x];
                  buf[x] = tmp;
  
                  changed = true;
              }
          }
      }
  }
  
  int main(int argc, char *argv[])
  {
      if (argc != 2) {
          fprintf(stderr, &quot;Usage: %s &lt;arraysize&gt;\n&quot;, argv[0]);
          return EXIT_FAILURE;
      }
  
      n = atoi(argv[1]);
      if (n &lt; 1) {
          fprintf(stderr, &quot;Invalid array size.\n&quot;);
          return EXIT_FAILURE;
      }
  
      int *buf = malloc(sizeof(int) * n);
  
      /* init buffer with random values */
      srand(time(NULL));
      for (int i = 0; i &lt; n; i++)
          buf[i] = rand() % n + 1;
  
      bubblesort(buf);
  
      return EXIT_SUCCESS;
  }
  </code></pre>
  <p>The assembly language generated for <code>-O2</code> (from <a href="https://godbolt.org/z/5G5WzTrPf" rel="noreferrer">godbolt.org</a>):</p>
  <pre class="lang-none prettyprint-override"><code>bubblesort:
          mov     r9d, DWORD PTR n[rip]
          xor     edx, edx
          xor     r10d, r10d
  .L2:
          lea     r8d, [r9-1]
          cmp     r8d, edx
          jle     .L13
  .L5:
          movsx   rax, edx
          lea     rax, [rdi+rax*4]
  .L4:
          mov     esi, DWORD PTR [rax]
          mov     ecx, DWORD PTR [rax+4]
          add     edx, 1
          cmp     esi, ecx
          jle     .L2
          mov     DWORD PTR [rax+4], esi
          mov     r10d, 1
          add     rax, 4
          mov     DWORD PTR [rax-4], ecx
          cmp     r8d, edx
          jg      .L4
          mov     r9d, r8d
          xor     edx, edx
          xor     r10d, r10d
          lea     r8d, [r9-1]
          cmp     r8d, edx
          jg      .L5
  .L13:
          test    r10b, r10b
          jne     .L14
  .L1:
          ret
  .L14:
          lea     eax, [r9-2]
          cmp     r9d, 2
          jle     .L1
          mov     r9d, r8d
          xor     edx, edx
          mov     r8d, eax
          xor     r10d, r10d
          jmp     .L5
  </code></pre>
  <p>And the same for <code>-O3</code>:</p>
  <pre class="lang-none prettyprint-override"><code>bubblesort:
          mov     r9d, DWORD PTR n[rip]
          xor     edx, edx
          xor     r10d, r10d
  .L2:
          lea     r8d, [r9-1]
          cmp     r8d, edx
          jle     .L13
  .L5:
          movsx   rax, edx
          lea     rcx, [rdi+rax*4]
  .L4:
          movq    xmm0, QWORD PTR [rcx]
          add     edx, 1
          pshufd  xmm2, xmm0, 0xe5
          movd    esi, xmm0
          movd    eax, xmm2
          pshufd  xmm1, xmm0, 225
          cmp     esi, eax
          jle     .L2
          movq    QWORD PTR [rcx], xmm1
          mov     r10d, 1
          add     rcx, 4
          cmp     r8d, edx
          jg      .L4
          mov     r9d, r8d
          xor     edx, edx
          xor     r10d, r10d
          lea     r8d, [r9-1]
          cmp     r8d, edx
          jg      .L5
  .L13:
          test    r10b, r10b
          jne     .L14
  .L1:
          ret
  .L14:
          lea     eax, [r9-2]
          cmp     r9d, 2
          jle     .L1
          mov     r9d, r8d
          xor     edx, edx
          mov     r8d, eax
          xor     r10d, r10d
          jmp     .L5
  </code></pre>
  <p>It seems like the only significant difference to me is the apparent attempt to use <a href="https://en.wikipedia.org/wiki/SIMD" rel="noreferrer">SIMD</a>, which <em>seems</em> like it should be a large improvement, but I also can't tell what on earth it's attempting with those <code>pshufd</code> instructions... is this just a failed attempt at SIMD? Or maybe the couple of extra instructions is just about edging out my instruction cache?</p>
  <p>Timings were done on an AMD <a href="https://en.wikipedia.org/wiki/Ryzen" rel="noreferrer">Ryzen</a> 5 3600.</p>