From: Martijn van Oosterhout <kleptog@svana.org>
To: Florian Weimer <fw@deneb.enyo.de>
Cc: Neil Conway <neilc@samurai.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Gary Doades <gpd@gpdnet.co.uk>
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: qsort again
Date: Thu, 16 Feb 2006 13:49:18 +0100
Message-ID: <20060216124918.GE26127@svana.org> (raw)
In-Reply-To: <873bijsdvb.fsf@mid.deneb.enyo.de>
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>
On Thu, Feb 16, 2006 at 01:10:48PM +0100, Florian Weimer wrote:
> * Neil Conway:
>
> > 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.
>
> 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,
--
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.
Attachments:
signature.asc (application/pgp-signature, 188B) download
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: kleptog@svana.org, fw@deneb.enyo.de, neilc@samurai.com, tgl@sss.pgh.pa.us, gpd@gpdnet.co.uk, pgsql-hackers@postgresql.org
Subject: Re: qsort again
In-Reply-To: <20060216124918.GE26127@svana.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox