Strike "switches to qsort" insert "switches to heapsort"
> -----Original Message----- > From: [EMAIL PROTECTED] [mailto:pgsql-hackers- > [EMAIL PROTECTED] 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: [EMAIL PROTECTED] [mailto:pgsql-hackers- > > [EMAIL PROTECTED] 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 ---------------------------(end of broadcast)--------------------------- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
