Module Name: src
Committed By: yamt
Date: Mon Jun 1 06:37:40 UTC 2009
Modified Files:
src/lib/libc/stdlib: qsort.c
Log Message:
qsort: remove the "switch to insertion sort" optimization because it
causes catastrophic performance for certain inputs.
To generate a diff of this commit:
cvs rdiff -u -r1.19 -r1.20 src/lib/libc/stdlib/qsort.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/lib/libc/stdlib/qsort.c
diff -u src/lib/libc/stdlib/qsort.c:1.19 src/lib/libc/stdlib/qsort.c:1.20
--- src/lib/libc/stdlib/qsort.c:1.19 Fri Jan 30 23:38:44 2009
+++ src/lib/libc/stdlib/qsort.c Mon Jun 1 06:37:40 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: qsort.c,v 1.19 2009/01/30 23:38:44 lukem Exp $ */
+/* $NetBSD: qsort.c,v 1.20 2009/06/01 06:37:40 yamt Exp $ */
/*-
* Copyright (c) 1992, 1993
@@ -34,7 +34,7 @@
#if 0
static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
#else
-__RCSID("$NetBSD: qsort.c,v 1.19 2009/01/30 23:38:44 lukem Exp $");
+__RCSID("$NetBSD: qsort.c,v 1.20 2009/06/01 06:37:40 yamt Exp $");
#endif
#endif /* LIBC_SCCS and not lint */
@@ -103,13 +103,12 @@
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
size_t d, r;
- int swaptype, swap_cnt, cmp_result;
+ int swaptype, cmp_result;
_DIAGASSERT(a != NULL);
_DIAGASSERT(cmp != NULL);
loop: SWAPINIT(a, es);
- swap_cnt = 0;
if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
@@ -136,7 +135,6 @@
for (;;) {
while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
if (cmp_result == 0) {
- swap_cnt = 1;
swap(pa, pb);
pa += es;
}
@@ -144,7 +142,6 @@
}
while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
if (cmp_result == 0) {
- swap_cnt = 1;
swap(pc, pd);
pd -= es;
}
@@ -153,17 +150,9 @@
if (pb > pc)
break;
swap(pb, pc);
- swap_cnt = 1;
pb += es;
pc -= es;
}
- if (swap_cnt == 0) { /* Switch to insertion sort */
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
- pl -= es)
- swap(pl, pl - es);
- return;
- }
pn = (char *) a + n * es;
r = min(pa - (char *) a, pb - pa);
