Re: Which qsort is used

Strike "switches to qsort" insert "switches to heapsort"

> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] On Behalf Of Dann Corbit
> Sent: Tuesday, December 13, 2005 10:40 AM
> To: Qingqing Zhou; Luke Lonergan
> Cc: Tom Lane; Neil Conway; Bruce Momjian; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Which qsort is used
>
> Here is a sort template (that can very easily be turned into a C
> routine).
>
> It is an introspective sort.  Bentley & McIlroy proved that every
qsort
> routine will degrade into quadratic behavior with a worst-case input.
> This function detects quadratic behavior and switches to qsort when
      heapsort 
> needed.
>
> Use of this template is totally unrestricted.
>
> I sent a copy to the author of FastDB and it is what he uses for
> ordering data, as he found it to be an excellent performer.
>
> It uses all the standard tricks to ensure good performance.
>
> > -----Original Message-----
> > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> > owner@postgresql.org] On Behalf Of Qingqing Zhou
> > Sent: Tuesday, December 13, 2005 10:29 AM
> > To: Luke Lonergan
> > Cc: Tom Lane; Neil Conway; Bruce Momjian;
pgsql-hackers@postgresql.org
> > Subject: Re: [HACKERS] Which qsort is used
> >
> >
> >
> > On Mon, 12 Dec 2005, Luke Lonergan wrote:
> > >
> > > Might you have time to implement these within the testing
framework
> I
> > > published previously?  It has both the NetBSD and qsortG included
> along
> > with
> > > a timing routine, etc.
> > >
> >
> > Here we go:
> >
> > http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html
> >
> > The source tar ball and linux 2.4G gcc 2.96 test results is on the
> page.
> > There is a clear loser glibc, not sure qsortB or qsortG which is
> better.
> >
> > Regards,
> > Qingqing
> >
> > ---------------------------(end of
> broadcast)---------------------------
> > TIP 2: Don't 'kill -9' the postmaster