tests/qsort_perf.c

   1 /*
   2  * Randomized test for qsort() routine.
   3  *
   4  * Includes code derived from stdlib/FreeBSD/qsort.c and the copyright header
   5  * in that file applies.
   6  */
   7
   8 #include <sys/cdefs.h>
   9
  10 #include <assert.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <darwintest.h>
  14 #include <darwintest_utils.h>
  15
  16 static void qsort1(void *aa, size_t n, size_t es,
  17         int (*cmp)(const void *, const void *));
  18
  19 static int
  20 cmp_int(const void *aa, const void *bb)
  21 {
  22     int a, b;
  23
  24     a = *(const int *)aa;
  25     b = *(const int *)bb;
  26     return(a - b);
  27 }
  28
  29 #define nelm 1000000
  30
  31 T_DECL(qsort_perf, "qsort perf test", T_META_CHECK_LEAKS(NO))
  32 {
  33     int i;
  34     int arr[nelm];
  35     int save[nelm];
  36     uint64_t time_elapsed;
  37
  38     // ----- 25-75 -----
  39
  40     int k = nelm/4;
  41     for (i = 0; i < k; i++) {
  42         save[i] = i;
  43     }
  44     for (i = k; i < nelm; i++) {
  45         save[i] = i - k;
  46     }
  47
  48     bcopy(save, arr, sizeof(arr));
  49     dt_timer_start("25-75 (qsort)");
  50     qsort(arr, nelm, sizeof(arr[0]), cmp_int);
  51     time_elapsed = dt_timer_stop("25-75 (qsort)");
  52     T_LOG("25-75 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
  53     for (i = 1; i < nelm; i++) {
  54         if(arr[i - 1] > arr[i]) {
  55             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
  56             break;
  57         }
  58     }
  59
  60     bcopy(save, arr, sizeof(arr));
  61     dt_timer_start("25-75 (Bentley)");
  62     qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
  63     time_elapsed = dt_timer_stop("25-75 (Bentley)");
  64     T_LOG("25-75 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
  65     for (i = 1; i < nelm; i++) {
  66         if(arr[i - 1] > arr[i]) {
  67             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
  68             break;
  69         }
  70     }
  71     // ----- 50-50 -----
  72
  73     k = nelm/2;
  74     for (i = 0; i < k; i++) {
  75         save[i] = i;
  76     }
  77     for (i = k; i < nelm; i++) {
  78         save[i] = i - k;
  79     }
  80
  81     bcopy(save, arr, sizeof(arr));
  82     dt_timer_start("50-50 (qsort)");
  83     qsort(arr, nelm, sizeof(arr[0]), cmp_int);
  84     time_elapsed = dt_timer_stop("50-50 (qsort)");
  85     T_LOG("50-50 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
  86     for (i = 1; i < nelm; i++) {
  87         if(arr[i - 1] > arr[i]) {
  88             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
  89             break;
  90         }
  91     }
  92
  93     bcopy(save, arr, sizeof(arr));
  94     dt_timer_start("50-50 (Bentley)");
  95     qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
  96     time_elapsed = dt_timer_stop("50-50 (Bentley)");
  97     T_LOG("50-50 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
  98     for (i = 1; i < nelm; i++) {
  99         if(arr[i - 1] > arr[i]) {
 100             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
 101             break;
 102         }
 103     }
 104
 105     // ----- median-of-3 killer -----
 106
 107     k = nelm / 2;
 108     for (i = 1; i <= k; i++) {
 109         if(i % 2 == 1) {
 110             save[i - 1] = i;
 111             save[i] = k + i;
 112         }
 113         save[k + i - 1] = 2 * i;
 114     }
 115
 116     bcopy(save, arr, sizeof(arr));
 117     dt_timer_start("median-of-3 killer (qsort)");
 118     qsort(arr, nelm, sizeof(arr[0]), cmp_int);
 119     time_elapsed = dt_timer_stop("median-of-3 killer (qsort)");
 120     T_LOG("median-of-3 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
 121     for (i = 1; i < nelm; i++) {
 122         if(arr[i - 1] > arr[i]) {
 123             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
 124         }
 125     }
 126
 127     bcopy(save, arr, sizeof(arr));
 128     dt_timer_start("median-of-3 killer (Bentley)");
 129     qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
 130     time_elapsed = dt_timer_stop("median-of-3 killer (Bentley)");
 131     T_LOG("median-of-3 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
 132     for (i = 1; i < nelm; i++) {
 133         if(arr[i - 1] > arr[i]) {
 134             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
 135         }
 136     }
 137
 138     // ----- random -----
 139
 140     for (i = 0; i < nelm; i++) {
 141         save[i] = random();
 142     }
 143
 144     bcopy(save, arr, sizeof(arr));
 145     dt_timer_start("random (qsort)");
 146     qsort(arr, nelm, sizeof(arr[0]), cmp_int);
 147     time_elapsed = dt_timer_stop("random (qsort)");
 148     T_LOG("random (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
 149     for (i = 1; i < nelm; i++) {
 150         if(arr[i - 1] > arr[i]) {
 151             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
 152         }
 153     }
 154
 155
 156     bcopy(save, arr, sizeof(arr));
 157     dt_timer_start("random (Bentley)");
 158     qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
 159     time_elapsed = dt_timer_stop("random (Bentley)");
 160     T_LOG("random (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
 161     for (i = 1; i < nelm; i++) {
 162         if(arr[i - 1] > arr[i]) {
 163             T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
 164         }
 165     }
 166
 167     T_PASS("All tests completed successfully.");
 168 }
 169
 170 /* qsort1 -- qsort interface implemented by faster quicksort */
 171
 172 #define SWAPINIT(a, es) swaptype =                            \
 173     (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \
 174     es == sizeof(long) ? 0 : 1;
 175 #define swapcode(TYPE, parmi, parmj, n) {  \
 176     long i = (n) / sizeof(TYPE);           \
 177     register TYPE *pi = (TYPE *) (parmi);  \
 178     register TYPE *pj = (TYPE *) (parmj);  \
 179     do {                                   \
 180         register TYPE t = *pi;             \
 181         *pi++ = *pj;                       \
 182         *pj++ = t;                         \
 183     } while (--i > 0);                     \
 184 }
 185 static void swapfunc(char *a, char *b, int n, int swaptype)
 186 {   if (swaptype <= 1) swapcode(long, a, b, n)
 187     else swapcode(char, a, b, n)
 188 }
 189 #define swap(a, b)                         \
 190     if (swaptype == 0) {                   \
 191         long t = * (long *) (a);           \
 192         * (long *) (a) = * (long *) (b);   \
 193         * (long *) (b) = t;                \
 194     } else                                 \
 195         swapfunc(a, b, es, swaptype)
 196 #define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)
 197
 198 #define min(x, y) ((x)<=(y) ? (x) : (y))
 199
 200 static char *med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
 201 {
 202     return cmp(a, b) < 0 ?
 203             (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) )
 204             : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) );
 205 }
 206
 207 static void
 208 qsort1(void *aa, size_t n, size_t es,
 209       int (*cmp)(const void *, const void *))
 210 {
 211         char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 212         int  d, r, swaptype;
 213         char *a = aa;
 214
 215         SWAPINIT(a, es);
 216         if (n < 7) { /* Insertion sort on small arrays */
 217                 for (pm = a + es; pm < a + n*es; pm += es)
 218                         for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
 219                                 swap(pl, pl-es);
 220                 return;
 221         }
 222         pm = a + (n/2) * es;
 223         if (n > 7) {
 224                 pl = a;
 225                 pn = a + (n-1) * es;
 226                 if (n > 40) { /* On big arrays, pseudomedian of 9 */
 227                         d = (n/8) * es;
 228                         pl = med3(pl, pl+d, pl+2*d, cmp);
 229                         pm = med3(pm-d, pm, pm+d, cmp);
 230                         pn = med3(pn-2*d, pn-d, pn, cmp);
 231                 }
 232                 pm = med3(pl, pm, pn, cmp); /* On mid arrays, med of 3 */
 233         }
 234         swap(a, pm); /* On tiny arrays, partition around middle */
 235         pa = pb = a + es;
 236         pc = pd = a + (n-1)*es;
 237         for (;;) {
 238                 while (pb <= pc && (r = cmp(pb, a)) <= 0) {
 239                         if (r == 0) { swap(pa, pb); pa += es; }
 240                         pb += es;
 241                 }
 242                 while (pb <= pc && (r = cmp(pc, a)) >= 0) {
 243                         if (r == 0) { swap(pc, pd); pd -= es; }
 244                         pc -= es;
 245                 }
 246                 if (pb > pc) break;
 247                 swap(pb, pc);
 248                 pb += es;
 249                 pc -= es;
 250         }
 251         pn = a + n*es;
 252         r = min(pa-a,  pb-pa);    vecswap(a,  pb-r, r);
 253         r = min(pd-pc, pn-pd-es); vecswap(pb, pn-r, r);
 254         if ((r = pb-pa) > es) qsort1(a, r/es, es, cmp);
 255         if ((r = pd-pc) > es) qsort1(pn-r, r/es, es, cmp);
 256 }