From owner-freebsd-hackers Sat Aug 21 17: 0:38 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 8B4CE14BFF for ; Sat, 21 Aug 1999 17:00:30 -0700 (PDT) (envelope-from a-wada@mars.dti.ne.jp) Received: from a.mars.dti.ne.jp (PPP46.tachikawa-ap4.dti.ne.jp [202.216.255.46]) by smtp2.dti.ne.jp (8.9.3/3.7W) with SMTP id JAA06407; Sun, 22 Aug 1999 09:00:09 +0900 (JST) Message-Id: <199908212359.AA00049@a.mars.dti.ne.jp> From: Akira Wada Date: Sun, 22 Aug 1999 08:59:27 +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=us-ascii 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 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 partitionigs. 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) pl += es; + if (pl >= pn) return; if (n < 7) { -------------------------------------------------------------- -Akira Wada To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message