-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Thursday, December 15, 2005 6:24 PM
To: Dann Corbit
Cc: Qingqing Zhou; Greg Stark; Jim C. Nasby; Luke Lonergan; Neil
Conway;
Bruce Momjian; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used
Here's some results for a 2.5Ghz G5 and a 933Mhz G4
http://www.jefftrout.com/sort/
--
Jeff Trout [EMAIL PROTECTED]
http://www.jefftrout.com/
http://www.stuarthamm.net/
---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster
Luke Lonergan wrote:
Qingqing,
On 12/15/05 6:33 PM, Qingqing Zhou [EMAIL PROTECTED] wrote:
Thanks for Greg let me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy
On Thu, Dec 15, 2005 at 12:10:37AM -0500, Qingqing Zhou wrote:
On Wed, 14 Dec 2005, Luke Lonergan wrote:
Overall - I'd say that the BSD routine is showing the best overall results
when the scale test is included. The qsortG routine has some significantly
better performance in certain
On Thu, 15 Dec 2005, Jim C. Nasby wrote:
I have access to both some (SLOW) ultra5's and a machine running
opensolaris on AMD if testing there would help. I'll need a pointer to a
patch and test-case though...
Thanks! I've patched the program with the following changes:
(1) add gcc-mingw
Based on this it seems like we should expose the option to choose the BSD
qsort routine at configure time.
I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have
Greg Stark [EMAIL PROTECTED] writes:
I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have implementations that don't use function pointers.
There are calls to qsort in
On Thu, 15 Dec 2005, Greg Stark wrote:
I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have implementations that don't use function pointers. This
might perform faster
: [HACKERS] Which qsort is used
On Thu, 15 Dec 2005, Greg Stark wrote:
I have a related question. qsort is only used in the postgres source
in
a few
places. If postgres used an internal implementation instead of the
library
source it could have implementations that don't use function
Dann Corbit [EMAIL PROTECTED] writes:
Radix sort can also be made completely generic by using a callback
function.
The function gives back n-bits at a time, from the most significant bits
to the least significant.
That's mighty handwavy --- it assumes that the datatype permits a simple
[Face flushed begin]
Thanks for Greg let me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy now ...
[Face flushed continue]
After I re-tested it, now BSD qsort is
Qingqing,
On 12/15/05 6:33 PM, Qingqing Zhou [EMAIL PROTECTED] wrote:
Thanks for Greg let me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy now ...
After I
On Fri, 16 Dec 2005, Luke Lonergan wrote:
Can you post the new results like the last post?
Yeah, it is at the same website (I disabled Jim's result since he hasn't
updated using the new program).
Regards,
Qingqing
---(end of broadcast)---
Qingqing,
On 12/13/05 10:28 AM, Qingqing Zhou [EMAIL PROTECTED] wrote:
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.
Great stuff -
On Wed, 14 Dec 2005, Luke Lonergan wrote:
Overall - I'd say that the BSD routine is showing the best overall results
when the scale test is included. The qsortG routine has some significantly
better performance in certain cases at smaller sort set sizes - it could
probably be improved for
On 12/12/05, Bruce Momjian pgman@candle.pha.pa.us wrote:
Qingqing Zhou wrote:
Seems we don't link against the port/qsort.c - is there any reason for
that? My tests indicates our qsort is much much faster than the libc's.
Are you willing to say that we should always prefer pgport over
Marko Kreen [EMAIL PROTECTED] writes:
http://sourceware.org/ml/libc-alpha/2000-03/msg00139.html
Seems glibc guys once tested some implementation of quicksort vs. merge sort
and found out that
For small sets and smaller data types (arrays of ints and
arrays of doubles) mergesort is
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
-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
; 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
Dann Corbit [EMAIL PROTECTED] writes:
Here is a sort template (that can very easily be turned into a C
routine).
Right offhand I'd guess this to be a loser on not-quite-sorted input,
because the tests it makes to try to prove the input is already sorted
can add significant overhead before
The test is O(n)
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Tuesday, December 13, 2005 10:51 AM
To: Dann Corbit
Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
[EMAIL PROTECTED]
Subject: Re: [HACKERS] Which qsort is used
Dann Corbit
: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
[EMAIL PROTECTED]
Subject: Re: [HACKERS] Which qsort is used
The test is O(n)
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Tuesday, December 13, 2005 10:51 AM
To: Dann Corbit
Cc: Qingqing
On Tue, 13 Dec 2005, Dann Corbit wrote:
The test is designed especially for database systems, which are likely
to be clustered on data or index (and in the general case are sometimes
loaded in physically sorted order). In the clustered case, the only
time the data will not be ordered is
I will send you an ANSI C version.
-Original Message-
From: Qingqing Zhou [mailto:[EMAIL PROTECTED]
Sent: Tuesday, December 13, 2005 1:08 PM
To: Dann Corbit
Cc: Tom Lane; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
[EMAIL PROTECTED]
Subject: RE: [HACKERS] Which qsort is used
Dann Corbit [EMAIL PROTECTED] writes:
The in-order check happens only once
Hm? What about that call inside qloop's loop?
regards, tom lane
---(end of broadcast)---
TIP 6: explain analyze is your friend
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Tuesday, December 13, 2005 7:38 PM
To: Dann Corbit
Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
[EMAIL PROTECTED]
Subject: Re: [HACKERS] Which qsort is used
Dann Corbit [EMAIL PROTECTED
Seems we don't link against the port/qsort.c - is there any reason for
that? My tests indicates our qsort is much much faster than the libc's.
Regards,
Qingqing
---(end of broadcast)---
TIP 4: Have you searched our list archives?
Qingqing Zhou wrote:
Seems we don't link against the port/qsort.c - is there any reason for
that? My tests indicates our qsort is much much faster than the libc's.
We haven't been able to determine if the OS's qsort or pgport's is
faster. Right now we only force pgport qsort on Solaris (from
Bruce Momjian pgman@candle.pha.pa.us wrote
Are you willing to say that we should always prefer pgport over glibc's
qsort()?
At least for Linux and windows. My test is performed on a dataset ranges
from 10 to 1500 elements. Each elements contains a 64 bytes garbage
character area and an
On Mon, 2005-12-12 at 11:50 -0500, Bruce Momjian wrote:
Are you willing to say that we should always prefer pgport over glibc's
qsort()?
glibc's qsort is actually implemented via merge sort. I'm not sure why
the glibc folks chose to do that, but as a result, it's not surprising
that BSD qsort
On Mon, 12 Dec 2005, Neil Conway wrote:
Whether we should go to the trouble of second-guessing glibc is a
separate question, though: it would be good to see some performance
figures for real-world queries.
For qsort, due to its simple usage, I think simulation test should be
enough. But we
Neil Conway [EMAIL PROTECTED] writes:
BTW, Luke Lonergan recently posted some performance results for a fairly
efficient public domain implementation of qsort to the bizgres list:
http://lists.pgfoundry.org/pipermail/bizgres-general/2005-December/000294.html
As those results suggest, there can
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
dangerous to say
On Mon, 12 Dec 2005, Luke Lonergan wrote:
Do you have a test suite you can recommend with those edge cases?
I have at least those factors in mind:
+ f1: number of elements
- in {10^3, 10^4, 10^5, 10^6, 10^7}
+ f2: key comparators measured by cpu cost
- in {1, 10, 100+};
+ f3: data
Qingqing,
On 12/12/05 5:08 PM, Qingqing Zhou [EMAIL PROTECTED] wrote:
This will gives us a 5*3*4*4 = 240 tests ...
Looks good - I'm not going to be able to implement this matrix of tests
quickly, but each dimension seems right.
Might you have time to implement these within the testing
Tom,
IIRC, the reason we reject
Solaris' qsort is not that it is so bad in the typical case, but that it
has some horrible corner-case behaviors.
Sun claims to have fixed these. Hopefully they'll do some testing which will
prove it.
--
Josh Berkus
Aglio Database Solutions
San Francisco
37 matches
Mail list logo
