title: Fastest sort of fixed length 6 int array
body: <p>Answering to another Stack Overflow question (<a href="https://stackoverflow.com/questions/2775774/what-is-the-best-algorithm-for-this-array-comparison-problem/2777202#2777202">this one</a>) I stumbled upon an interesting sub-problem. What is the fastest way to sort an array of 6 integers?</p>
  
  <p>As the question is very low level:</p>
  
  <ul>
  <li>we can't assume libraries are available (and the call itself has its cost), only plain C</li>
  <li>to avoid emptying instruction pipeline (that has a <em>very</em> high cost) we should probably minimize branches, jumps, and every other kind of control flow breaking (like those hidden behind sequence points in <code>&amp;&amp;</code> or <code>||</code>).</li>
  <li>room is constrained and minimizing registers and memory use is an issue, ideally in place sort is probably best.</li>
  </ul>
  
  <p>Really this question is a kind of Golf where the goal is not to minimize source length but execution time. I call it 'Zening' code as used in the title of the book <a href="https://rads.stackoverflow.com/amzn/click/com/1883577039" rel="noreferrer" rel="nofollow noreferrer">Zen of Code optimization</a> by <a href="http://en.wikipedia.org/wiki/Michael_Abrash" rel="noreferrer">Michael Abrash</a> and its <a href="http://www.codinghorror.com/blog/2008/02/there-aint-no-such-thing-as-the-fastest-code.html" rel="noreferrer">sequels</a>.</p>
  
  <p>As for why it is interesting, there is several layers:</p>
  
  <ul>
  <li>the example is simple and easy to understand and measure, not much C skill involved</li>
  <li>it shows effects of choice of a good algorithm for the problem, but also effects of the compiler and underlying hardware.</li>
  </ul>
  
  <p>Here is my reference (naive, not optimized) implementation and my test set.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  static __inline__ int sort6(int * d){
  
      char j, i, imin;
      int tmp;
      for (j = 0 ; j &lt; 5 ; j++){
          imin = j;
          for (i = j + 1; i &lt; 6 ; i++){
              if (d[i] &lt; d[imin]){
                  imin = i;
              }
          }
          tmp = d[j];
          d[j] = d[imin];
          d[imin] = tmp;
      }
  }
  
  static __inline__ unsigned long long rdtsc(void)
  {
    unsigned long long int x;
       __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
       return x;
  }
  
  int main(int argc, char ** argv){
      int i;
      int d[6][5] = {
          {1, 2, 3, 4, 5, 6},
          {6, 5, 4, 3, 2, 1},
          {100, 2, 300, 4, 500, 6},
          {100, 2, 3, 4, 500, 6},
          {1, 200, 3, 4, 5, 600},
          {1, 1, 2, 1, 2, 1}
      };
  
      unsigned long long cycles = rdtsc();
      for (i = 0; i &lt; 6 ; i++){
          sort6(d[i]);
          /*
           * printf("d%d : %d %d %d %d %d %d\n", i,
           *  d[i][0], d[i][6], d[i][7],
           *  d[i][8], d[i][9], d[i][10]);
          */
      }
      cycles = rdtsc() - cycles;
      printf("Time is %d\n", (unsigned)cycles);
  }
  </code></pre>
  
  <h2><strong>Raw results</strong></h2>
  
  <p>As number of variants is becoming large, I gathered them all in a test suite that can be found <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>. The actual tests used are a bit less naive than those showed above, thanks to Kevin Stock. You can compile and execute it in your own environment. I'm quite interested by behavior on different target architecture/compilers. (OK guys, put it in answers, I will +1 every contributor of a new resultset). </p>
  
  <p>I gave the answer to Daniel Stutzbach (for golfing) one year ago as he was at the source of the fastest solution at that time (sorting networks).</p>
  
  <p><strong>Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O2</strong></p>
  
  <ul>
  <li>Direct call to qsort library function      : 689.38</li>
  <li>Naive implementation (insertion sort)      : 285.70</li>
  <li>Insertion Sort (Daniel Stutzbach)          : 142.12</li>
  <li>Insertion Sort Unrolled                    : 125.47</li>
  <li>Rank Order                                 : 102.26</li>
  <li>Rank Order with registers                  : 58.03</li>
  <li>Sorting Networks (Daniel Stutzbach)        : 111.68</li>
  <li>Sorting Networks (Paul R)                  : 66.36</li>
  <li>Sorting Networks 12 with Fast Swap         : 58.86</li>
  <li>Sorting Networks 12 reordered Swap         : 53.74</li>
  <li>Sorting Networks 12 reordered Simple Swap  : 31.54</li>
  <li>Reordered Sorting Network w/ fast swap     : 31.54</li>
  <li>Reordered Sorting Network w/ fast swap V2  : 33.63</li>
  <li>Inlined Bubble Sort (Paolo Bonzini)        : 48.85</li>
  <li>Unrolled Insertion Sort (Paolo Bonzini)    : 75.30</li>
  </ul>
  
  <p><strong>Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O1</strong></p>
  
  <ul>
  <li>Direct call to qsort library function      : 705.93</li>
  <li>Naive implementation (insertion sort)      : 135.60</li>
  <li>Insertion Sort (Daniel Stutzbach)          : 142.11</li>
  <li>Insertion Sort Unrolled                    : 126.75</li>
  <li>Rank Order                                 : 46.42</li>
  <li>Rank Order with registers                  : 43.58</li>
  <li>Sorting Networks (Daniel Stutzbach)        : 115.57</li>
  <li>Sorting Networks (Paul R)                  : 64.44</li>
  <li>Sorting Networks 12 with Fast Swap         : 61.98</li>
  <li>Sorting Networks 12 reordered Swap         : 54.67</li>
  <li>Sorting Networks 12 reordered Simple Swap  : 31.54</li>
  <li>Reordered Sorting Network w/ fast swap     : 31.24</li>
  <li>Reordered Sorting Network w/ fast swap V2  : 33.07</li>
  <li>Inlined Bubble Sort (Paolo Bonzini)        : 45.79</li>
  <li>Unrolled Insertion Sort (Paolo Bonzini)    : 80.15</li>
  </ul>
  
  <p>I included both -O1 and -O2 results because surprisingly for several programs O2 is <strong>less</strong> efficient than O1. I wonder what specific optimization has this effect ?</p>
  
  <h2><strong>Comments on proposed solutions</strong></h2>
  
  <p><strong>Insertion Sort (Daniel Stutzbach)</strong></p>
  
  <p>As expected minimizing branches is indeed a good idea.</p>
  
  <p><strong>Sorting Networks (Daniel Stutzbach)</strong></p>
  
  <p>Better than insertion sort. I wondered if the main effect was not get from avoiding the external loop. I gave it a try by unrolled insertion sort to check and indeed we get roughly the same figures (code is <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>).</p>
  
  <p><strong>Sorting Networks (Paul R)</strong></p>
  
  <p>The best so far. The actual code I used to test is <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>. Don't know yet why it is nearly two times as fast as the other sorting network implementation. Parameter passing ? Fast max ?</p>
  
  <p><strong>Sorting Networks 12 SWAP with Fast Swap</strong></p>
  
  <p>As suggested by Daniel Stutzbach, I combined his 12 swap sorting network with branchless fast swap (code is <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>). It is indeed faster, the best so far with a small margin (roughly 5%) as could be expected using 1 less swap. </p>
  
  <p>It is also interesting to notice that the branchless swap seems to be much (4 times) less efficient than the simple one using if on PPC architecture.</p>
  
  <p><strong>Calling Library qsort</strong></p>
  
  <p>To give another reference point I also tried as suggested to just call library qsort (code is <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>). As expected it is much slower : 10 to 30 times slower...  as it became obvious with the new test suite, the main problem seems to be the initial load of the library after the first call, and it compares not so poorly with other version. It is just between 3 and 20 times slower on my Linux. On some architecture used for tests by others it seems even to be faster (I'm really surprised by that one, as library qsort use a more complex API).</p>
  
  <p><strong>Rank order</strong></p>
  
  <p>Rex Kerr proposed another completely different method : for each item of the array compute directly its final position. This is efficient because computing rank order do not need branch. The drawback of this method is that it takes three times the amount of memory of the array (one copy of array and variables to store rank orders). The performance results are very surprising (and interesting). On my reference architecture with 32 bits OS and Intel Core2 Quad E8300, cycle count was slightly below 1000 (like sorting networks with branching swap). But when compiled and executed on my 64 bits box (Intel Core2 Duo) it performed much better : it became the fastest so far. I finally found out the true reason. My 32bits box use gcc 4.4.1 and my 64bits box gcc 4.4.3 and the last one seems much better at optimizing this particular code (there was very little difference for other proposals).</p>
  
  <p><em>update</em>:</p>
  
  <p>As published figures above shows this effect was still enhanced by later versions of gcc and Rank Order became consistently twice as fast as any other alternative.</p>
  
  <p><strong>Sorting Networks 12 with reordered Swap</strong></p>
  
  <p>The amazing efficiency of the Rex Kerr proposal with gcc 4.4.3 made me wonder : how could a program with 3 times as much memory usage be faster than branchless sorting networks? My hypothesis was that it had less dependencies of the kind read after write, allowing for better use of the superscalar instruction scheduler of the x86. That gave me an idea: reorder swaps to minimize read after write dependencies. More simply put: when you do <code>SWAP(1, 2); SWAP(0, 2);</code> you have to wait for the first swap to be finished before performing the second one because both access to a common memory cell. When you do <code>SWAP(1, 2); SWAP(4, 5);</code>the processor can execute both in parallel. I tried it and it works as expected, the sorting networks is running about 10% faster. </p>
  
  <p><strong>Sorting Networks 12 with Simple Swap</strong></p>
  
  <p>One year after the original post Steinar H. Gunderson suggested, that we should not try to outsmart the compiler and keep the swap code simple. It's indeed a good idea as the resulting code is about 40% faster! He also proposed a swap optimized by hand using x86 inline assembly code that can still spare some more cycles. The most surprising (it says volumes on programmer's psychology) is that one year ago none of used tried that version of swap. Code I used to test is <a href="http://pastebin.com/azzuk072" rel="noreferrer">here</a>. Others suggested other ways to write a C fast swap, but it yields the same performances as the simple one with a decent compiler.</p>
  
  <p>The "best" code is now as follow:</p>
  
  <pre><code>static inline void sort6_sorting_network_simple_swap(int * d){
  #define min(x, y) (x&lt;y?x:y)
  #define max(x, y) (x&lt;y?y:x) 
  #define SWAP(x,y) { const int a = min(d[x], d[y]); \
                      const int b = max(d[x], d[y]); \
                      d[x] = a; d[y] = b; }
      SWAP(1, 2);
      SWAP(4, 5);
      SWAP(0, 2);
      SWAP(3, 5);
      SWAP(0, 1);
      SWAP(3, 4);
      SWAP(1, 4);
      SWAP(0, 3);
      SWAP(2, 5);
      SWAP(1, 3);
      SWAP(2, 4);
      SWAP(2, 3);
  #undef SWAP
  #undef min
  #undef max
  }
  </code></pre>
  
  <p>If we believe our test set (and, yes it is quite poor, it's mere benefit is being short, simple and easy to understand what we are measuring), the average number of cycles of the resulting code for one sort is below 40 cycles (6 tests are executed). That put each swap at an average of 4 cycles. I call that amazingly fast. Any other improvements possible ?</p>