daily pastebin goal
82%
SHARE
TWEET

sort6_suite

a guest Aug 24th, 2011 381 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){
  76. #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
  77.     SWAP(1, 2);
  78.     SWAP(0, 2);
  79.     SWAP(0, 1);
  80.     SWAP(4, 5);
  81.     SWAP(3, 5);
  82.     SWAP(3, 4);
  83.     SWAP(0, 3);
  84.     SWAP(1, 4);
  85.     SWAP(2, 5);
  86.     SWAP(2, 4);
  87.     SWAP(1, 3);
  88.     SWAP(2, 3);
  89. #undef SWAP
  90. }
  91.  
  92. #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  93. #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  94.  
  95. static inline void sort2_sorting_network_v2(int *p0, int *p1)
  96. {
  97.     const int temp = min(*p0, *p1);
  98.     *p1 = max(*p0, *p1);
  99.     *p0 = temp;
  100. }
  101.  
  102. static inline void sort3_sorting_network_v2(int *p0, int *p1, int *p2)
  103. {
  104.     sort2_sorting_network_v2(p0, p1);
  105.     sort2_sorting_network_v2(p1, p2);
  106.     sort2_sorting_network_v2(p0, p1);
  107. }
  108.  
  109. static inline void sort4_sorting_network_v2(int *p0, int *p1, int *p2, int *p3)
  110. {
  111.     sort2_sorting_network_v2(p0, p1);
  112.     sort2_sorting_network_v2(p2, p3);
  113.     sort2_sorting_network_v2(p0, p2);  
  114.     sort2_sorting_network_v2(p1, p3);  
  115.     sort2_sorting_network_v2(p1, p2);  
  116. }
  117.  
  118. static inline void sort6_sorting_network_v2(int *d)
  119. {
  120.     sort3_sorting_network_v2(d+0, d+1, d+2);
  121.     sort3_sorting_network_v2(d+3, d+4, d+5);
  122.     sort2_sorting_network_v2(d+0, d+3);  
  123.     sort2_sorting_network_v2(d+2, d+5);  
  124.     sort4_sorting_network_v2(d+1, d+2, d+3, d+4);  
  125. }
  126. #undef min
  127. #undef max
  128.  
  129.  
  130. static inline void sort6_sorting_network_v3(int * d){
  131. #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  132. #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  133. #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  134.     SWAP(1, 2);
  135.     SWAP(0, 2);
  136.     SWAP(0, 1);
  137.     SWAP(4, 5);
  138.     SWAP(3, 5);
  139.     SWAP(3, 4);
  140.     SWAP(0, 3);
  141.     SWAP(1, 4);
  142.     SWAP(2, 5);
  143.     SWAP(2, 4);
  144.     SWAP(1, 3);
  145.     SWAP(2, 3);
  146. #undef SWAP
  147. #undef min
  148. #undef max
  149. }
  150.  
  151. static inline void sort6_sorting_network_v4(int * d){
  152. #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
  153. #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
  154. #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
  155.     SWAP(1, 2);
  156.     SWAP(4, 5);
  157.     SWAP(0, 2);
  158.     SWAP(3, 5);
  159.     SWAP(0, 1);
  160.     SWAP(3, 4);
  161.     SWAP(1, 4);
  162.     SWAP(0, 3);
  163.     SWAP(2, 5);
  164.     SWAP(1, 3);
  165.     SWAP(2, 4);
  166.     SWAP(2, 3);
  167. #undef SWAP
  168. #undef min
  169. #undef max
  170. }
  171.  
  172. static inline void sort6_rank_order(int *d) {
  173.     int e[6];
  174.     memcpy(e,d,6*sizeof(int));
  175.     int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  176.     int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  177.     int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  178.     int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  179.     int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  180.     int o5 = 15-(o0+o1+o2+o3+o4);
  181.     d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
  182. }
  183.  
  184. static inline void sort6_rank_order_reg(int *d) {
  185.     register int x0,x1,x2,x3,x4,x5;
  186.     x0 = d[0];
  187.     x1 = d[1];
  188.     x2 = d[2];
  189.     x3 = d[3];
  190.     x4 = d[4];
  191.     x5 = d[5];
  192.     int o0 = (x0>x1)+(x0>x2)+(x0>x3)+(x0>x4)+(x0>x5);
  193.     int o1 = (x1>=x0)+(x1>x2)+(x1>x3)+(x1>x4)+(x1>x5);
  194.     int o2 = (x2>=x0)+(x2>=x1)+(x2>x3)+(x2>x4)+(x2>x5);
  195.     int o3 = (x3>=x0)+(x3>=x1)+(x3>=x2)+(x3>x4)+(x3>x5);
  196.     int o4 = (x4>=x0)+(x4>=x1)+(x4>=x2)+(x4>=x3)+(x4>x5);
  197.     int o5 = 15-(o0+o1+o2+o3+o4);
  198.     d[o0]=x0; d[o1]=x1; d[o2]=x2; d[o3]=x3; d[o4]=x4; d[o5]=x5;
  199. }
  200.  
  201. static inline void sort6_fast_network(int * d) {
  202. //#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");
  203. //    register int x0,x1,x2,x3,x4,x5,tmp;
  204. #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
  205.     register int x0,x1,x2,x3,x4,x5;
  206.     x1 = d[1];
  207.     x2 = d[2];
  208.     SWAP(x1, x2);
  209.     x4 = d[4];
  210.     x5 = d[5];
  211.     SWAP(x4, x5);
  212.     x0 = d[0];
  213.     SWAP(x0, x2);
  214.     x3 = d[3];
  215.     SWAP(x3, x5);
  216.     SWAP(x0, x1);
  217.     SWAP(x3, x4);
  218.     SWAP(x1, x4);
  219.     SWAP(x0, x3);
  220.     d[0] = x0;
  221.     SWAP(x2, x5);
  222.     d[5] = x5;
  223.     SWAP(x1, x3);
  224.     d[1] = x1;
  225.     SWAP(x2, x4);
  226.     d[4] = x4;
  227.     SWAP(x2, x3);
  228.     d[2] = x2;
  229.     d[3] = x3;
  230.  
  231. #undef SWAP
  232. #undef min
  233. #undef max
  234. }
  235.  
  236. static inline unsigned long long rdtsc(void)
  237. {
  238.     unsigned long long int x;
  239.     asm volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
  240.     return x;
  241. }
  242.  
  243. void ran_fill(int n, int *a) {
  244.     static int seed = 76521;
  245.     while (n--) *a++ = (seed = seed *1812433253 + 12345);
  246. }
  247.  
  248.  
  249. #define NTESTS 4096
  250. int main(){
  251.  
  252. #define TEST(variant, description) {\
  253.     int i;\
  254.     int d[6*NTESTS];\
  255.     ran_fill(6*NTESTS, d);\
  256.     unsigned long long cycles = rdtsc();\
  257.     for (i = 0; i < 6*NTESTS ; i+=6){\
  258.         sort6_##variant(d+i);\
  259.     }\
  260.     cycles = rdtsc() - cycles;\
  261.     printf(description " : %.2lf\n", (double)cycles/(double)NTESTS);\
  262.     for (i = 0; i < 6*NTESTS ; i+=6) { \
  263.         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]) \
  264.             printf("d%d : %d %d %d %d %d %d\n", i, \
  265.                     d[i+0], d[i+1], d[i+2], \
  266.                     d[i+3], d[i+4], d[i+5]); \
  267.     } \
  268. }
  269.  
  270. TEST(libqsort,                "Direct call to qsort library function  ");
  271. TEST(insertion_sort_v1,       "Naive implementation (insertion sort)  ");
  272. TEST(insertion_sort_v2,       "Insertion Sort (Daniel Stutzbach)      ");
  273. TEST(insertion_sort_unrolled, "Insertion Sort Unrolled                ");
  274. TEST(rank_order,              "Rank Order                             ");
  275. TEST(rank_order_reg,          "Rank Order with registers              ");
  276. TEST(sorting_network_v1,      "Sorting Networks (Daniel Stutzbach)    ");
  277. TEST(sorting_network_v2,      "Sorting Networks (Paul R)              ");
  278. TEST(sorting_network_v3,      "Sorting Networks 12 with Fast Swap     ");
  279. TEST(sorting_network_v4,      "Sorting Networks 12 reordered Swap     ");
  280. TEST(fast_network,            "Reordered Sorting Network w/ fast swap ");
  281.  
  282. return 0;
  283.  
  284. }
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