API tools faq
paste
Guest User

qsort native, inline, block

a guest
Jan 28th, 2017
83
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 13.58 KB | None | 0 0
raw download clone embed print report
  1. /*  $OpenBSD: qsort.c,v 1.11 2010/02/08 11:04:07 otto Exp $ */
  2. /*-
  3.  * Jan.28.2017 Rick C. Hodgin -- See if inlining or blocks are faster.
  4.  *             Average results Win7:  Native=78, Inline=47, Block=31
  5.  *
  6.  * Copyright (c) 1992, 1993
  7.  *  The Regents of the University of California.  All rights reserved.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  * 1. Redistributions of source code must retain the above copyright
  13.  *    notice, this list of conditions and the following disclaimer.
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in the
  16.  *    documentation and/or other materials provided with the distribution.
  17.  * 3. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #include <sys/types.h>
  35. #include <stdio.h>
  36. #include <stdlib.h>
  37. #include <windows.h>
  38.  
  39. typedef unsigned long long u64;
  40.  
  41. static __inline void     swapfunc(char *, char *, size_t, int);
  42. static __inline char    *med3_native(char *, char *, char *, int (*)(const void *, const void *));
  43. static __inline char    *med3_inline(char *, char *, char *);
  44. static __inline char    *med3_block(char *, char *, char *);
  45.  
  46. #define compare_block(l, r) (((*(int*)l < *(int*)r) ? -1 : ((*(int*)l > *(int*)r) ? 1 : 0)))
  47. //#define compare_block_asm(l, r) (((*(int*)l < *(int*)r) ? -1 : ((*(int*)l > *(int*)r) ? 1 : 0)))
  48.  
  49. #define mymin(a, b) (((a) < (b)) ? a : b)
  50.  
  51.  
  52. int compare(const void* left, const void* right)
  53. {
  54.     int l, r;
  55.  
  56.  
  57.     l = *(int*)left;
  58.     r = *(int*)right;
  59.  
  60.          if (l < r)     return(-1);     // Left is less
  61.     else if (l > r)     return(1);      // Left is greater
  62.     else                return(0);      // Equal
  63. }
  64.  
  65. /*
  66.  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  67.  */
  68. #define swapcode(TYPE, parmi, parmj, n) {       \
  69.     size_t i = (n) / sizeof (TYPE);         \
  70.     TYPE *pi = (TYPE *) (parmi);            \
  71.     TYPE *pj = (TYPE *) (parmj);            \
  72.     do {                        \
  73.         TYPE    t = *pi;            \
  74.         *pi++ = *pj;                \
  75.         *pj++ = t;              \
  76.         } while (--i > 0);              \
  77. }
  78.  
  79. #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  80.     es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
  81.  
  82. static __inline void
  83. swapfunc(char *a, char *b, size_t n, int swaptype)
  84. {
  85.     if (swaptype <= 1)
  86.         swapcode(long, a, b, n)
  87.     else
  88.         swapcode(char, a, b, n)
  89. }
  90.  
  91. #define swap(a, b)                  \
  92.     if (swaptype == 0) {                \
  93.         long t = *(long *)(a);          \
  94.         *(long *)(a) = *(long *)(b);        \
  95.         *(long *)(b) = t;           \
  96.     } else                      \
  97.         swapfunc(a, b, es, swaptype)
  98.  
  99. #define vecswap(a, b, n)    if ((n) > 0) swapfunc(a, b, n, swaptype)
  100.  
  101. static __inline char *
  102. med3_native(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
  103. {
  104.     return cmp(a, b) < 0    ?   (cmp(b, c) < 0  ?   b
  105.                                                 :   (cmp(a, c) < 0  ?   c
  106.                                                                     :   a ))
  107.                             :   (cmp(b, c) > 0  ?   b
  108.                                                 :   (cmp(a, c) < 0  ?   a
  109.                                                                     :   c ));
  110. }
  111.  
  112. static __inline char *
  113. med3_inline(char *a, char *b, char *c)
  114. {
  115.     return compare(a, b) < 0    ?   (compare(b, c) < 0  ?   b
  116.                                                         :   (compare(a, c) < 0  ?   c
  117.                                                                                 :   a ))
  118.                                 :   (compare(b, c) > 0  ?   b
  119.                                                         :   (compare(a, c) < 0  ?   a
  120.                                                                                 :   c ));
  121. }
  122.  
  123. static __inline char *
  124. med3_block(char *a, char *b, char *c)
  125. {
  126.     return compare_block(a, b) < 0  ?   (compare_block(b, c) < 0    ?   b
  127.                                                                     :   (compare_block(a, c) < 0    ?   c
  128.                                                                                                     :   a ))
  129.                                     :   (compare_block(b, c) > 0    ?   b
  130.                                                                     :   (compare_block(a, c) < 0    ?   a
  131.                                                                                                     :   c ));
  132. }
  133.  
  134. void
  135. myqsort_native(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *))
  136. {
  137.     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  138.     int cmp_result, swaptype, swap_cnt;
  139.     size_t d, r;
  140.     char *a = (char *)aa;
  141.  
  142. loop:   SWAPINIT(a, es);
  143.     swap_cnt = 0;
  144.     if (n < 7) {
  145.         for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
  146.             for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
  147.                  pl -= es)
  148.                 swap(pl, pl - es);
  149.         return;
  150.     }
  151.     pm = (char *)a + (n / 2) * es;
  152.     if (n > 7) {
  153.         pl = (char *)a;
  154.         pn = (char *)a + (n - 1) * es;
  155.         if (n > 40) {
  156.             d = (n / 8) * es;
  157.             pl = med3_native(pl,            pl + d,     pl + 2 * d,     cmp);
  158.             pm = med3_native(pm - d,        pm,         pm + d,         cmp);
  159.             pn = med3_native(pn - 2 * d,    pn - d,     pn,             cmp);
  160.         } else {
  161.             pm = med3_native(pl,            pm,         pn,             cmp);
  162.         }
  163.     }
  164.     swap(a, pm);
  165.     pa = pb = (char *)a + es;
  166.  
  167.     pc = pd = (char *)a + (n - 1) * es;
  168.     for (;;) {
  169.         while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
  170.             if (cmp_result == 0) {
  171.                 swap_cnt = 1;
  172.                 swap(pa, pb);
  173.                 pa += es;
  174.             }
  175.             pb += es;
  176.         }
  177.         while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
  178.             if (cmp_result == 0) {
  179.                 swap_cnt = 1;
  180.                 swap(pc, pd);
  181.                 pd -= es;
  182.             }
  183.             pc -= es;
  184.         }
  185.         if (pb > pc)
  186.             break;
  187.         swap(pb, pc);
  188.         swap_cnt = 1;
  189.         pb += es;
  190.         pc -= es;
  191.     }
  192.     if (swap_cnt == 0) {  /* Switch to insertion sort */
  193.         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
  194.             for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
  195.                  pl -= es)
  196.                 swap(pl, pl - es);
  197.         return;
  198.     }
  199.  
  200.     pn = (char *)a + n * es;
  201.     r = mymin(pa - (char *)a, pb - pa);
  202.     vecswap(a, pb - r, r);
  203.     r = mymin(pd - pc, pn - pd - es);
  204.     vecswap(pb, pn - r, r);
  205.     if ((r = pb - pa) > es)
  206.         myqsort_native(a, r / es, es, cmp);
  207.     if ((r = pd - pc) > es) {
  208.         /* Iterate rather than recurse to save stack space */
  209.         a = pn - r;
  210.         n = r / es;
  211.         goto loop;
  212.     }
  213. /*      qsort(pn - r, r / es, es, cmp);*/
  214. }
  215.  
  216. void
  217. myqsort_inline(void *aa, size_t n, size_t es)
  218. {
  219.     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  220.     int cmp_result, swaptype, swap_cnt;
  221.     size_t d, r;
  222.     char *a = (char *)aa;
  223.  
  224. loop:   SWAPINIT(a, es);
  225.     swap_cnt = 0;
  226.     if (n < 7) {
  227.         for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
  228.             for (pl = pm; pl > (char *) a && compare(pl - es, pl) > 0;
  229.                  pl -= es)
  230.                 swap(pl, pl - es);
  231.         return;
  232.     }
  233.     pm = (char *)a + (n / 2) * es;
  234.     if (n > 7) {
  235.         pl = (char *)a;
  236.         pn = (char *)a + (n - 1) * es;
  237.         if (n > 40) {
  238.             d = (n / 8) * es;
  239.             pl = med3_inline(pl,            pl + d,     pl + 2 * d);
  240.             pm = med3_inline(pm - d,        pm,         pm + d);
  241.             pn = med3_inline(pn - 2 * d,    pn - d,     pn);
  242.         } else {
  243.             pm = med3_inline(pl,            pm,         pn);
  244.         }
  245.     }
  246.     swap(a, pm);
  247.     pa = pb = (char *)a + es;
  248.  
  249.     pc = pd = (char *)a + (n - 1) * es;
  250.     for (;;) {
  251.         while (pb <= pc && (cmp_result = compare(pb, a)) <= 0) {
  252.             if (cmp_result == 0) {
  253.                 swap_cnt = 1;
  254.                 swap(pa, pb);
  255.                 pa += es;
  256.             }
  257.             pb += es;
  258.         }
  259.         while (pb <= pc && (cmp_result = compare(pc, a)) >= 0) {
  260.             if (cmp_result == 0) {
  261.                 swap_cnt = 1;
  262.                 swap(pc, pd);
  263.                 pd -= es;
  264.             }
  265.             pc -= es;
  266.         }
  267.         if (pb > pc)
  268.             break;
  269.         swap(pb, pc);
  270.         swap_cnt = 1;
  271.         pb += es;
  272.         pc -= es;
  273.     }
  274.     if (swap_cnt == 0) {  /* Switch to insertion sort */
  275.         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
  276.             for (pl = pm; pl > (char *) a && compare(pl - es, pl) > 0;
  277.                  pl -= es)
  278.                 swap(pl, pl - es);
  279.         return;
  280.     }
  281.  
  282.     pn = (char *)a + n * es;
  283.     r = mymin(pa - (char *)a, pb - pa);
  284.     vecswap(a, pb - r, r);
  285.     r = mymin(pd - pc, pn - pd - es);
  286.     vecswap(pb, pn - r, r);
  287.     if ((r = pb - pa) > es)
  288.         myqsort_inline(a, r / es, es);
  289.     if ((r = pd - pc) > es) {
  290.         /* Iterate rather than recurse to save stack space */
  291.         a = pn - r;
  292.         n = r / es;
  293.         goto loop;
  294.     }
  295. /*      qsort(pn - r, r / es, es, cmp);*/
  296. }
  297.  
  298. void
  299. myqsort_block(void *aa, size_t n, size_t es)
  300. {
  301.     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  302.     int cmp_result, swaptype, swap_cnt;
  303.     size_t d, r;
  304.     char *a = (char *)aa;
  305.  
  306. loop:   SWAPINIT(a, es);
  307.     swap_cnt = 0;
  308.     if (n < 7) {
  309.         for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
  310.             for (pl = pm; pl > (char *) a && compare(pl - es, pl) > 0;
  311.                  pl -= es)
  312.                 swap(pl, pl - es);
  313.         return;
  314.     }
  315.     pm = (char *)a + (n / 2) * es;
  316.     if (n > 7) {
  317.         pl = (char *)a;
  318.         pn = (char *)a + (n - 1) * es;
  319.         if (n > 40) {
  320.             d = (n / 8) * es;
  321.             pl = med3_block(pl,         pl + d,     pl + 2 * d);
  322.             pm = med3_block(pm - d,     pm,         pm + d);
  323.             pn = med3_block(pn - 2 * d, pn - d,     pn);
  324.         } else {
  325.             pm = med3_block(pl,         pm,         pn);
  326.         }
  327.     }
  328.     swap(a, pm);
  329.     pa = pb = (char *)a + es;
  330.  
  331.     pc = pd = (char *)a + (n - 1) * es;
  332.     for (;;) {
  333.         while (pb <= pc && (cmp_result = compare_block(pb, a)) <= 0) {
  334.             if (cmp_result == 0) {
  335.                 swap_cnt = 1;
  336.                 swap(pa, pb);
  337.                 pa += es;
  338.             }
  339.             pb += es;
  340.         }
  341.         while (pb <= pc && (cmp_result = compare_block(pc, a)) >= 0) {
  342.             if (cmp_result == 0) {
  343.                 swap_cnt = 1;
  344.                 swap(pc, pd);
  345.                 pd -= es;
  346.             }
  347.             pc -= es;
  348.         }
  349.         if (pb > pc)
  350.             break;
  351.         swap(pb, pc);
  352.         swap_cnt = 1;
  353.         pb += es;
  354.         pc -= es;
  355.     }
  356.     if (swap_cnt == 0) {  /* Switch to insertion sort */
  357.         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
  358.             for (pl = pm; pl > (char *) a && compare(pl - es, pl) > 0;
  359.                  pl -= es)
  360.                 swap(pl, pl - es);
  361.         return;
  362.     }
  363.  
  364.     pn = (char *)a + n * es;
  365.     r = mymin(pa - (char *)a, pb - pa);
  366.     vecswap(a, pb - r, r);
  367.     r = mymin(pd - pc, pn - pd - es);
  368.     vecswap(pb, pn - r, r);
  369.     if ((r = pb - pa) > es)
  370.         myqsort_inline(a, r / es, es);
  371.     if ((r = pd - pc) > es) {
  372.         /* Iterate rather than recurse to save stack space */
  373.         a = pn - r;
  374.         n = r / es;
  375.         goto loop;
  376.     }
  377. /*      qsort(pn - r, r / es, es, cmp);*/
  378. }
  379.  
  380. int array[100000];
  381.  
  382. int main(int argc, char* argv[])
  383. {
  384.     int     i, j, pass, subpass, iter_size, array_size;
  385.     u64     deltaNative, deltaInline, deltaBlock, deltaNativeBest, deltaInlineBest, deltaBlockBest, deltaNativeAvg, deltaInlineAvg, deltaBlockAvg, startTick;
  386.     char*   description;
  387.  
  388.     // This algorithm breaks down the qsort() algorithm into three forms:
  389.     //
  390.     //      Native -- the original qsort algorithm from:  https://raw.githubusercontent.com/01org/linux-sgx/master/sdk/tlibc/stdlib/qsort.c
  391.     //      Inline -- removing the callback, and directly calling the function with full optimizations at compile-time.
  392.     //      Blocks -- replacing the callback with a macro which handles the compare directly.
  393.     //
  394.     // Tests were computed on 100K, 10K, and 1K array[] sizes.
  395.  
  396.     for (pass = 0; pass < 3; pass++)
  397.     {
  398.         deltaNativeBest = 9999999999999;
  399.         deltaInlineBest = 9999999999999;
  400.         deltaBlockBest  = 9999999999999;
  401.  
  402.         deltaNativeAvg  = 0;
  403.         deltaInlineAvg  = 0;
  404.         deltaBlockAvg   = 0;
  405.  
  406.         // Determine sort size
  407.         switch (pass)
  408.         {
  409.             case 0:
  410.                 array_size  = 100000;
  411.                 iter_size   = 50;
  412.                 description = "100K";
  413.                 break;
  414.             case 1:
  415.                 array_size  = 10000;
  416.                 iter_size   = 500;
  417.                 description = " 10K";
  418.                 break;
  419.             case 2:
  420.                 array_size  = 1000;
  421.                 iter_size   = 5000;
  422.                 description = "  1K";
  423.                 break;
  424.         }
  425.  
  426.         for (subpass = 0; subpass < 10; subpass++)
  427.         {
  428.             //////////
  429.             // Native
  430.             //////
  431.                 deltaNative = 0;
  432.                 srand((pass + 1) * subpass);
  433.                 for (i = 0; i < iter_size; i++)
  434.                 {
  435.                     // Generate all random numbers
  436.                     for (j = 0; j < array_size; j++)
  437.                         array[j] = rand();
  438.  
  439.                     startTick = GetTickCount64();
  440.                     myqsort_native(&array[0], array_size, sizeof(int), compare);
  441.                     deltaNative += GetTickCount64() - startTick;
  442.                 }
  443.  
  444.  
  445.             //////////
  446.             // Inline
  447.             //////
  448.                 deltaInline = 0;
  449.                 srand((pass + 1) * subpass);
  450.                 for (i = 0; i < iter_size; i++)
  451.                 {
  452.                     // Re-generate
  453.                     for (j = 0; j < array_size; j++)
  454.                         array[j] = rand();
  455.  
  456.                     startTick = GetTickCount64();
  457.                     myqsort_inline(&array[0], array_size, sizeof(int));
  458.                     deltaInline += GetTickCount64() - startTick;
  459.                 }
  460.  
  461.  
  462.             //////////
  463.             // Block
  464.             //////
  465.                 deltaBlock = 0;
  466.                 srand((pass + 1) * subpass);
  467.                 for (i = 0; i < iter_size; i++)
  468.                 {
  469.                     // Re-generate
  470.                     for (j = 0; j < array_size; j++)
  471.                         array[j] = rand();
  472.  
  473.                     startTick = GetTickCount64();
  474.                     myqsort_block(&array[0], array_size, sizeof(int));
  475.                     deltaBlock += GetTickCount64() - startTick;
  476.                 }
  477.  
  478.  
  479. //          // Report results
  480. //          printf("%s subpass %d Native = %I64d\n", description, subpass, deltaNative);
  481. //          printf("%s subpass %d Inline = %I64d\n", description, subpass, deltaInline);
  482. //          printf("%s subpass %d  Block = %I64d\n", description, subpass, deltaBlock);
  483.  
  484.             // Store best
  485.             deltaNativeBest = min(deltaNativeBest, deltaNative);
  486.             deltaInlineBest = min(deltaInlineBest, deltaInline);
  487.             deltaBlockBest  = min(deltaBlockBest,  deltaBlock);
  488.  
  489.             // Store for average
  490.             deltaNativeAvg  += deltaNative;
  491.             deltaInlineAvg  += deltaInline;
  492.             deltaBlockAvg   += deltaBlock;
  493.         }
  494.  
  495.         printf("%s Native best = %I64d,\taverage = %I64d)\n", description, deltaNativeBest, deltaNativeAvg / subpass);
  496.         printf("%s Inline best = %I64d,\taverage = %I64d)\n", description, deltaInlineBest, deltaInlineAvg / subpass);
  497.         printf("%s  Block best = %I64d,\taverage = %I64d)\n\n", description, deltaBlockBest, deltaBlockAvg / subpass);
  498.     }
  499.  
  500.  
  501.     return 0;
  502. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!