API tools faq
paste
Advertisement
Guest User

fastest sort of fixed length 6 int array

a guest
Aug 25th, 2011
5,436
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 24.01 KB | None | 0 0
raw download clone embed print report
  1.     #include <stdio.h>
  2.     #include <stdlib.h>
  3.     #include <string.h>
  4.      
  5.     static inline int cmp(const void *p1, const void *p2)
  6.     {
  7.         return *(int*)p1 > *(int*)p2 ? 1 : (*(int*)p1 == *(int*)p2 ? 0 : -1);
  8.         //return *(int*)p1-*(int*)p2;
  9.     }
  10.      
  11.     static inline void sort6_libqsort(int * d)
  12.     {
  13.         qsort(d, 6, sizeof(int), cmp);
  14.     }
  15.      
  16.      
  17.      
  18.     static inline void sort6_insertion_sort_v1(int * d){
  19.      
  20.         int j, i, imin;
  21.         int tmp;
  22.         for (j = 0 ; j < 5 ; j++){
  23.             imin = j;
  24.             for (i = j + 1; i < 6 ; i++){
  25.                 if (d[i] < d[imin]){
  26.                     imin = i;
  27.                 }
  28.             }
  29.             tmp = d[j];
  30.             d[j] = d[imin];
  31.             d[imin] = tmp;
  32.         }
  33.     }
  34.      
  35.      
  36.     static inline void sort6_insertion_sort_v2(int *d){
  37.         int i, j;
  38.         for (i = 1; i < 6; i++) {
  39.             int tmp = d[i];
  40.             for (j = i; j >= 1 && tmp < d[j-1]; j--)
  41.                 d[j] = d[j-1];
  42.             d[j] = tmp;
  43.         }
  44.     }
  45.      
  46.     static inline void sort6_insertion_sort_unrolled(int *d){
  47.         int j1;
  48.         int tmp1 = d[1];
  49.         for (j1 = 1; j1 >= 1 && tmp1 < d[j1-1]; j1--)
  50.             d[j1] = d[j1-1];
  51.         d[j1] = tmp1;
  52.         int j2;
  53.         int tmp2 = d[2];
  54.         for (j2 = 2; j2 >= 1 && tmp2 < d[j2-1]; j2--)
  55.             d[j2] = d[j2-1];
  56.         d[j2] = tmp2;
  57.         int j3;
  58.         int tmp3 = d[3];
  59.         for (j3 = 3; j3 >= 1 && tmp3 < d[j3-1]; j3--)
  60.             d[j3] = d[j3-1];
  61.         d[j3] = tmp3;
  62.         int j4;
  63.         int tmp4 = d[4];
  64.         for (j4 = 4; j4 >= 1 && tmp4 < d[j4-1]; j4--)
  65.             d[j4] = d[j4-1];
  66.         d[j4] = tmp4;
  67.         int j5;
  68.         int tmp5 = d[5];
  69.         for (j5 = 5; j5 >= 1 && tmp5 < d[j5-1]; j5--)
  70.             d[j5] = d[j5-1];
  71.         d[j5] = tmp5;
  72.     }
  73.      
  74.      
  75.     static inline void sort6_sorting_network_v1(int * d){    #include <stdio.h>
  76.     #include <stdlib.h>
  77.     #include <string.h>
  78.      
  79.     static inline int cmp(const void *p1, const void *p2)
  80.     {
  81.         return *(int*)p1 > *(int*)p2 ? 1 : (*(int*)p1 == *(int*)p2 ? 0 : -1);
  82.         //return *(int*)p1-*(int*)p2;
  83.     }
  84.      
  85.     static inline void sort6_libqsort(int * d)
  86.     {
  87.         qsort(d, 6, sizeof(int), cmp);
  88.     }
  89.      
  90.      
  91.      
  92.     static inline void sort6_insertion_sort_v1(int * d){
  93.      
  94.         int j, i, imin;
  95.         int tmp;
  96.         for (j = 0 ; j < 5 ; j++){
  97.             imin = j;
  98.             for (i = j + 1; i < 6 ; i++){
  99.                 if (d[i] < d[imin]){
  100.                     imin = i;
  101.                 }
  102.             }
  103.             tmp = d[j];
  104.             d[j] = d[imin];
  105.             d[imin] = tmp;
  106.         }
  107.     }
  108.      
  109.      
  110.     static inline void sort6_insertion_sort_v2(int *d){
  111.         int i, j;
  112.         for (i = 1; i < 6; i++) {
  113.             int tmp = d[i];
  114.             for (j = i; j >= 1 && tmp < d[j-1]; j--)
  115.                 d[j] = d[j-1];
  116.             d[j] = tmp;
  117.         }
  118.     }
  119.      
  120.     static inline void sort6_insertion_sort_unrolled(int *d){
  121.         int j1;
  122.         int tmp1 = d[1];
  123.         for (j1 = 1; j1 >= 1 && tmp1 < d[j1-1]; j1--)
  124.             d[j1] = d[j1-1];
  125.         d[j1] = tmp1;
  126.         int j2;
  127.         int tmp2 = d[2];
  128.         for (j2 = 2; j2 >= 1 && tmp2 < d[j2-1]; j2--)
  129.             d[j2] = d[j2-1];
  130.         d[j2] = tmp2;
  131.         int j3;
  132.         int tmp3 = d[3];
  133.         for (j3 = 3; j3 >= 1 && tmp3 < d[j3-1]; j3--)
  134.             d[j3] = d[j3-1];
  135.         d[j3] = tmp3;
  136.         int j4;
  137.         int tmp4 = d[4];
  138.         for (j4 = 4; j4 >= 1 && tmp4 < d[j4-1]; j4--)
  139.             d[j4] = d[j4-1];
  140.         d[j4] = tmp4;
  141.         int j5;
  142.         int tmp5 = d[5];
  143.         for (j5 = 5; j5 >= 1 && tmp5 < d[j5-1]; j5--)
  144.             d[j5] = d[j5-1];
  145.         d[j5] = tmp5;
  146.     }
  147.      
  148.      
  149.     static inline void sort6_sorting_network_v1(int * d){
  150.     #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
  151.         SWAP(1, 2);
  152.         SWAP(0, 2);
  153.         SWAP(0, 1);
  154.         SWAP(4, 5);
  155.         SWAP(3, 5);
  156.         SWAP(3, 4);
  157.         SWAP(0, 3);
  158.         SWAP(1, 4);
  159.         SWAP(2, 5);
  160.         SWAP(2, 4);
  161.         SWAP(1, 3);
  162.         SWAP(2, 3);
  163.     #undef SWAP
  164.     }
  165.      
  166.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  167.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  168.      
  169.     static inline void sort2_sorting_network_v2(int *p0, int *p1)
  170.     {
  171.         const int temp = min(*p0, *p1);
  172.         *p1 = max(*p0, *p1);
  173.         *p0 = temp;
  174.     }
  175.      
  176.     static inline void sort3_sorting_network_v2(int *p0, int *p1, int *p2)
  177.     {
  178.         sort2_sorting_network_v2(p0, p1);
  179.         sort2_sorting_network_v2(p1, p2);
  180.         sort2_sorting_network_v2(p0, p1);
  181.     }
  182.      
  183.     static inline void sort4_sorting_network_v2(int *p0, int *p1, int *p2, int *p3)
  184.     {
  185.         sort2_sorting_network_v2(p0, p1);
  186.         sort2_sorting_network_v2(p2, p3);
  187.         sort2_sorting_network_v2(p0, p2);  
  188.         sort2_sorting_network_v2(p1, p3);  
  189.         sort2_sorting_network_v2(p1, p2);  
  190.     }
  191.      
  192.     static inline void sort6_sorting_network_v2(int *d)
  193.     {
  194.         sort3_sorting_network_v2(d+0, d+1, d+2);
  195.         sort3_sorting_network_v2(d+3, d+4, d+5);
  196.         sort2_sorting_network_v2(d+0, d+3);  
  197.         sort2_sorting_network_v2(d+2, d+5);  
  198.         sort4_sorting_network_v2(d+1, d+2, d+3, d+4);  
  199.     }
  200.     #undef min
  201.     #undef max
  202.      
  203.      
  204.     static inline void sort6_sorting_network_v3(int * d){
  205.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  206.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  207.     #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  208.         SWAP(1, 2);
  209.         SWAP(0, 2);
  210.         SWAP(0, 1);
  211.         SWAP(4, 5);
  212.         SWAP(3, 5);
  213.         SWAP(3, 4);
  214.         SWAP(0, 3);
  215.         SWAP(1, 4);
  216.         SWAP(2, 5);
  217.         SWAP(2, 4);
  218.         SWAP(1, 3);
  219.         SWAP(2, 3);
  220.     #undef SWAP
  221.     #undef min
  222.     #undef max
  223.     }
  224.      
  225.     static inline void sort6_sorting_network_v4(int * d){
  226.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  227.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  228.     #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  229.         SWAP(1, 2);
  230.         SWAP(4, 5);
  231.         SWAP(0, 2);
  232.         SWAP(3, 5);
  233.         SWAP(0, 1);
  234.         SWAP(3, 4);
  235.         SWAP(1, 4);
  236.         SWAP(0, 3);
  237.         SWAP(2, 5);
  238.         SWAP(1, 3);
  239.         SWAP(2, 4);
  240.         SWAP(2, 3);
  241.     #undef SWAP
  242.     #undef min
  243.     #undef max
  244.     }
  245.  
  246.     static inline void sort6_sorting_net_simple_swap(int * d){
  247.     #define min(x, y) (y > x ? x : y)
  248.     #define max(x, y) (y > x ? y : x)
  249.     #define SWAP(x,y) { int a = min(d[x], d[y]); int b = max(d[x], d[y]); d[x] = a; d[y] = b;}
  250.         SWAP(1, 2);
  251.         SWAP(4, 5);
  252.         SWAP(0, 2);
  253.         SWAP(3, 5);
  254.         SWAP(0, 1);
  255.         SWAP(3, 4);
  256.         SWAP(1, 4);
  257.         SWAP(0, 3);
  258.         SWAP(2, 5);
  259.         SWAP(1, 3);
  260.         SWAP(2, 4);
  261.         SWAP(2, 3);
  262.     #undef SWAP
  263.     #undef min
  264.     #undef max
  265.     }
  266.      
  267.     static inline void sort6_rank_order(int *d) {
  268.         int e[6];
  269.         memcpy(e,d,6*sizeof(int));
  270.         int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  271.         int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  272.         int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  273.         int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  274.         int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  275.         int o5 = 15-(o0+o1+o2+o3+o4);
  276.         d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
  277.     }
  278.      
  279.     static inline void sort6_rank_order_reg(int *d) {
  280.         register int x0,x1,x2,x3,x4,x5;
  281.         x0 = d[0];
  282.         x1 = d[1];
  283.         x2 = d[2];
  284.         x3 = d[3];
  285.         x4 = d[4];
  286.         x5 = d[5];
  287.         int o0 = (x0>x1)+(x0>x2)+(x0>x3)+(x0>x4)+(x0>x5);
  288.         int o1 = (x1>=x0)+(x1>x2)+(x1>x3)+(x1>x4)+(x1>x5);
  289.         int o2 = (x2>=x0)+(x2>=x1)+(x2>x3)+(x2>x4)+(x2>x5);
  290.         int o3 = (x3>=x0)+(x3>=x1)+(x3>=x2)+(x3>x4)+(x3>x5);
  291.         int o4 = (x4>=x0)+(x4>=x1)+(x4>=x2)+(x4>=x3)+(x4>x5);
  292.         int o5 = 15-(o0+o1+o2+o3+o4);
  293.         d[o0]=x0; d[o1]=x1; d[o2]=x2; d[o3]=x3; d[o4]=x4; d[o5]=x5;
  294.     }
  295.      
  296.     static inline void sort6_inlined_bubble(int * d){
  297.     #define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
  298.         SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
  299.         SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
  300.         SWAP(0,1); SWAP(1,2); SWAP(2,3);
  301.         SWAP(0,1); SWAP(1,2);
  302.         SWAP(0,1);
  303.     #undef SWAP
  304.     }
  305.  
  306.  
  307.     static inline void sort6_insertion_sort_unrolled_v2(int * d){
  308.         //#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
  309.         //Faster on x86, probably slower on ARM or similar:
  310.         #define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
  311.             int t;
  312.             t = d[1]; ITER(0);
  313.             t = d[2]; ITER(1); ITER(0);
  314.             t = d[3]; ITER(2); ITER(1); ITER(0);
  315.             t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
  316.             t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);
  317.         #undef ITER
  318.     }
  319.  
  320.     // to be debugged
  321.     static inline void sort6_shellsort(int * d) {
  322.         char j, i, inc;
  323.         int tmp;
  324.         for (inc = 4; inc > 0; inc -= 3) {
  325.             for (i = inc; i < 5; i++) {
  326.                 tmp = d[i];
  327.                 j = i;
  328.                 while (j >= inc && d[j - inc] > tmp) {
  329.                     d[j] = d[j - inc];
  330.                     j -= inc;
  331.                 }
  332.                 d[j] = tmp;
  333.             }
  334.         }
  335.     }
  336.  
  337.     static inline void sort6_fast_network(int * d) {
  338.     //#define SWAP(x,y) asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (x), "=r" (y), "=r" (tmp) : "0" (x), "1" (y) : "cc");
  339.     //    register int x0,x1,x2,x3,x4,x5,tmp;
  340.     #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
  341.         register int x0,x1,x2,x3,x4,x5;
  342.         x1 = d[1];
  343.         x2 = d[2];
  344.         SWAP(x1, x2);
  345.         x4 = d[4];
  346.         x5 = d[5];
  347.         SWAP(x4, x5);
  348.         x0 = d[0];
  349.         SWAP(x0, x2);
  350.         x3 = d[3];
  351.         SWAP(x3, x5);
  352.         SWAP(x0, x1);
  353.         SWAP(x3, x4);
  354.         SWAP(x1, x4);
  355.         SWAP(x0, x3);
  356.         d[0] = x0;
  357.         SWAP(x2, x5);
  358.         d[5] = x5;
  359.         SWAP(x1, x3);
  360.         d[1] = x1;
  361.         SWAP(x2, x4);
  362.         d[4] = x4;
  363.         SWAP(x2, x3);
  364.         d[2] = x2;
  365.         d[3] = x3;
  366.      
  367.     #undef SWAP
  368.     #undef min
  369.     #undef max
  370.     }
  371.      
  372.  
  373.     static inline void sort6_fast_network_simplified(int * d) {
  374.     //#define SWAP(x,y) asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (x), "=r" (y), "=r" (tmp) : "0" (x), "1" (y) : "cc");
  375.     #define SWAP(x,y) { int dx = d[x]; int dy = d[y]; int tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
  376.         SWAP(1, 2);
  377.         SWAP(4, 5);
  378.         SWAP(0, 2);
  379.         SWAP(3, 5);
  380.         SWAP(0, 1);
  381.         SWAP(3, 4);
  382.         SWAP(1, 4);
  383.         SWAP(0, 3);
  384.         SWAP(2, 5);
  385.         SWAP(1, 3);
  386.         SWAP(2, 4);
  387.         SWAP(2, 3);
  388.     #undef SWAP
  389.     #undef min
  390.     #undef max
  391.     }
  392.  
  393.     static inline unsigned long long rdtsc(void)
  394.     {
  395.         unsigned long long int x;
  396.         asm volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
  397.         return x;
  398.     }
  399.      
  400.     void ran_fill(int n, int *a) {
  401.         static int seed = 76521;
  402.         while (n--) *a++ = (seed = seed *1812433253 + 12345);
  403.     }
  404.      
  405.      
  406.     #define NTESTS 16384
  407.     int main(){
  408.      
  409.     #define TEST(variant, description) {\
  410.         int i;\
  411.         int d[6*NTESTS];\
  412.         sort6_##variant(d);\
  413.         ran_fill(6*NTESTS, d);\
  414.         unsigned long long cycles = rdtsc();\
  415.         for (i = 0; i < 6*NTESTS ; i+=6){\
  416.             sort6_##variant(d+i);\
  417.         }\
  418.         cycles = rdtsc() - cycles;\
  419.         printf(description " : %.2lf\n", (double)cycles/(double)NTESTS);\
  420.         {\
  421.         int passed = 1;\
  422.         for (i = 0; i < 6*NTESTS ; i+=6) { \
  423.             if (d[i+0] > d[i+1] \
  424.                 || d[i+1] > d[i+2] \
  425.                 || d[i+2] > d[i+3] \
  426.                 || d[i+3] > d[i+4] \
  427.                 || d[i+4] > d[i+5]) {\
  428.                 printf("d%d : %d %d %d %d %d %d\n", i, \
  429.                         d[i+0], d[i+1], d[i+2], \
  430.                         d[i+3], d[i+4], d[i+5]); \
  431.                 passed = 0;\
  432.             }\
  433.         } \
  434.         if (!passed) {\
  435.                 printf(" FAILED\n");\
  436.         }\
  437.         }\
  438.     }
  439.      
  440.     TEST(libqsort,                "Direct call to qsort library function     ");
  441.     TEST(insertion_sort_v1,       "Naive implementation (insertion sort)     ");
  442.     TEST(insertion_sort_v2,       "Insertion Sort (Daniel Stutzbach)         ");
  443.     TEST(insertion_sort_unrolled, "Insertion Sort Unrolled                   ");
  444.     TEST(rank_order,              "Rank Order                                ");
  445.     TEST(rank_order_reg,          "Rank Order with registers                 ");
  446.     TEST(sorting_network_v1,      "Sorting Networks (Daniel Stutzbach)       ");
  447.     TEST(sorting_network_v2,      "Sorting Networks (Paul R)                 ");
  448.     TEST(sorting_network_v3,      "Sorting Networks 12 with Fast Swap        ");
  449.     TEST(sorting_network_v4,      "Sorting Networks 12 reordered Swap        ");
  450.     TEST(sorting_net_simple_swap, "Sorting Networks 12 reordered Simple Swap (");
  451.     TEST(fast_network,            "Reordered Sorting Network w/ fast swap    ");
  452.     TEST(fast_network_simplified, "Reordered Sorting Network w/ fast swap V2 ");
  453.     TEST(inlined_bubble,          "Inlined Bubble Sort (Paolo Bonzini)       ");
  454.     TEST(insertion_sort_unrolled_v2, "Unrolled Insertion Sort (Paolo Bonzini)   ");
  455.      
  456.     return 0;
  457.      
  458.     }
  459.  
  460.     #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
  461.         SWAP(1, 2);
  462.         SWAP(0, 2);
  463.         SWAP(0, 1);
  464.         SWAP(4, 5);
  465.         SWAP(3, 5);
  466.         SWAP(3, 4);
  467.         SWAP(0, 3);
  468.         SWAP(1, 4);
  469.         SWAP(2, 5);
  470.         SWAP(2, 4);
  471.         SWAP(1, 3);
  472.         SWAP(2, 3);
  473.     #undef SWAP
  474.     }
  475.      
  476.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  477.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  478.      
  479.     static inline void sort2_sorting_network_v2(int *p0, int *p1)
  480.     {
  481.         const int temp = min(*p0, *p1);
  482.         *p1 = max(*p0, *p1);
  483.         *p0 = temp;
  484.     }
  485.      
  486.     static inline void sort3_sorting_network_v2(int *p0, int *p1, int *p2)
  487.     {
  488.         sort2_sorting_network_v2(p0, p1);
  489.         sort2_sorting_network_v2(p1, p2);
  490.         sort2_sorting_network_v2(p0, p1);
  491.     }
  492.      
  493.     static inline void sort4_sorting_network_v2(int *p0, int *p1, int *p2, int *p3)
  494.     {
  495.         sort2_sorting_network_v2(p0, p1);
  496.         sort2_sorting_network_v2(p2, p3);
  497.         sort2_sorting_network_v2(p0, p2);  
  498.         sort2_sorting_network_v2(p1, p3);  
  499.         sort2_sorting_network_v2(p1, p2);  
  500.     }
  501.      
  502.     static inline void sort6_sorting_network_v2(int *d)
  503.     {
  504.         sort3_sorting_network_v2(d+0, d+1, d+2);
  505.         sort3_sorting_network_v2(d+3, d+4, d+5);
  506.         sort2_sorting_network_v2(d+0, d+3);  
  507.         sort2_sorting_network_v2(d+2, d+5);  
  508.         sort4_sorting_network_v2(d+1, d+2, d+3, d+4);  
  509.     }
  510.     #undef min
  511.     #undef max
  512.      
  513.      
  514.     static inline void sort6_sorting_network_v3(int * d){
  515.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  516.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  517.     #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  518.         SWAP(1, 2);
  519.         SWAP(0, 2);
  520.         SWAP(0, 1);
  521.         SWAP(4, 5);
  522.         SWAP(3, 5);
  523.         SWAP(3, 4);
  524.         SWAP(0, 3);
  525.         SWAP(1, 4);
  526.         SWAP(2, 5);
  527.         SWAP(2, 4);
  528.         SWAP(1, 3);
  529.         SWAP(2, 3);
  530.     #undef SWAP
  531.     #undef min
  532.     #undef max
  533.     }
  534.      
  535.     static inline void sort6_sorting_network_v4(int * d){
  536.     #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  537.     #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  538.     #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  539.         SWAP(1, 2);
  540.         SWAP(4, 5);
  541.         SWAP(0, 2);
  542.         SWAP(3, 5);
  543.         SWAP(0, 1);
  544.         SWAP(3, 4);
  545.         SWAP(1, 4);
  546.         SWAP(0, 3);
  547.         SWAP(2, 5);
  548.         SWAP(1, 3);
  549.         SWAP(2, 4);
  550.         SWAP(2, 3);
  551.     #undef SWAP
  552.     #undef min
  553.     #undef max
  554.     }
  555.  
  556.     static inline void sort6_sorting_net_simple_swap(int * d){
  557.     #define min(x, y) (y > x ? x : y)
  558.     #define max(x, y) (y > x ? y : x)
  559.     #define SWAP(x,y) { int a = min(d[x], d[y]); int b = max(d[x], d[y]); d[x] = a; d[y] = b;}
  560.         SWAP(1, 2);
  561.         SWAP(4, 5);
  562.         SWAP(0, 2);
  563.         SWAP(3, 5);
  564.         SWAP(0, 1);
  565.         SWAP(3, 4);
  566.         SWAP(1, 4);
  567.         SWAP(0, 3);
  568.         SWAP(2, 5);
  569.         SWAP(1, 3);
  570.         SWAP(2, 4);
  571.         SWAP(2, 3);
  572.     #undef SWAP
  573.     #undef min
  574.     #undef max
  575.     }
  576.      
  577.     static inline void sort6_rank_order(int *d) {
  578.         int e[6];
  579.         memcpy(e,d,6*sizeof(int));
  580.         int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  581.         int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  582.         int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  583.         int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  584.         int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  585.         int o5 = 15-(o0+o1+o2+o3+o4);
  586.         d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
  587.     }
  588.      
  589.     static inline void sort6_rank_order_reg(int *d) {
  590.         register int x0,x1,x2,x3,x4,x5;
  591.         x0 = d[0];
  592.         x1 = d[1];
  593.         x2 = d[2];
  594.         x3 = d[3];
  595.         x4 = d[4];
  596.         x5 = d[5];
  597.         int o0 = (x0>x1)+(x0>x2)+(x0>x3)+(x0>x4)+(x0>x5);
  598.         int o1 = (x1>=x0)+(x1>x2)+(x1>x3)+(x1>x4)+(x1>x5);
  599.         int o2 = (x2>=x0)+(x2>=x1)+(x2>x3)+(x2>x4)+(x2>x5);
  600.         int o3 = (x3>=x0)+(x3>=x1)+(x3>=x2)+(x3>x4)+(x3>x5);
  601.         int o4 = (x4>=x0)+(x4>=x1)+(x4>=x2)+(x4>=x3)+(x4>x5);
  602.         int o5 = 15-(o0+o1+o2+o3+o4);
  603.         d[o0]=x0; d[o1]=x1; d[o2]=x2; d[o3]=x3; d[o4]=x4; d[o5]=x5;
  604.     }
  605.      
  606.     static inline void sort6_inlined_bubble(int * d){
  607.     #define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
  608.         SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
  609.         SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
  610.         SWAP(0,1); SWAP(1,2); SWAP(2,3);
  611.         SWAP(0,1); SWAP(1,2);
  612.         SWAP(0,1);
  613.     #undef SWAP
  614.     }
  615.  
  616.  
  617.     static inline void sort6_insertion_sort_unrolled_v2(int * d){
  618.         //#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
  619.         //Faster on x86, probably slower on ARM or similar:
  620.         #define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
  621.             int t;
  622.             t = d[1]; ITER(0);
  623.             t = d[2]; ITER(1); ITER(0);
  624.             t = d[3]; ITER(2); ITER(1); ITER(0);
  625.             t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
  626.             t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);
  627.         #undef ITER
  628.     }
  629.  
  630.     // to be debugged
  631.     static inline void sort6_shellsort(int * d) {
  632.         char j, i, inc;
  633.         int tmp;
  634.         for (inc = 4; inc > 0; inc -= 3) {
  635.             for (i = inc; i < 5; i++) {
  636.                 tmp = d[i];
  637.                 j = i;
  638.                 while (j >= inc && d[j - inc] > tmp) {
  639.                     d[j] = d[j - inc];
  640.                     j -= inc;
  641.                 }
  642.                 d[j] = tmp;
  643.             }
  644.         }
  645.     }
  646.  
  647.     static inline void sort6_fast_network(int * d) {
  648.     //#define SWAP(x,y) asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (x), "=r" (y), "=r" (tmp) : "0" (x), "1" (y) : "cc");
  649.     //    register int x0,x1,x2,x3,x4,x5,tmp;
  650.     #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
  651.         register int x0,x1,x2,x3,x4,x5;
  652.         x1 = d[1];
  653.         x2 = d[2];
  654.         SWAP(x1, x2);
  655.         x4 = d[4];
  656.         x5 = d[5];
  657.         SWAP(x4, x5);
  658.         x0 = d[0];
  659.         SWAP(x0, x2);
  660.         x3 = d[3];
  661.         SWAP(x3, x5);
  662.         SWAP(x0, x1);
  663.         SWAP(x3, x4);
  664.         SWAP(x1, x4);
  665.         SWAP(x0, x3);
  666.         d[0] = x0;
  667.         SWAP(x2, x5);
  668.         d[5] = x5;
  669.         SWAP(x1, x3);
  670.         d[1] = x1;
  671.         SWAP(x2, x4);
  672.         d[4] = x4;
  673.         SWAP(x2, x3);
  674.         d[2] = x2;
  675.         d[3] = x3;
  676.      
  677.     #undef SWAP
  678.     #undef min
  679.     #undef max
  680.     }
  681.      
  682.  
  683.     static inline void sort6_fast_network_simplified(int * d) {
  684.     //#define SWAP(x,y) asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (x), "=r" (y), "=r" (tmp) : "0" (x), "1" (y) : "cc");
  685.     #define SWAP(x,y) { int dx = d[x]; int dy = d[y]; int tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
  686.         SWAP(1, 2);
  687.         SWAP(4, 5);
  688.         SWAP(0, 2);
  689.         SWAP(3, 5);
  690.         SWAP(0, 1);
  691.         SWAP(3, 4);
  692.         SWAP(1, 4);
  693.         SWAP(0, 3);
  694.         SWAP(2, 5);
  695.         SWAP(1, 3);
  696.         SWAP(2, 4);
  697.         SWAP(2, 3);
  698.     #undef SWAP
  699.     #undef min
  700.     #undef max
  701.     }
  702.  
  703.     static inline unsigned long long rdtsc(void)
  704.     {
  705.         unsigned long long int x;
  706.         asm volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
  707.         return x;
  708.     }
  709.      
  710.     void ran_fill(int n, int *a) {
  711.         static int seed = 76521;
  712.         while (n--) *a++ = (seed = seed *1812433253 + 12345);
  713.     }
  714.      
  715.      
  716.     #define NTESTS 16384
  717.     int main(){
  718.      
  719.     #define TEST(variant, description) {\
  720.         int i;\
  721.         int d[6*NTESTS];\
  722.         sort6_##variant(d);\
  723.         ran_fill(6*NTESTS, d);\
  724.         unsigned long long cycles = rdtsc();\
  725.         for (i = 0; i < 6*NTESTS ; i+=6){\
  726.             sort6_##variant(d+i);\
  727.         }\
  728.         cycles = rdtsc() - cycles;\
  729.         printf(description " : %.2lf\n", (double)cycles/(double)NTESTS);\
  730.         {\
  731.         int passed = 1;\
  732.         for (i = 0; i < 6*NTESTS ; i+=6) { \
  733.             if (d[i+0] > d[i+1] \
  734.                 || d[i+1] > d[i+2] \
  735.                 || d[i+2] > d[i+3] \
  736.                 || d[i+3] > d[i+4] \
  737.                 || d[i+4] > d[i+5]) {\
  738.                 printf("d%d : %d %d %d %d %d %d\n", i, \
  739.                         d[i+0], d[i+1], d[i+2], \
  740.                         d[i+3], d[i+4], d[i+5]); \
  741.                 passed = 0;\
  742.             }\
  743.         } \
  744.         if (!passed) {\
  745.                 printf(" FAILED\n");\
  746.         }\
  747.         }\
  748.     }
  749.      
  750.     TEST(libqsort,                "Direct call to qsort library function     ");
  751.     TEST(insertion_sort_v1,       "Naive implementation (insertion sort)     ");
  752.     TEST(insertion_sort_v2,       "Insertion Sort (Daniel Stutzbach)         ");
  753.     TEST(insertion_sort_unrolled, "Insertion Sort Unrolled                   ");
  754.     TEST(rank_order,              "Rank Order                                ");
  755.     TEST(rank_order_reg,          "Rank Order with registers                 ");
  756.     TEST(sorting_network_v1,      "Sorting Networks (Daniel Stutzbach)       ");
  757.     TEST(sorting_network_v2,      "Sorting Networks (Paul R)                 ");
  758.     TEST(sorting_network_v3,      "Sorting Networks 12 with Fast Swap        ");
  759.     TEST(sorting_network_v4,      "Sorting Networks 12 reordered Swap        ");
  760.     TEST(sorting_net_simple_swap, "Sorting Networks 12 reordered Simple Swap (");
  761.     TEST(fast_network,            "Reordered Sorting Network w/ fast swap    ");
  762.     TEST(fast_network_simplified, "Reordered Sorting Network w/ fast swap V2 ");
  763.     TEST(inlined_bubble,          "Inlined Bubble Sort (Paolo Bonzini)       ");
  764.     TEST(insertion_sort_unrolled_v2, "Unrolled Insertion Sort (Paolo Bonzini)   ");
  765.      
  766.     return 0;
  767.      
  768.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!