[apple/libc.git] / tests / qsort_perf.c

/*
 * 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);
}
Commit	Line	Data
b061a43b A	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	}