title: > vs. >= in bubble sort causes significant performance difference
body: <p>I just stumbled upon something. At first I thought it might be a case of branch misprediction like it is <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">in this case</a>, but I cannot explain why branch misprediction should cause this behaviour.</p>
  <p>I implemented two versions of Bubble Sort in Java and did some performance testing:</p>
  <pre><code>import java.util.Random;
  
  public class BubbleSortAnnomaly {
  
      public static void main(String... args) {
          final int ARRAY_SIZE = Integer.parseInt(args[0]);
          final int LIMIT = Integer.parseInt(args[1]);
          final int RUNS = Integer.parseInt(args[2]);
  
          int[] a = new int[ARRAY_SIZE];
          int[] b = new int[ARRAY_SIZE];
          Random r = new Random();
          for (int run = 0; RUNS &gt; run; ++run) {
              for (int i = 0; i &lt; ARRAY_SIZE; i++) {
                  a[i] = r.nextInt(LIMIT);
                  b[i] = a[i];
              }
  
              System.out.print(&quot;Sorting with sortA: &quot;);
              long start = System.nanoTime();
              int swaps = bubbleSortA(a);
  
              System.out.println(  (System.nanoTime() - start) + &quot; ns. &quot;
                                 + &quot;It used &quot; + swaps + &quot; swaps.&quot;);
  
              System.out.print(&quot;Sorting with sortB: &quot;);
              start = System.nanoTime();
              swaps = bubbleSortB(b);
  
              System.out.println(  (System.nanoTime() - start) + &quot; ns. &quot;
                                 + &quot;It used &quot; + swaps + &quot; swaps.&quot;);
          }
      }
  
      public static int bubbleSortA(int[] a) {
          int counter = 0;
          for (int i = a.length - 1; i &gt;= 0; --i) {
              for (int j = 0; j &lt; i; ++j) {
                  if (a[j] &gt; a[j + 1]) {
                      swap(a, j, j + 1);
                      ++counter;
                  }
              }
          }
          return (counter);
      }
  
      public static int bubbleSortB(int[] a) {
          int counter = 0;
          for (int i = a.length - 1; i &gt;= 0; --i) {
              for (int j = 0; j &lt; i; ++j) {
                  if (a[j] &gt;= a[j + 1]) {
                      swap(a, j, j + 1);
                      ++counter;
                  }
              }
          }
          return (counter);
      }
  
      private static void swap(int[] a, int j, int i) {
          int h = a[i];
          a[i] = a[j];
          a[j] = h;
      }
  }
  </code></pre>
  <p>As we can see, the only difference between those two sorting methods is the <code>&gt;</code> vs. <code>&gt;=</code>. When running the program with <code>java BubbleSortAnnomaly 50000 10 10</code>, one would obviously expect that <code>sortB</code> is slower than <code>sortA</code> because it has to execute more <code>swap(...)</code>s. But I got the following (or similar) output on three different machines:</p>
  <pre><code>Sorting with sortA: 4.214 seconds. It used  564960211 swaps.
  Sorting with sortB: 2.278 seconds. It used 1249750569 swaps.
  Sorting with sortA: 4.199 seconds. It used  563355818 swaps.
  Sorting with sortB: 2.254 seconds. It used 1249750348 swaps.
  Sorting with sortA: 4.189 seconds. It used  560825110 swaps.
  Sorting with sortB: 2.264 seconds. It used 1249749572 swaps.
  Sorting with sortA: 4.17  seconds. It used  561924561 swaps.
  Sorting with sortB: 2.256 seconds. It used 1249749766 swaps.
  Sorting with sortA: 4.198 seconds. It used  562613693 swaps.
  Sorting with sortB: 2.266 seconds. It used 1249749880 swaps.
  Sorting with sortA: 4.19  seconds. It used  561658723 swaps.
  Sorting with sortB: 2.281 seconds. It used 1249751070 swaps.
  Sorting with sortA: 4.193 seconds. It used  564986461 swaps.
  Sorting with sortB: 2.266 seconds. It used 1249749681 swaps.
  Sorting with sortA: 4.203 seconds. It used  562526980 swaps.
  Sorting with sortB: 2.27  seconds. It used 1249749609 swaps.
  Sorting with sortA: 4.176 seconds. It used  561070571 swaps.
  Sorting with sortB: 2.241 seconds. It used 1249749831 swaps.
  Sorting with sortA: 4.191 seconds. It used  559883210 swaps.
  Sorting with sortB: 2.257 seconds. It used 1249749371 swaps.
  </code></pre>
  <p>When I set the parameter for <code>LIMIT</code> to, e.g., <code>50000</code> (<code>java BubbleSortAnnomaly 50000 50000 10</code>), I get the expected results:</p>
  <pre><code>Sorting with sortA: 3.983 seconds. It used  625941897 swaps.
  Sorting with sortB: 4.658 seconds. It used  789391382 swaps.
  </code></pre>
  <p>I ported the program to C++ to determine whether this problem is Java-specific. Here is the C++ code.</p>
  <pre><code>#include &lt;cstdlib&gt;
  #include &lt;iostream&gt;
  
  #include &lt;omp.h&gt;
  
  #ifndef ARRAY_SIZE
  #define ARRAY_SIZE 50000
  #endif
  
  #ifndef LIMIT
  #define LIMIT 10
  #endif
  
  #ifndef RUNS
  #define RUNS 10
  #endif
  
  void swap(int * a, int i, int j)
  {
      int h = a[i];
      a[i] = a[j];
      a[j] = h;
  }
  
  int bubbleSortA(int * a)
  {
      const int LAST = ARRAY_SIZE - 1;
      int counter = 0;
      for (int i = LAST; 0 &lt; i; --i)
      {
          for (int j = 0; j &lt; i; ++j)
          {
              int next = j + 1;
              if (a[j] &gt; a[next])
              {
                  swap(a, j, next);
                  ++counter;
              }
          }
      }
      return (counter);
  }
  
  int bubbleSortB(int * a)
  {
      const int LAST = ARRAY_SIZE - 1;
      int counter = 0;
      for (int i = LAST; 0 &lt; i; --i)
      {
          for (int j = 0; j &lt; i; ++j)
          {
              int next = j + 1;
              if (a[j] &gt;= a[next])
              {
                  swap(a, j, next);
                  ++counter;
              }
          }
      }
      return (counter);
  }
  
  int main()
  {
      int * a = (int *) malloc(ARRAY_SIZE * sizeof(int));
      int * b = (int *) malloc(ARRAY_SIZE * sizeof(int));
  
      for (int run = 0; RUNS &gt; run; ++run)
      {
          for (int idx = 0; ARRAY_SIZE &gt; idx; ++idx)
          {
              a[idx] = std::rand() % LIMIT;
              b[idx] = a[idx];
          }
  
          std::cout &lt;&lt; &quot;Sorting with sortA: &quot;;
          double start = omp_get_wtime();
          int swaps = bubbleSortA(a);
  
          std::cout &lt;&lt; (omp_get_wtime() - start) &lt;&lt; &quot; seconds. It used &quot; &lt;&lt; swaps
                    &lt;&lt; &quot; swaps.&quot; &lt;&lt; std::endl;
  
          std::cout &lt;&lt; &quot;Sorting with sortB: &quot;;
          start = omp_get_wtime();
          swaps = bubbleSortB(b);
  
          std::cout &lt;&lt; (omp_get_wtime() - start) &lt;&lt; &quot; seconds. It used &quot; &lt;&lt; swaps
                    &lt;&lt; &quot; swaps.&quot; &lt;&lt; std::endl;
      }
  
      free(a);
      free(b);
  
      return (0);
  }
  </code></pre>
  <p>This program shows the same behaviour. Can someone explain what exactly is going on here?</p>
  <p>Executing <code>sortB</code> first and then <code>sortA</code> does not change the results.</p>