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
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
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
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
"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
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
"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
> -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,
> 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
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
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
>> 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
> -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,
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.
[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
"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
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
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
"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
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
"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
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
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
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
24 matches
Mail list logo