On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
kleptog@svana.org wrote:
But where are you including the cost to check how many cells are
already sorted? That would be O(H), right?
Yes. I didn't mention it, because H N.
This is where we come back
to the issue that comparisons in
: Tom Lane; Dann Corbit; Qingqing Zhou; Bruce Momjian; Luke
Lonergan;
Neil Conway; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Re: Which qsort is used
On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
kleptog@svana.org wrote:
But where are you including the cost to check how
On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane [EMAIL PROTECTED]
wrote:
I've still got a problem with these checks; I think they are a net
waste of cycles on average. [...]
and when they fail, those cycles are entirely wasted;
you have not advanced the state of the sort at all.
How can we make
On Thu, Dec 22, 2005 at 01:43:34AM +0100, Manfred Koizar wrote:
Qsorting N elements costs O(N*lnN), so excluding H elements from the
sort reduces the cost by at least O(H*lnN). The merge step costs O(N)
plus some (=50%) more memory, unless someone knows a fast in-place
merge. So depending on
On Fri, Dec 16, 2005 at 10:43:58PM -0800, Dann Corbit wrote:
I am actually quite impressed with the excellence of Bentley's sort out
of the box. It's definitely the best library implementation of a sort I
have seen.
I'm not sure whether we have a conclusion here, but I do have one
question:
Martin,
On 12/19/05 3:37 AM, Martijn van Oosterhout kleptog@svana.org wrote:
I'm not sure whether we have a conclusion here, but I do have one
question: is there a significant difference in the number of times the
comparison routines are called? Comparisons in PostgreSQL are fairly
expensive
Luke Lonergan wrote:
Tom,
On 12/12/05 2:47 PM, Tom Lane [EMAIL PROTECTED] wrote:
As those results suggest, there can be huge differences in sort
performance depending on whether the input is random, nearly sorted,
nearly reverse sorted, possesses many equal keys, etc. It would be very
On Fri, 16 Dec 2005, Bruce Momjian wrote:
At this point, I think we have done enough testing on enough platforms
to just use port/qsort on all platforms in 8.2. It seems whenever
someone tries to improve the BSD qsort, they make it worse.
Not necessariliy true. Dann Corbit sent me an
-Original Message-
From: [EMAIL PROTECTED] [mailto:pgsql-hackers-
[EMAIL PROTECTED] On Behalf Of Qingqing Zhou
Sent: Friday, December 16, 2005 5:14 PM
To: Bruce Momjian
Cc: Luke Lonergan; Tom Lane; Neil Conway; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Re: Which qsort
Dann Corbit [EMAIL PROTECTED] writes:
Both of them are modified versions of Bentley's sort algorithm.
Jon Bentley of Bell Labs? Small world ... he was my thesis adviser
for awhile when he was at CMU. He's a good algorithms man, for sure.
I just added the in-order check to both of them, and
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Friday, December 16, 2005 9:03 PM
To: Dann Corbit
Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
[EMAIL PROTECTED]
Subject: Re: [HACKERS] Re: Which qsort is used
Dann Corbit [EMAIL PROTECTED
On Sat, 17 Dec 2005, Dann Corbit wrote:
The benchmarks say that they (order checks) are a good idea on average
for ordered data, random data, and partly ordered data.
I interpret that in linux, 500 seems a divide for qsortpdq. Before
that number, it wins, after that, bsd wins more. On
-Original Message-
From: Qingqing Zhou [mailto:[EMAIL PROTECTED]
Sent: Friday, December 16, 2005 10:13 PM
To: Dann Corbit
Cc: Tom Lane; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
[EMAIL PROTECTED]
Subject: RE: [HACKERS] Re: Which qsort is used
On Sat, 17 Dec 2005, Dann
Dann Corbit [EMAIL PROTECTED] writes:
I've still got a problem with these checks; I think they are a net
waste of cycles on average.
The benchmarks say that they (order checks) are a good idea on average
for ordered data, random data, and partly ordered data.
There are lies, damn lies, and
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Friday, December 16, 2005 10:41 PM
To: Dann Corbit
Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
[EMAIL PROTECTED]
Subject: Re: [HACKERS] Re: Which qsort is used
Dann Corbit [EMAIL PROTECTED
15 matches
Mail list logo
