Date: Fri, 19 May 2017 04:59:12 +0000 (UTC) From: Xin LI <delphij@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r318515 - head/lib/libc/stdlib Message-ID: <201705190459.v4J4xCqq022614@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: delphij Date: Fri May 19 04:59:12 2017 New Revision: 318515 URL: https://svnweb.freebsd.org/changeset/base/318515 Log: The current qsort(3) implementation ignores the sizes of partitions, and always perform recursion on the left partition, then use a tail call to handle the right partition. In the worst case this could require O(N) levels of recursions. Reduce the possible recursion level to log2(N) by always recursing on the smaller partition instead. Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096 Modified: head/lib/libc/stdlib/qsort.c Modified: head/lib/libc/stdlib/qsort.c ============================================================================== --- head/lib/libc/stdlib/qsort.c Fri May 19 04:44:14 2017 (r318514) +++ head/lib/libc/stdlib/qsort.c Fri May 19 04:59:12 2017 (r318515) @@ -117,7 +117,7 @@ qsort(void *a, size_t n, size_t es, cmp_ #endif { char *pa, *pb, *pc, *pd, *pl, *pm, *pn; - size_t d, r; + size_t d1, d2; int cmp_result; int swaptype_long, swaptype_int, swap_cnt; @@ -137,7 +137,8 @@ loop: SWAPINIT(long, a, es); pl = a; pn = (char *)a + (n - 1) * es; if (n > 40) { - d = (n / 8) * es; + size_t d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); pm = med3(pm - d, pm, pm + d, cmp, thunk); pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); @@ -182,21 +183,43 @@ loop: SWAPINIT(long, a, es); } pn = (char *)a + n * es; - r = MIN(pa - (char *)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) + d1 = MIN(pa - (char *)a, pb - pa); + vecswap(a, pb - d1, d1); + d1 = MIN(pd - pc, pn - pd - es); + vecswap(pb, pn - d1, d1); + + d1 = pb - pa; + d2 = pd - pc; + if (d1 <= d2) { + /* Recurse on left partition, then iterate on right partition */ + if (d1 > es) { #ifdef I_AM_QSORT_R - qsort_r(a, r / es, es, thunk, cmp); + qsort_r(a, d1 / es, es, thunk, cmp); #else - qsort(a, r / es, es, cmp); + qsort(a, d1 / es, es, cmp); #endif - if ((r = pd - pc) > es) { - /* Iterate rather than recurse to save stack space */ - a = pn - r; - n = r / es; - goto loop; + } + if (d2 > es) { + /* Iterate rather than recurse to save stack space */ + /* qsort(pn - d2, d2 / es, es, cmp); */ + a = pn - d2; + n = d2 / es; + goto loop; + } + } else { + /* Recurse on right partition, then iterate on left partition */ + if (d2 > es) { +#ifdef I_AM_QSORT_R + qsort_r(pn - d2, d2 / es, es, thunk, cmp); +#else + qsort(pn - d2, d2 / es, es, cmp); +#endif + } + if (d1 > es) { + /* Iterate rather than recurse to save stack space */ + /* qsort(a, d1 / es, es, cmp); */ + n = d1 / es; + goto loop; + } } -/* qsort(pn - r, r / es, es, cmp);*/ }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201705190459.v4J4xCqq022614>