From: Florian Weimer <fw@deneb.enyo.de>
To: 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:10:48 +0100
Message-ID: <873bijsdvb.fsf@mid.deneb.enyo.de> (raw)
In-Reply-To: <1140055972.31672.42.camel@localhost.localdomain>
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>
* 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.
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: 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: <873bijsdvb.fsf@mid.deneb.enyo.de>
* 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