From: Steinar H. Gunderson <sgunderson@bigfoot.com>
To: pgsql-performance@postgresql.org
Subject: Re: qsort again (was Re: Strange Create Index
Date: Thu, 16 Feb 2006 12:35:22 +0100
Message-ID: <20060216113522.GA3461@uio.no> (raw)
In-Reply-To: <7.0.1.0.2.20060215223710.03a7c618@earthlink.net>
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>
<7.0.1.0.2.20060215194635.03b55da0@earthlink.net>
<21615.1140052893@sss.pgh.pa.us>
<7.0.1.0.2.20060215223710.03a7c618@earthlink.net>
On Wed, Feb 15, 2006 at 11:30:54PM -0500, Ron wrote:
> Even better (and more easily scaled as the number of GPR's in the CPU
> changes) is to use
> the set {L; L+1; L+2; t>>1; R-2; R-1; R}
> This means that instead of 7 random memory accesses, we have 3; two
> of which result in a
> burst access for three elements each.
Isn't that improvement going to disappear competely if you choose a bad
pivot?
> SIDE NOTE: IIRC glibc's qsort is actually merge sort. Merge sort
> performance is insensitive to all inputs, and there are way to
> optimize it as well.
glibc-2.3.5/stdlib/qsort.c:
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
I can't see any references to merge sort in there at all.
/* Steinar */
--
Homepage: http://www.sesse.net/
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: sgunderson@bigfoot.com
Subject: Re: qsort again (was Re: Strange Create Index
In-Reply-To: <20060216113522.GA3461@uio.no>
* 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