StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Looks like I got to the party a year late, but here we go...</p> <p>Looking at the assembly generated by gcc 4.5.2 I observed that loads and stores are being done for every swap, which really isn't needed. It would be better to load the 6 values into registers, sort those, and store them back into memory. I ordered the loads at stores to be as close as possible to there the registers are first needed and last used. I also used Steinar H. Gunderson's SWAP macro. Update: I switched to Paolo Bonzini's SWAP macro which gcc converts into something similar to Gunderson's, but gcc is able to better order the instructions since they aren't given as explicit assembly.</p> <p>I used the same swap order as the reordered swap network given as the best performing, although there may be a better ordering. If I find some more time I'll generate and test a bunch of permutations.</p> <p>I changed the testing code to consider over 4000 arrays and show the average number of cycles needed to sort each one. On an i5-650 I'm getting ~34.1 cycles/sort (using -O3), compared to the original reordered sorting network getting ~65.3 cycles/sort (using -O1, beats -O2 and -O3).</p> <pre><code>#include <stdio.h> static inline void sort6_fast(int * d) { #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; } register int x0,x1,x2,x3,x4,x5; x1 = d[1]; x2 = d[2]; SWAP(x1, x2); x4 = d[4]; x5 = d[5]; SWAP(x4, x5); x0 = d[0]; SWAP(x0, x2); x3 = d[3]; SWAP(x3, x5); SWAP(x0, x1); SWAP(x3, x4); SWAP(x1, x4); SWAP(x0, x3); d[0] = x0; SWAP(x2, x5); d[5] = x5; SWAP(x1, x3); d[1] = x1; SWAP(x2, x4); d[4] = x4; SWAP(x2, x3); d[2] = x2; d[3] = x3; #undef SWAP #undef min #undef max } static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx"); return x; } void ran_fill(int n, int *a) { static int seed = 76521; while (n--) *a++ = (seed = seed *1812433253 + 12345); } #define NTESTS 4096 int main() { int i; int d[6*NTESTS]; ran_fill(6*NTESTS, d); unsigned long long cycles = rdtsc(); for (i = 0; i < 6*NTESTS ; i+=6) { sort6_fast(d+i); } cycles = rdtsc() - cycles; printf("Time is %.2lf\n", (double)cycles/(double)NTESTS); for (i = 0; i < 6*NTESTS ; i+=6) { if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5]) printf("d%d : %d %d %d %d %d %d\n", i, d[i+0], d[i+1], d[i+2], d[i+3], d[i+4], d[i+5]); } return 0; } </code></pre> <p>I changed <a href="http://pastebin.com/0aq18p7m">modified the test suite</a> to also report clocks per sort and run more tests (the cmp function was updated to handle integer overflow as well), here are the results on some different architectures. I attempted testing on an AMD cpu but rdtsc isn't reliable on the X6 1100T I have available.</p> <pre><code>Clarkdale (i5-650) ================== Direct call to qsort library function 635.14 575.65 581.61 577.76 521.12 Naive implementation (insertion sort) 538.30 135.36 134.89 240.62 101.23 Insertion Sort (Daniel Stutzbach) 424.48 159.85 160.76 152.01 151.92 Insertion Sort Unrolled 339.16 125.16 125.81 129.93 123.16 Rank Order 184.34 106.58 54.74 93.24 94.09 Rank Order with registers 127.45 104.65 53.79 98.05 97.95 Sorting Networks (Daniel Stutzbach) 269.77 130.56 128.15 126.70 127.30 Sorting Networks (Paul R) 551.64 103.20 64.57 73.68 73.51 Sorting Networks 12 with Fast Swap 321.74 61.61 63.90 67.92 67.76 Sorting Networks 12 reordered Swap 318.75 60.69 65.90 70.25 70.06 Reordered Sorting Network w/ fast swap 145.91 34.17 32.66 32.22 32.18 Kentsfield (Core 2 Quad) ======================== Direct call to qsort library function 870.01 736.39 723.39 725.48 721.85 Naive implementation (insertion sort) 503.67 174.09 182.13 284.41 191.10 Insertion Sort (Daniel Stutzbach) 345.32 152.84 157.67 151.23 150.96 Insertion Sort Unrolled 316.20 133.03 129.86 118.96 105.06 Rank Order 164.37 138.32 46.29 99.87 99.81 Rank Order with registers 115.44 116.02 44.04 116.04 116.03 Sorting Networks (Daniel Stutzbach) 230.35 114.31 119.15 110.51 111.45 Sorting Networks (Paul R) 498.94 77.24 63.98 62.17 65.67 Sorting Networks 12 with Fast Swap 315.98 59.41 58.36 60.29 55.15 Sorting Networks 12 reordered Swap 307.67 55.78 51.48 51.67 50.74 Reordered Sorting Network w/ fast swap 149.68 31.46 30.91 31.54 31.58 Sandy Bridge (i7-2600k) ======================= Direct call to qsort library function 559.97 451.88 464.84 491.35 458.11 Naive implementation (insertion sort) 341.15 160.26 160.45 154.40 106.54 Insertion Sort (Daniel Stutzbach) 284.17 136.74 132.69 123.85 121.77 Insertion Sort Unrolled 239.40 110.49 114.81 110.79 117.30 Rank Order 114.24 76.42 45.31 36.96 36.73 Rank Order with registers 105.09 32.31 48.54 32.51 33.29 Sorting Networks (Daniel Stutzbach) 210.56 115.68 116.69 107.05 124.08 Sorting Networks (Paul R) 364.03 66.02 61.64 45.70 44.19 Sorting Networks 12 with Fast Swap 246.97 41.36 59.03 41.66 38.98 Sorting Networks 12 reordered Swap 235.39 38.84 47.36 38.61 37.29 Reordered Sorting Network w/ fast swap 115.58 27.23 27.75 27.25 26.54 Nehalem (Xeon E5640) ==================== Direct call to qsort library function 911.62 890.88 681.80 876.03 872.89 Naive implementation (insertion sort) 457.69 236.87 127.68 388.74 175.28 Insertion Sort (Daniel Stutzbach) 317.89 279.74 147.78 247.97 245.09 Insertion Sort Unrolled 259.63 220.60 116.55 221.66 212.93 Rank Order 140.62 197.04 52.10 163.66 153.63 Rank Order with registers 84.83 96.78 50.93 109.96 54.73 Sorting Networks (Daniel Stutzbach) 214.59 220.94 118.68 120.60 116.09 Sorting Networks (Paul R) 459.17 163.76 56.40 61.83 58.69 Sorting Networks 12 with Fast Swap 284.58 95.01 50.66 53.19 55.47 Sorting Networks 12 reordered Swap 281.20 96.72 44.15 56.38 54.57 Reordered Sorting Network w/ fast swap 128.34 50.87 26.87 27.91 28.02 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload