X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id D6AA09DC9A7;
	Thu, 16 Feb 2006 08:49:41 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 80506-09; Thu, 16 Feb 2006 08:49:45 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from svana.org (svana.org [125.62.94.225])
	by postgresql.org (Postfix) with ESMTP id 8315F9DC86A;
	Thu, 16 Feb 2006 08:49:39 -0400 (AST)
Received: from kleptog by svana.org with local (Exim 4.50)
	id 1F9iZS-0007Y9-5X; Thu, 16 Feb 2006 23:49:18 +1100
Date: Thu, 16 Feb 2006 13:49:18 +0100
From: Martijn van Oosterhout <kleptog@svana.org>
To: Florian Weimer <fw@deneb.enyo.de>
Cc: Neil Conway <neilc@samurai.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	Gary Doades <gpd@gpdnet.co.uk>, pgsql-performance@postgresql.org,
	pgsql-hackers@postgresql.org
Subject: Re: qsort again
Message-ID: <20060216124918.GE26127@svana.org>
Reply-To: Martijn van Oosterhout <kleptog@svana.org>
References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us>
	<19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk>
	<20781.1140046109@sss.pgh.pa.us>
	<1140055972.31672.42.camel@localhost.localdomain>
	<873bijsdvb.fsf@mid.deneb.enyo.de>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="VUDLurXRWRKrGuMn"
Content-Disposition: inline
In-Reply-To: <873bijsdvb.fsf@mid.deneb.enyo.de>
X-PGP-Key-ID: Length=1024; ID=0x0DC67BE6
X-PGP-Key-Fingerprint: 295F A899 A81A 156D B522  48A7 6394 F08A 0DC6 7BE6
X-PGP-Key-URL: <http://svana.org/kleptog/0DC67BE6.pgp.asc>
User-Agent: Mutt/1.5.9i
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Mail-From: kleptog@svana.org
X-SA-Exim-Scanned: No (on svana.org); SAEximRunCond expanded to false
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.121 required=5 tests=[AWL=0.121]
X-Spam-Score: 0.121
X-Spam-Level: 
X-Archive-Number: 200602/617
X-Sequence-Number: 79755


--VUDLurXRWRKrGuMn
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Feb 16, 2006 at 01:10:48PM +0100, Florian Weimer wrote:
> * Neil Conway:
>=20
> > On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
> >> It seems clear that our qsort.c is doing a pretty awful job of picking
> >> qsort pivots, while glibc is mostly managing not to make that mistake.
> >> I haven't looked at the glibc code yet to see what they are doing
> >> differently.
> >
> > glibc qsort is actually merge sort, so I'm not surprised it avoids this
> > problem.
>=20
> qsort also performs twice as many key comparisons as the theoretical
> minimum.  If key comparison is not very cheap, other schemes (like
> heapsort, for example) are more attractive.

Last time around there were a number of different algorithms tested.
Did anyone run those tests while getting it to count the number of
actual comparisons (which could easily swamp the time taken to do the
actual sort in some cases)?

Have a nice day,
--=20
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

--VUDLurXRWRKrGuMn
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFD9HTOIB7bNG8LQkwRAlzeAJ9Vf2SSm2YzPK9xMWxkf3bVLz5P7ACfReyV
447sapSOkSO6/NtDqjGuV20=
=Fpm+
-----END PGP SIGNATURE-----

--VUDLurXRWRKrGuMn--