Re: [HACKERS] qsort, once again

2006-03-21 Thread Tom Lane
Greg Stark <[EMAIL PROTECTED]> writes: > My question explicitly recognized that possibility. I'm just a little > skeptical since the comparison function in Postgres is often not some simple > bit of tightly optimized C code, but rather a complex locale sensitive > comparison function or even a bit

Re: [HACKERS] qsort, once again

2006-03-21 Thread Greg Stark
Tom Lane <[EMAIL PROTECTED]> writes: > Greg Stark <[EMAIL PROTECTED]> writes: > > That looks better both on average and in the worst case. Are the time > > constants that much worse that the merge sort still takes longer? > > Keep in mind that this is only counting the number of > comparison-func

Re: [HACKERS] qsort, once again

2006-03-21 Thread Tom Lane
Greg Stark <[EMAIL PROTECTED]> writes: > That looks better both on average and in the worst case. Are the time > constants that much worse that the merge sort still takes longer? Keep in mind that this is only counting the number of comparison-function calls; it's not accounting for any other effe

Re: [HACKERS] qsort, once again

2006-03-21 Thread Greg Stark
Tom Lane <[EMAIL PROTECTED]> writes: > and here are the results using glibc's qsort, which of course isn't > quicksort at all but some kind of merge sort: > ... > Overall: average cratio 0.63 over 525 tests That looks better both on average and in the worst case. Are the time constants that much

Re: [HACKERS] qsort, once again

2006-03-21 Thread Tom Lane
"Dann Corbit" <[EMAIL PROTECTED]> writes: > Well, my point was that it is a snap to implement and test. Well, having done this, I have to eat my words: it does seem to be a pretty good idea. The following test numbers are using Bentley & McIlroy's test framework, but modified to test only the cas

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
Jonah H. Harris; pgsql-hackers@postgresql.org; Jerry Sievers > Subject: Re: [HACKERS] qsort, once again > > "Dann Corbit" <[EMAIL PROTECTED]> writes: > >> So my feeling is we should just remove the swap_cnt code and return > >> to the original B&M algor

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
"Dann Corbit" <[EMAIL PROTECTED]> writes: >> So my feeling is we should just remove the swap_cnt code and return >> to the original B&M algorithm. > Even if "hunks" of the input are sorted, the test is a very good idea. Yah know, guys, Bentley and McIlroy are each smarter than any five of us, and

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
> -Original Message- > From: [EMAIL PROTECTED] [mailto:pgsql-hackers- > [EMAIL PROTECTED] On Behalf Of Dann Corbit > Sent: Thursday, March 16, 2006 4:42 PM > To: Tom Lane > Cc: Jonah H. Harris; pgsql-hackers@postgresql.org; Jerry Sievers > Subject: Re: [HACKERS] qsort,

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
> So my feeling is we should just remove the swap_cnt code and return to > the original B&M algorithm. Being much faster than expected for > presorted input doesn't justify being far slower than expected for > other inputs, IMHO. In the context of Postgres I doubt that perfectly > sorted input sh

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
Darcy Buskermolen <[EMAIL PROTECTED]> writes: > On Thursday 16 March 2006 12:09, Tom Lane wrote: >> So we still have a problem of software archaeology: who added the >> insertion sort switch to the NetBSD version, and on what grounds? > This is when that particular code was pushed in, as to why ex

Re: [HACKERS] qsort, once again

2006-03-16 Thread Darcy Buskermolen
On Thursday 16 March 2006 12:09, Tom Lane wrote: > "Dann Corbit" <[EMAIL PROTECTED]> writes: > > I sent him a copy > > Thanks. This is really interesting: the switch to insertion sort on > perfect pivot is simply not there in Bentley & McIlroy's paper. So > it was added later, and evidently not

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
>> So at least on randomized data, the swap_cnt thing is a serious loser. >> Need to run some tests on special-case inputs though. Anyone have a >> test suite they like? > Here is a distribution maker that will create some torture tests for > sorting programs. I fleshed out the sort tester that

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
> -Original Message- > From: Dann Corbit > Sent: Thursday, March 16, 2006 1:31 PM > To: Dann Corbit; Tom Lane; Jonah H. Harris > Cc: pgsql-hackers@postgresql.org; Jerry Sievers > Subject: RE: [HACKERS] qsort, once again > > Actually, if you compile with CREATE_DISTRIBS defined,

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
PM > To: Tom Lane; Jonah H. Harris > Cc: pgsql-hackers@postgresql.org; Jerry Sievers > Subject: Re: [HACKERS] qsort, once again > > [snip] > > So at least on randomized data, the swap_cnt thing is a serious loser. > > Need to run some tests on special-case inputs though.

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
[snip] > So at least on randomized data, the swap_cnt thing is a serious loser. > Need to run some tests on special-case inputs though. Anyone have a > test suite they like? > > regards, tom lane Here is a distribution maker that will create some torture tests for sorting p

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
"Jonah H. Harris" <[EMAIL PROTECTED]> writes: > On 3/16/06, Tom Lane <[EMAIL PROTECTED]> wrote: >> So we still have a problem of software archaeology: who added the >> insertion sort switch to the NetBSD version, and on what grounds? > AFAICS, the insertion sort was added in BSD 4.4-lite and was i

Re: [HACKERS] qsort, once again

2006-03-16 Thread Jonah H. Harris
On 3/16/06, Tom Lane <[EMAIL PROTECTED]> wrote: So we still have a problem of software archaeology: who added theinsertion sort switch to the NetBSD version, and on what grounds? AFAICS, the insertion sort was added in BSD 4.4-lite and was inherited by NetBSD in CVS version 1.1.1.2. The previous

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
ackers@postgresql.org; Jerry Sievers > Subject: Re: [HACKERS] qsort, once again > > "Dann Corbit" <[EMAIL PROTECTED]> writes: > > I sent him a copy > > Thanks. This is really interesting: the switch to insertion sort on > perfect pivot is simply not there in

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
"Dann Corbit" <[EMAIL PROTECTED]> writes: > I sent him a copy Thanks. This is really interesting: the switch to insertion sort on perfect pivot is simply not there in Bentley & McIlroy's paper. So it was added later, and evidently not tested as carefully as it should have been. At this point I

Re: [HACKERS] qsort, once again

2006-03-16 Thread Jonah H. Harris
On 3/16/06, Tom Lane <[EMAIL PROTECTED]> wrote: "Jonah H. Harris" <[EMAIL PROTECTED]> writes:> doh! Sorry for the duplicate (again) Tom...  I wish Gmail would auto-reply to all.  grr.  Anyway, this is copied for others and the archives: There's a program I had used in the past to test qsort imple

Re: [HACKERS] qsort, once again

2006-03-16 Thread Tom Lane
"Jonah H. Harris" <[EMAIL PROTECTED]> writes: > doh! > On 3/16/06, Dann Corbit <[EMAIL PROTECTED]> wrote: >> I sent him a copy Got it, thanks guys ... regards, tom lane ---(end of broadcast)--- TIP 4: Have you searched our

Re: [HACKERS] qsort, once again

2006-03-16 Thread Jonah H. Harris
ubject: Re: [HACKERS] qsort, once again   On 3/16/06, Tom Lane < [EMAIL PROTECTED]> wrote: I'm wondering what the authors were expecting the insertion sort to handle exactly.  Does anyone have a copy of the paper that's referenced in the code comment? /* * Qsort routine fr

Re: [HACKERS] qsort, once again

2006-03-16 Thread Dann Corbit
I sent him  a copy   From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Jonah H. Harris Sent: Thursday, March 16, 2006 11:43 AM To: Tom Lane Cc: pgsql-hackers@postgresql.org; Jerry Sievers Subject: Re: [HACKERS] qsort, once again   On 3/16/06, Tom Lane <[EM

Re: [HACKERS] qsort, once again

2006-03-16 Thread Jonah H. Harris
On 3/16/06, Tom Lane <[EMAIL PROTECTED]> wrote: I'm wondering what the authors were expecting the insertion sort tohandle exactly.  Does anyone have a copy of the paper that's referencedin the code comment?/* * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". */ Yes, I have it