From owner-freebsd-hackers Sat Aug 21 17:59: 1 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from smtp2.dti.ne.jp (smtp2.dti.ne.jp [210.170.128.122]) by hub.freebsd.org (Postfix) with ESMTP id 47725150EB for ; Sat, 21 Aug 1999 17:58:58 -0700 (PDT) (envelope-from a-wada@mars.dti.ne.jp) Received: from a.mars.dti.ne.jp (PPP23.tachikawa-ap4.dti.ne.jp [202.216.255.23]) by smtp2.dti.ne.jp (8.9.3/3.7W) with SMTP id JAA08121; Sun, 22 Aug 1999 09:56:25 +0900 (JST) Message-Id: <199908220056.AA00050@a.mars.dti.ne.jp> From: Akira Wada Date: Sun, 22 Aug 1999 09:56:03 +0900 To: Archie Cobbs Cc: seiwald@perforce.com (Christopher Seiwald), freebsd-hackers@FreeBSD.ORG Subject: Re: anybody love qsort.c? In-Reply-To: <199908210135.SAA48009@bubba.whistle.com> References: <199908210135.SAA48009@bubba.whistle.com> MIME-Version: 1.0 X-Mailer: AL-Mail32 Version 1.10 Content-Type: text/plain; charset=iso-2022-jp Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Archie Cobbs wrote... >Christopher Seiwald writes: >> But as I'm proposing a change to a fairly sensitive piece of code, I'd >> like to keep the change as modest as possible. > >How about this? > >Index: qsort.c >=================================================================== >RCS file: /home/ncvs/src/lib/libc/stdlib/qsort.c,v >retrieving revision 1.7 >diff -u -r1.7 qsort.c >--- qsort.c 1997/02/22 15:03:14 1.7 >+++ qsort.c 1999/08/21 01:35:35 >@@ -153,7 +153,7 @@ > pb += es; > pc -= es; > } >- if (swap_cnt == 0) { /* Switch to insertion sort */ >+ if (n <= 32 && 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) > > >-Archie > >___________________________________________________________________________ >Archie Cobbs * Whistle Communications, Inc. * http://www.whistle.com > I think your modification would avoid the degeneration indicated by Christopher Seiwald, but degrade the advantage for the dataset sorted completely or sorted in reversed order, down to nearly equal for random dataset. I added a routine before selecting pivot to test current partition sorted already and if so, to bypass partitioning. It works well for dataset sorted in order, but doesn't work for dataset in reversed order. I believe a reversed dataset would be partitioned into two subpartitions sorted in order at the 1'st pass of the partitionings. Is this incorrect ? -------------------------------------------------------------- for qsort.c,v 1.9 1998/06/30 11:05:11 @@ -102,2 +102,5 @@ swap_cnt = 0; + pl = (char *)a; pn = (char *)a + (n - 1) * es; + while (pl < pn && cmp(pl, pl + es) <= 0) pl += es; + if (pl >= pn) return; if (n < 7) { -------------------------------------------------------------- -Akira Wada ***************************************** 和田　彬 ／ << Akira Wada >> 東京都福生市武蔵野台 1-27-5 ルネ福生 B609 (tel,fax) 042-552-1143 E-mail : a-wada@mars.dti.ne.jp ***************************************** To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message