pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Neil Conway <neilc@samurai.com>
To: Steinar H. Gunderson <sgunderson@bigfoot.com>
Cc: pgsql-performance@postgresql.org, PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Date: Thu, 16 Feb 2006 14:14:03 -0500
Message-ID: <1140117243.31672.54.camel@localhost.localdomain> (raw)
In-Reply-To: <20060216113522.GA3461@uio.no>
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>
	<20060216113522.GA3461@uio.no>

On Thu, 2006-02-16 at 12:35 +0100, Steinar H. Gunderson wrote:
> 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.

stdlib/qsort.c defines _quicksort(), not qsort(), which is defined by
msort.c. On looking closer, it seems glibc actually tries to determine
the physical memory in the machine -- if it is sorting a single array
that exceeds 1/4 of the machine's physical memory, it uses quick sort,
otherwise it uses merge sort.

-Neil





view thread (56+ messages)  latest in thread

Message-ID: <1140117243.31672.54.camel@localhost.localdomain>
Permalink:  ../1140117243.31672.54.camel@localhost.localdomain/
Also on:    postgresql.org/message-id/1140117243.31672.54.camel@localhost.localdomain

 · 

reply
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: neilc@samurai.com, sgunderson@bigfoot.com, pgsql-hackers@postgresql.org
  Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
  In-Reply-To: <1140117243.31672.54.camel@localhost.localdomain>

* 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