| 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 | } |