daily pastebin goal
68%
SHARE
TWEET

fastest sort of fixed length 6 int array

a guest Aug 25th, 2011 2,176 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.     }
RAW Paste Data
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
 
Top