Loading...
--- /dev/null
+++ Libc/Libc-1669.60.4/tests/qsort_perf.c
@@ -0,0 +1,256 @@
+/*
+ * Randomized test for qsort() routine.
+ *
+ * Includes code derived from stdlib/FreeBSD/qsort.c and the copyright header
+ * in that file applies.
+ */
+
+#include <sys/cdefs.h>
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <darwintest.h>
+#include <darwintest_utils.h>
+
+static void qsort1(void *aa, size_t n, size_t es,
+ int (*cmp)(const void *, const void *));
+
+static int
+cmp_int(const void *aa, const void *bb)
+{
+ int a, b;
+
+ a = *(const int *)aa;
+ b = *(const int *)bb;
+ return(a - b);
+}
+
+#define nelm 1000000
+
+T_DECL(qsort_perf, "qsort perf test", T_META_CHECK_LEAKS(NO))
+{
+ int i;
+ int arr[nelm];
+ int save[nelm];
+ uint64_t time_elapsed;
+
+ // ----- 25-75 -----
+
+ int k = nelm/4;
+ for (i = 0; i < k; i++) {
+ save[i] = i;
+ }
+ for (i = k; i < nelm; i++) {
+ save[i] = i - k;
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("25-75 (qsort)");
+ qsort(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("25-75 (qsort)");
+ T_LOG("25-75 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ break;
+ }
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("25-75 (Bentley)");
+ qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("25-75 (Bentley)");
+ T_LOG("25-75 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ break;
+ }
+ }
+ // ----- 50-50 -----
+
+ k = nelm/2;
+ for (i = 0; i < k; i++) {
+ save[i] = i;
+ }
+ for (i = k; i < nelm; i++) {
+ save[i] = i - k;
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("50-50 (qsort)");
+ qsort(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("50-50 (qsort)");
+ T_LOG("50-50 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ break;
+ }
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("50-50 (Bentley)");
+ qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("50-50 (Bentley)");
+ T_LOG("50-50 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ break;
+ }
+ }
+
+ // ----- median-of-3 killer -----
+
+ k = nelm / 2;
+ for (i = 1; i <= k; i++) {
+ if(i % 2 == 1) {
+ save[i - 1] = i;
+ save[i] = k + i;
+ }
+ save[k + i - 1] = 2 * i;
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("median-of-3 killer (qsort)");
+ qsort(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("median-of-3 killer (qsort)");
+ T_LOG("median-of-3 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ }
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("median-of-3 killer (Bentley)");
+ qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("median-of-3 killer (Bentley)");
+ T_LOG("median-of-3 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ }
+ }
+
+ // ----- random -----
+
+ for (i = 0; i < nelm; i++) {
+ save[i] = random();
+ }
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("random (qsort)");
+ qsort(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("random (qsort)");
+ T_LOG("random (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ }
+ }
+
+
+ bcopy(save, arr, sizeof(arr));
+ dt_timer_start("random (Bentley)");
+ qsort1(arr, nelm, sizeof(arr[0]), cmp_int);
+ time_elapsed = dt_timer_stop("random (Bentley)");
+ T_LOG("random (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC);
+ for (i = 1; i < nelm; i++) {
+ if(arr[i - 1] > arr[i]) {
+ T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]);
+ }
+ }
+
+ T_PASS("All tests completed successfully.");
+}
+
+/* qsort1 -- qsort interface implemented by faster quicksort */
+
+#define SWAPINIT(a, es) swaptype = \
+ (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \
+ es == sizeof(long) ? 0 : 1;
+#define swapcode(TYPE, parmi, parmj, n) { \
+ long i = (n) / sizeof(TYPE); \
+ register TYPE *pi = (TYPE *) (parmi); \
+ register TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ register TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+}
+static void swapfunc(char *a, char *b, int n, int swaptype)
+{ if (swaptype <= 1) swapcode(long, a, b, n)
+ else swapcode(char, a, b, n)
+}
+#define swap(a, b) \
+ if (swaptype == 0) { \
+ long t = * (long *) (a); \
+ * (long *) (a) = * (long *) (b); \
+ * (long *) (b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype)
+#define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)
+
+#define min(x, y) ((x)<=(y) ? (x) : (y))
+
+static char *med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
+{
+ return cmp(a, b) < 0 ?
+ (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) )
+ : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) );
+}
+
+static void
+qsort1(void *aa, size_t n, size_t es,
+ int (*cmp)(const void *, const void *))
+{
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ int d, r, swaptype;
+ char *a = aa;
+
+ SWAPINIT(a, es);
+ if (n < 7) { /* Insertion sort on small arrays */
+ for (pm = a + es; pm < a + n*es; pm += es)
+ for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
+ swap(pl, pl-es);
+ return;
+ }
+ pm = a + (n/2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = a + (n-1) * es;
+ if (n > 40) { /* On big arrays, pseudomedian of 9 */
+ d = (n/8) * es;
+ pl = med3(pl, pl+d, pl+2*d, cmp);
+ pm = med3(pm-d, pm, pm+d, cmp);
+ pn = med3(pn-2*d, pn-d, pn, cmp);
+ }
+ pm = med3(pl, pm, pn, cmp); /* On mid arrays, med of 3 */
+ }
+ swap(a, pm); /* On tiny arrays, partition around middle */
+ pa = pb = a + es;
+ pc = pd = a + (n-1)*es;
+ for (;;) {
+ while (pb <= pc && (r = cmp(pb, a)) <= 0) {
+ if (r == 0) { swap(pa, pb); pa += es; }
+ pb += es;
+ }
+ while (pb <= pc && (r = cmp(pc, a)) >= 0) {
+ if (r == 0) { swap(pc, pd); pd -= es; }
+ pc -= es;
+ }
+ if (pb > pc) break;
+ swap(pb, pc);
+ pb += es;
+ pc -= es;
+ }
+ pn = a + n*es;
+ r = min(pa-a, pb-pa); vecswap(a, pb-r, r);
+ r = min(pd-pc, pn-pd-es); vecswap(pb, pn-r, r);
+ if ((r = pb-pa) > es) qsort1(a, r/es, es, cmp);
+ if ((r = pd-pc) > es) qsort1(pn-r, r/es, es, cmp);
+}