From owner-svn-src-head@freebsd.org Fri May 19 04:59:13 2017 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id A144DD72DC4; Fri, 19 May 2017 04:59:13 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4CDF717B4; Fri, 19 May 2017 04:59:13 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v4J4xCGw022615; Fri, 19 May 2017 04:59:12 GMT (envelope-from delphij@FreeBSD.org) Received: (from delphij@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v4J4xCqq022614; Fri, 19 May 2017 04:59:12 GMT (envelope-from delphij@FreeBSD.org) Message-Id: <201705190459.v4J4xCqq022614@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: delphij set sender to delphij@FreeBSD.org using -f From: Xin LI Date: Fri, 19 May 2017 04:59:12 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r318515 - head/lib/libc/stdlib X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 19 May 2017 04:59:13 -0000 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);*/ }