From owner-freebsd-hackers  Mon Aug 23  0:28:57 1999
Delivered-To: freebsd-hackers@freebsd.org
Received: from perforce.com (spice.perforce.com [206.14.52.195])
	by hub.freebsd.org (Postfix) with ESMTP id 93B0814CAB
	for <freebsd-hackers@FreeBSD.ORG>; Mon, 23 Aug 1999 00:28:53 -0700 (PDT)
	(envelope-from seiwald@perforce.com)
Received: (from seiwald@localhost)
	by perforce.com (8.9.3/8.9.3) id AAA24061;
	Mon, 23 Aug 1999 00:28:32 -0700 (PDT)
	(envelope-from seiwald)
Date: Mon, 23 Aug 1999 00:28:32 -0700 (PDT)
From: Christopher Seiwald <seiwald@perforce.com>
Message-Id: <199908230728.AAA24061@perforce.com>
To: a-wada@mars.dti.ne.jp, archie@whistle.com
Subject: Re: anybody love qsort.c?
Cc: freebsd-hackers@FreeBSD.ORG
In-Reply-To: <199908220056.AA00050@a.mars.dti.ne.jp>
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

Archie's mod to qsort:

|  >-	if (swap_cnt == 0) {  /* Switch to insertion sort */
|  >+	if (n <= 32 && swap_cnt == 0) {  /* Switch to insertion sort */

As Akira Wada points out, this eliminates the benefit of the optimization
in the first place, which is to let isort take over if the data is largely
sorted in the first place.

Akira Wada's alternative mod:

| +       pl = (char *)a; pn = (char *)a + (n - 1) * es;
| +       while (pl < pn && cmp(pl, pl + es) <= 0) pl += es;
| +       if (pl >= pn) return;

This is a little more comprehensive, but does throw in an extra pass
of comparisons, which (I'm sure) someone would complain about.

The alteration that I've tried and tested is to have the isort bail
back to qsort if it does more than N swaps.  I put N at 1024, which
worked for my data :).    This is almost guaranteed to do no more work
than the current logic, because it it only gives up on the isort when
it has evidence that the isort is doing too much work.

Christopher


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message