Thread: Which qsort is used
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
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 configure.in): # Solaris has a very slow qsort in certain cases, so we replace it.if test "$PORTNAME" = "solaris"; thenAC_LIBOBJ(qsort)fi Are you willing to say that we should always prefer pgport over glibc's qsort()? -- Bruce Momjian | http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001+ If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square, Pennsylvania19073
"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 15000000 elements. Each elements contains a 64 bytes garbage character area and an integer key, which is uniformly distributed from 1 to RANGE. RANGE takes values from 2 to 2^31. In all cases, our qsort absolutely wins. Maybe skewed distribution should be tested? Another interesting thing is that the qsort on RANGE=2 or other small number in windows is terriblly slow - our version does not have this problem. The test code could be found here (Note: it mixed with some other experiements I am doing but might be a good start point to construct your own tests): http://www.cs.toronto.edu/~zhouqq/sort.c Regards, Qingqing
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 beats it for typical inputs. 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. 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 -Neil
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 have to consider many situations like cardinality, data distribution etc. Maybe not easy to find real world queries providing so many variations. > 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 > Ooops, more interesting than the thread itself ;-) Regards, Qingqing
Neil Conway <neilc@samurai.com> 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 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 "implementation A is better than implementation B" without having tested all those scenarios. 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. regards, tom lane
Tom, On 12/12/05 2:47 PM, "Tom Lane" <tgl@sss.pgh.pa.us> 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 "implementation A is better than implementation B" > without having tested all those scenarios. Yes. The Linux glibc qsort is proven terrible in the general case by these examples though. Bruce's point on that thread was that we shouldn't be replacing the OS routine in the general case. On the other hand, there is the precedent of replacing Solaris' routine with the NetBSD version. Based on the current testing, I think it would be a good idea to expose a "--with-qsort" option in configure to allow for it's selection as suggested by other posters. > 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. Do you have a test suite you can recommend with those edge cases? I built the one in the bizgres-general thread based on edge cases for Solaris that I found on a sun mailing list. The edge case referred to there was the all zero one, which does seem to have a significant advantage in the NetBSD. - Luke
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 distribution - in {uniform, Gussian, 95% sorted, 95% reverse sorted}
+ f4: data value range - in {2, 32, 1024, unlimited}: radix sort might be better for small
range
The element size doesn't matter since the main usage of our qsort is
on pointer array. Element data type is covered by f2 and f4.
This will gives us a 5*3*4*4 = 240 tests ...
Regards,
Qingqing
Qingqing, On 12/12/05 5:08 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> 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 framework I published previously? It has both the NetBSD and qsortG included along with a timing routine, etc. BTW - the edge case reported to the Sun mailing list was here: http://forum.sun.com/thread.jspa?forumID=4&threadID=7231 - Luke
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
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 glibc's > qsort()? I searched the archives and found this: 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 definitly faster and behavesbetter." If the qsort in Postgres is called usually on wide data - on full rows not on pointers to rows, then indeed it would be wise to use out own sort. Especially considering that qsort is not anything OS or machine -specific, better algorithm beats assembly-optimizations. If we have a very good good implementation we could use it everywhere. OTOH, someone should notify glibc devs that their qsort is mediocre, I don't see much activity on the lists around around that topic. -- marko
Marko Kreen <markokr@gmail.com> 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 definitly faster and behaves better." > If the qsort in Postgres is called usually on wide data - on full rows > not on pointers to rows, then indeed it would be wise to use out own > sort. But I can assure you that it is never called on any such thing. Since qsort only works on fixed-size items, it'd be essentially impossible to use it directly on rows; we *always* use it on pointers instead. (We could only do the other if we had a separate code path for rows containing only fixed-width-never-null columns, which we do not, and it'd be pretty silly to add one in view of the increased data-copying work that would result.) The referenced message is pretty interesting for this discussion, particularly its pointer to someone's sort test routines --- wonder if those are still available? It was also eye-opening to read that glibc actually contains two separate algorithms to use depending on the size of the target array. If that's still true then it throws a lot of the testing so far into doubt. regards, tom lane
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
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 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: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers- > owner@postgresql.org] 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
Attachment
Strike "switches to qsort" insert "switches to heapsort"
> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] 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: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> > owner@postgresql.org] 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
"Dann Corbit" <DCorbit@connx.com> 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 failing.
regards, tom lane
The test is O(n) > -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Tuesday, December 13, 2005 10:51 AM > To: Dann Corbit > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > hackers@postgresql.org > Subject: Re: [HACKERS] Which qsort is used > > "Dann Corbit" <DCorbit@connx.com> 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 failing. > > regards, tom lane
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 when there has been a page split and the statistics have not been updated. The in-order check happens only once and there will not be a significant performance hit for removal (except that it will be absurdly fast when the data is already ordered or in reverse order if left as-is.) Ordered and reverse-ordered are two cases where qsort goes quadratic (without a test). Of course, introspective sort does not suffer from this defect, even with the test removed. > -----Original Message----- > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers- > owner@postgresql.org] On Behalf Of Dann Corbit > Sent: Tuesday, December 13, 2005 11:53 AM > To: Tom Lane > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > hackers@postgresql.org > Subject: Re: [HACKERS] Which qsort is used > > The test is O(n) > > > -----Original Message----- > > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > > Sent: Tuesday, December 13, 2005 10:51 AM > > To: Dann Corbit > > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > > hackers@postgresql.org > > Subject: Re: [HACKERS] Which qsort is used > > > > "Dann Corbit" <DCorbit@connx.com> 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 failing. > > > > regards, tom lane > > ---------------------------(end of broadcast)--------------------------- > TIP 9: In versions below 8.0, the planner will ignore your desire to > choose an index scan if your joining column's datatypes do not > match
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 when there has been a page split > and the statistics have not been updated. > > The in-order check happens only once and there will not be a significant > performance hit for removal (except that it will be absurdly fast when > the data is already ordered or in reverse order if left as-is.) > > Ordered and reverse-ordered are two cases where qsort goes quadratic > (without a test). Of course, introspective sort does not suffer from > this defect, even with the test removed. > Yeah, I would think O(n) in-order check doesn't matter for random data set. For nearly-ordered set, may be not true. I am not good at C++, so can you patch the test program with your sort method and the page-split-data generator? I would be happy to give it a test. Regards, Qingqing
I will send you an ANSI C version. > -----Original Message----- > From: Qingqing Zhou [mailto:zhouqq@cs.toronto.edu] > Sent: Tuesday, December 13, 2005 1:08 PM > To: Dann Corbit > Cc: Tom Lane; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > hackers@postgresql.org > Subject: RE: [HACKERS] Which qsort is used > > > > 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 when there has been a page split > > and the statistics have not been updated. > > > > The in-order check happens only once and there will not be a significant > > performance hit for removal (except that it will be absurdly fast when > > the data is already ordered or in reverse order if left as-is.) > > > > Ordered and reverse-ordered are two cases where qsort goes quadratic > > (without a test). Of course, introspective sort does not suffer from > > this defect, even with the test removed. > > > > Yeah, I would think O(n) in-order check doesn't matter for random data > set. For nearly-ordered set, may be not true. I am not good at C++, so can > you patch the test program with your sort method and the page-split-data > generator? I would be happy to give it a test. > > Regards, > Qingqing
"Dann Corbit" <DCorbit@connx.com> writes:
> The in-order check happens only once
Hm? What about that call inside qloop's loop?
regards, tom lane
> -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Tuesday, December 13, 2005 7:38 PM > To: Dann Corbit > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > hackers@postgresql.org > Subject: Re: [HACKERS] Which qsort is used > > "Dann Corbit" <DCorbit@connx.com> writes: > > The in-order check happens only once > > Hm? What about that call inside qloop's loop? You're right. Once per partition of size 50 or greater. In my tests, it was a clear win. We'll see in the Qingqing Zhou test setup if it helps or not. If there is some order to the data, it will be of benefit. For purely random samples, there will be a small fixed cost.
Qingqing, On 12/13/05 10:28 AM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> 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 - thanks for doing this. From the results, it's clear that the scale test makes a huge difference in the relative performance. I'm wondering if it's an L2 cache effect, as it seems to occur in that range. 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 better L2 use, but BSD is already there. Based on this it seems like we should expose the option to choose the BSD qsort routine at configure time. - Luke
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 better L2 use, but BSD is already there. > > Based on this it seems like we should expose the option to choose the BSD > qsort routine at configure time. > Before we pin down this, I hope more extensive tests on various platforms could be done. So we could give some suggestions when we should enable the "--enable-bsdqsort" option. I can post a result on a SunOS machine (but the problem is that many ppl share this machine) and a windows machine. Regards, Qingqing
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 cases at smaller sort set sizes - it could > > probably be improved for better L2 use, but BSD is already there. > > > > Based on this it seems like we should expose the option to choose the BSD > > qsort routine at configure time. > > > > Before we pin down this, I hope more extensive tests on various platforms > could be done. So we could give some suggestions when we should enable the > "--enable-bsdqsort" option. I can post a result on a SunOS machine (but > the problem is that many ppl share this machine) and a windows machine. 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... Oh, I also have access to an old SGI... -- Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com Pervasive Software http://pervasive.com work: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461
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 support; (2) move the check_sort() out of do_sort() - the previous program is actually measuring the time of qsort plus result verification. Though that one "fairly" add equal cost to every competitor, which will not affect the confidence of the result, it is a defeat, sorry about that; The new results with SunOS and Windows tests are published at the same place: http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html As Luke suggested, BSD seems a good choice for scalable and stable consideration. But I also sent an email to the author of qsortG, and he might take a look at the small-range performance problem during the holiday. So if he can help that, then we will have another candidate. By the way, I do spend some time on fighting the win32 gettimeofday() emulation. I would suggest adding a comment like "don't use this method in windows to get high precision time, use elapsed_time() instead" ... Regards, Qingqing
> > > 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 implementations that don't use function pointers. This might perform faster for a few reasons. The comparator is much more likely to be eligible for inlining for one. It also opens the door to using different sort algorithms for different applications. There may be some cases where the input is never sorted and the sample size is small so qsort is a good choice, and others where the inputs can be large and using a better algorithm with worse overhead like mergesort might make more sense. Unfortunately there isn't just a single qsort call though. I count 6 comparators in the source tree I have. So perhaps this is a non-starter. Having 6 qsort implementations around sounds pretty sketchy. -- greg
Greg Stark <gsstark@mit.edu> 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 upwards of 40 different source files; many
of those files contain multiple comparator functions. Doesn't look like
"a few" to me. But I'll grant that the vast majority are not
performance critical. One could imagine putting a custom implementation
into only tuplesort.c, say, where you could certainly get rid of one
level of function call (qsort_comparetup) by providing a saner API that
passes a state pointer as well as a function pointer to the qsort code.
Whether that would be worth the trouble is a question for experiment ...
regards, tom lane
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 for a few reasons. The comparator is much more likely to > be eligible for inlining for one. > > It also opens the door to using different sort algorithms for different > applications. There may be some cases where the input is never sorted and the > sample size is small so qsort is a good choice, and others where the inputs > can be large and using a better algorithm with worse overhead like mergesort > might make more sense. > > Unfortunately there isn't just a single qsort call though. I count 6 > comparators in the source tree I have. So perhaps this is a non-starter. > Having 6 qsort implementations around sounds pretty sketchy. > [also with reply to Tom] Both ideas look like doable (or at least testable) for me. I agree that the only interesting pot is in tuplesort.c. For the 2nd idea, for smaller range, we may consider radix sort, which is definitely faster - but this may need some work that enable query optimizer know the *exact* data range. Regards, Qingqing
> -----Original Message----- > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers- > owner@postgresql.org] On Behalf Of Qingqing Zhou > Sent: Thursday, December 15, 2005 3:16 PM > To: Greg Stark > Cc: Jim C. Nasby; Luke Lonergan; Tom Lane; Neil Conway; Bruce Momjian; > pgsql-hackers@postgresql.org > Subject: Re: [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 pointers. > This > > might perform faster for a few reasons. The comparator is much more > likely to > > be eligible for inlining for one. > > > > It also opens the door to using different sort algorithms for different > > applications. There may be some cases where the input is never sorted > and the > > sample size is small so qsort is a good choice, and others where the > inputs > > can be large and using a better algorithm with worse overhead like > mergesort > > might make more sense. > > > > Unfortunately there isn't just a single qsort call though. I count 6 > > comparators in the source tree I have. So perhaps this is a non-starter. > > Having 6 qsort implementations around sounds pretty sketchy. > > > > [also with reply to Tom] Both ideas look like doable (or at least > testable) for me. I agree that the only interesting pot is in tuplesort.c. > For the 2nd idea, for smaller range, we may consider radix sort, which is > definitely faster - but this may need some work that enable query > optimizer know the *exact* data range. 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. So, for char string, and a radix of 256, you just return the first char, then the second char, etc. to get the classical radix sort. Radix sort is no advantage for long, similar strings. Suppose that you have a comparison sort that is O(n*log(n)). If n is one billion items, then log2(n) is 32 and therefore LSD radix 256 sorts of 33 character fields will be slower than a comparison sort, even for one billion items.
"Dann Corbit" <DCorbit@connx.com> 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
breakdown into small pieces that can be sorted lexicographically. Seems
to me that's a much stronger requirement than assuming that you can tell
which of two whole values is smaller. What's worse, it needs to be the
same number of pieces for every value, which makes it hard to deal with
variable-length data.
> So, for char string, and a radix of 256, you just return the first char,
> then the second char, etc. to get the classical radix sort.
Uh, no, you'd need to work right-to-left, after having padded all the
strings to the same length somehow.
regards, tom lane
[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 the obvious winner in most situations. [Face flushed end] Regards, Qingqing
Qingqing, On 12/15/05 6:33 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> 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 re-tested it, now BSD qsort is the obvious winner in most > situations. :-D Can you post the new results like the last post? - Luke
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
> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> 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
>
> "Dann Corbit" <DCorbit@connx.com> 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
> breakdown into small pieces that can be sorted lexicographically.
It's not so hard. For fixed length character strings, the mapping is
just the character. For integers the mapping is obvious [msb to lsb or
lsb to msb of the integer, depending on whether you are doing msd or lsd
radix sort]. For intel floating point, the transformation is:
#include <assert.h>
#include "inteltyp.h"
uint32
float2key(float f)
{ uint32 sign, mant, mask;
assert(sizeof(float) == sizeof(uint32)); mant = *(uint32 *) & f; /* Load float as array of bits */ sign =
mant& SB_MASK32; /* Isolate the leading sign bit */ mant ^= SB_MASK32; /* Invert the sign bit, making + >
-*/ mask = sign - (sign >> 31); /* Either 0 or 0x7fffffff */ mant ^= mask; /* Invert exp and mant if
negative*/ return mant;
}
uint64
double2key(double d)
{ uint64 sign, mant, mask;
assert(sizeof(double) == sizeof(uint64)); mant = *(uint64 *) & d; /* Load float as array of bits */ sign =
mant& SB_MASK64; /* Isolate the leading sign bit */ mant ^= SB_MASK64; /* Invert the sign bit, making + >
-*/ mask = sign - (sign >> 63); /* Either 0 or 0x7fffffffffffffff */ mant ^= mask; /* Invert exp and
mantif negative */ return mant;
}
Where the contents of inteltyp.h are as follows:
/*
** Typdefs for Intel formats.
** See keyxfrm.c for usage.
*/
typedef unsigned long uint32;
#define SB_MASK32 0x80000000UL
#ifdef _MSC_VER
typedef unsigned __int64 uint64;
typedef __int64 sint64;
#define SB_MASK64 0x8000000000000000ui64
#else
typedef unsigned long long uint64;
typedef long long sint64;
#define SB_MASK64 0x8000000000000000ULL
#endif
extern uint32 float2key(float f);
uint64 double2key(double d);
=======================================================
After the above transformation, you just use the same buckets as for
integers.
In general, the creation of the mapping function is no more difficult
than the creation of a comparison function.
> Seems
> to me that's a much stronger requirement than assuming that you can
tell
> which of two whole values is smaller. What's worse, it needs to be
the
> same number of pieces for every value, which makes it hard to deal
with
> variable-length data.
No. The number of pieces is irrelevant. And you can use MSD radix sort
for variable length data.
> > So, for char string, and a radix of 256, you just return the first
char,
> > then the second char, etc. to get the classical radix sort.
>
> Uh, no, you'd need to work right-to-left, after having padded all the
> strings to the same length somehow.
Unless you use MSD radix sort (which is usually better anyway).
> regards, tom lane
Here's some results for a 2.5Ghz G5 and a 933Mhz G4 http://www.jefftrout.com/sort/ -- Jeff Trout <jeff@jefftrout.com> http://www.jefftrout.com/ http://www.stuarthamm.net/
Luke Lonergan wrote: > Tom, > > On 12/12/05 2:47 PM, "Tom Lane" <tgl@sss.pgh.pa.us> 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 "implementation A is better than implementation B" > > without having tested all those scenarios. > > Yes. The Linux glibc qsort is proven terrible in the general case by these > examples though. > > Bruce's point on that thread was that we shouldn't be replacing the OS > routine in the general case. On the other hand, there is the precedent of > replacing Solaris' routine with the NetBSD version. 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. Were the BSD programmers geniuses and we are all idiots now, or what? -- Bruce Momjian | http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001+ If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square, Pennsylvania19073
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 implementation a while ago (you can see it on the same site). BSD qsort is improved, though not that much, by two methods. Since Dann write the program from scratch, so I am not sure if we are afford to take the efforts for the improvement. Regards, Qingqing
> -----Original Message----- > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers- > owner@postgresql.org] 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 is used > > 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 implementation a while ago > (you can see it on the same site). BSD qsort is improved, though not that > much, by two methods. Since Dann write the program from scratch, so I am > not sure if we are afford to take the efforts for the improvement. Both of them are modified versions of Bentley's sort algorithm. I just added the in-order check to both of them, and the reversed partition check for the second method (in the case of the subfiles because insertion sort is allergic to reversed partitions). At any rate, neither is much of an improvement on Bentley's version. For the rare cases of completely ordered or completely reversed, it will be a monumental improvement. But that is a pretty rare case. If I could use C++, I could do much better. It is very difficult for me to write an ADT in C instead of in C++.
Luke Lonergan wrote: > Qingqing, > > > On 12/15/05 6:33 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> 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 re-tested it, now BSD qsort is the obvious winner in most >>situations. > > > :-D > > Can you post the new results like the last post? > > - Luke > Here is a result from a dual 0.8G x86 running Freebsd 6.0-RELEASE: http://homepages.paradise.net.nz/markir/download/sort-fbsd.out (after patching the bug with qsortB calling qsort). Clearly in this case, there is no glibc version, hence I've relabeled the 1st case as "native qsort". Cheers Mark
"Dann Corbit" <DCorbit@connx.com> 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 the reversed
> partition check for the second method (in the case of the subfiles
> because insertion sort is allergic to reversed partitions).
I've still got a problem with these checks; I think they are a net
waste of cycles on average. They would only be a win if you expected a
nontrivial percentage of perfectly-in-order or perfectly-reverse-order
inputs. What I think is much more probable in the Postgres environment
is almost-but-not-quite-ordered inputs --- eg, a table that was
perfectly ordered by key when filled, but some of the tuples have since
been moved by UPDATEs. This is the worst possible case for the in-order
checks, because they can then grovel over large percentages of the file
before failing ... and when they fail, those cycles are entirely wasted;
you have not advanced the state of the sort at all.
For the "usual" case of randomly ordered input, of course it doesn't
matter much at all because the in-order checks will fail after examining
not too many items. But to argue that the checks are worth making, you
have to assume that perfectly-ordered inputs are more common than
almost-ordered inputs, and I think that is exactly the wrong assumption
for the Postgres environment. I sure haven't seen any evidence that
it's a good assumption.
regards, tom lane
> -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Friday, December 16, 2005 9:03 PM > To: Dann Corbit > Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- > hackers@postgresql.org > Subject: Re: [HACKERS] Re: Which qsort is used > > "Dann Corbit" <DCorbit@connx.com> 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 the reversed > > partition check for the second method (in the case of the subfiles > > because insertion sort is allergic to reversed partitions). > > I've still got a problem with these checks; I think they are a net > waste of cycles on average. They would only be a win if you expected a > nontrivial percentage of perfectly-in-order or perfectly-reverse-order > inputs. What I think is much more probable in the Postgres environment > is almost-but-not-quite-ordered inputs --- eg, a table that was > perfectly ordered by key when filled, but some of the tuples have since > been moved by UPDATEs. This is the worst possible case for the in-order > checks, because they can then grovel over large percentages of the file > before failing ... and when they fail, those cycles are entirely wasted; > you have not advanced the state of the sort at all. > > For the "usual" case of randomly ordered input, of course it doesn't > matter much at all because the in-order checks will fail after examining > not too many items. But to argue that the checks are worth making, you > have to assume that perfectly-ordered inputs are more common than > almost-ordered inputs, and I think that is exactly the wrong assumption > for the Postgres environment. I sure haven't seen any evidence that > it's a good assumption. The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. It does not require perfectly ordered data for the checks to be useful. On mostly ordered data, it is likely that some partitions are perfectly ordered. If you trace the algorithms in a debugger you will be surprised at how often the partitions are ordered, even with random sets as input.
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, 5000000 seems a divide for qsortpdq. Before that number, it wins, after that, bsd wins more. On SunOS, qsortpdq takes the lead till the last second -- I suspect this is due to the rand() function: Linux - #define RAND_MAX 2147483647SunOS - #define RAND_MAX 32767 So in SunOS, the data actually not that scattered - so more favourate for sorted() or reversed() check? Regards, Qingqing
> -----Original Message----- > From: Qingqing Zhou [mailto:zhouqq@cs.toronto.edu] > Sent: Friday, December 16, 2005 10:13 PM > To: Dann Corbit > Cc: Tom Lane; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- > hackers@postgresql.org > Subject: RE: [HACKERS] Re: Which qsort is used > > > > 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, 5000000 seems a divide for qsortpdq. Before > that number, it wins, after that, bsd wins more. On SunOS, qsortpdq takes > the lead till the last second -- I suspect this is due to the rand() > function: > > Linux - #define RAND_MAX 2147483647 > SunOS - #define RAND_MAX 32767 > > So in SunOS, the data actually not that scattered - so more favourate for > sorted() or reversed() check? There is a lot of variability from system to system even for the same tests. I see different results depending on whether I use GCC or Intel or MS compilers.
"Dann Corbit" <DCorbit@connx.com> 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 benchmarks ;-)
The problem with citing a benchmark for this discussion is that a
benchmark can't tell you anything about real-world probabilities;
it only tells you about the probabilities occuring in the benchmark
case. You need to make the case that the benchmark reflects the
real world, which you didn't.
> If you trace the algorithms in a debugger you will be surprised at how
> often the partitions are ordered, even with random sets as input.
Well, I do agree that checking for orderedness on small partitions would
succeed more often than on larger partitions or the whole file --- but
the code-as-given checks all the way down. Moreover, the argument given
for spending these cycles is that insertion sort sucks on reverse-order
input ... where "sucks" means that it spends O(N^2) time. But it spends
O(N^2) in the average case, too.
regards, tom lane
> -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Friday, December 16, 2005 10:41 PM > To: Dann Corbit > Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- > hackers@postgresql.org > Subject: Re: [HACKERS] Re: Which qsort is used > > "Dann Corbit" <DCorbit@connx.com> 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 benchmarks ;-) > > The problem with citing a benchmark for this discussion is that a > benchmark can't tell you anything about real-world probabilities; > it only tells you about the probabilities occuring in the benchmark > case. You need to make the case that the benchmark reflects the > real world, which you didn't. > > > If you trace the algorithms in a debugger you will be surprised at how > > often the partitions are ordered, even with random sets as input. > > Well, I do agree that checking for orderedness on small partitions would > succeed more often than on larger partitions or the whole file --- but > the code-as-given checks all the way down. Moreover, the argument given > for spending these cycles is that insertion sort sucks on reverse-order > input ... where "sucks" means that it spends O(N^2) time. But it spends > O(N^2) in the average case, too. I agree that in general these checks are not important and they complicate what is a simple and elegant algorithm. The cases where the checks are important (highly ordered data sets) are rare and so the value added is minimal. 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.
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: is there a significant difference in the number of times the comparison routines are called? Comparisons in PostgreSQL are fairly expensive given the fmgr overhead and when comparing tuples it's even worse. We don't want to accedently pick a routine that saves data shuffling by adding extra comparisons. The stats at [1] don't say. They try to factor in CPU cost but they seem to use unrealistically small values. I would think a number around 50 (or higher) would be more representative. [1] http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a > tool for doing 5% of the work and then sitting around waiting for someone > else to do the other 95% so you can sue them.
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 given the fmgr overhead and when comparing tuples it's even > worse. It would be interesting to note the comparison count of the different routines. Something that really grabbed me about the results though is that the relative performance of the routines dramatically shifted when the indirect references in the comparators went in. The first test I did sorted an array of int4 - these tests that Qingqing did sorted arrays using an indirect pointer list, at which point the same distributions performed very differently. I suspect that it is the number of comparisons that caused this, and further that the indirection has disabled the compiler optimizations for memory prefetch and other things that it could normally recognize. Given the usage pattern in Postgres, where sorted things are a mix of strings and intrinsic types, I'm not sure those optimizations could be done by one routine. I haven't verified this, but it certainly seems that the NetBSD routine is the overall winner for the type of use that Postgres has (sorting the using a pointer list). - Luke
On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <tgl@sss.pgh.pa.us> 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 the initial check "adavance the state of the sort"? One answer might be to exclude the sorted sequence at the start of the array from the qsort, and merge the two sorted lists as the final stage of the sort. 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 the constant factors involved there might be a usable solution. I've been playing with some numbers and assuming the constant factors to be equal for all the O()'s this method starts to pay off at H for N 20 100 130 10008000 100000 ServusManfred
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 the constant factors involved there might be a > usable solution. But where are you including the cost to check how many cells are already sorted? That would be O(H), right? This is where we come back to the issue that comparisons in PostgreSQL are expensive. The cpu_cost in the tests I saw so far is unrealistically low. > I've been playing with some numbers and assuming the constant factors > to be equal for all the O()'s this method starts to pay off at > H for N > 20 100 20% > 130 1000 13% > 8000 100000 8% Hmm, what are the chances you have 100000 unordered items to sort and that the first 8% will already be in order. ISTM that that probability will be close enough to zero to not matter... Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a > tool for doing 5% of the work and then sitting around waiting for someone > else to do the other 95% so you can sue them.
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 PostgreSQL are expensive. So we agree that we should try to reduce the number of comparisons. How many comparisons does it take to sort 100000 items? 1.5 million? >Hmm, what are the chances you have 100000 unordered items to sort and >that the first 8% will already be in order. ISTM that that probability >will be close enough to zero to not matter... If the items are totally unordered, the check is so cheap you won't even notice. OTOH in Tom's example ... |What I think is much more probable in the Postgres environment |is almost-but-not-quite-ordered inputs --- eg, a table that was |perfectly ordered by key when filled, but some of the tuples have since |been moved by UPDATEs. ... I'd not be surprised if H is 90% of N. ServusManfred
An interesting article on sorting and comparison count: http://www.acm.org/jea/ARTICLES/Vol7Nbr5.pdf Here is the article, the code, and an implementation that I have been toying with: http://cap.connx.com/chess-engines/new-approach/algos.zip Algorithm quickheap is especially interesting because it does not require much additional space (just an array of integers up to size log(element_count) and in addition, it has very few data movements. > -----Original Message----- > From: Manfred Koizar [mailto:mkoi-pg@aon.at] > Sent: Thursday, December 22, 2005 1:59 PM > To: Martijn van Oosterhout > Cc: 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 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 PostgreSQL are expensive. > > So we agree that we should try to reduce the number of comparisons. > How many comparisons does it take to sort 100000 items? 1.5 million? > > >Hmm, what are the chances you have 100000 unordered items to sort and > >that the first 8% will already be in order. ISTM that that probability > >will be close enough to zero to not matter... > > If the items are totally unordered, the check is so cheap you won't > even notice. OTOH in Tom's example ... > > |What I think is much more probable in the Postgres environment > |is almost-but-not-quite-ordered inputs --- eg, a table that was > |perfectly ordered by key when filled, but some of the tuples have since > |been moved by UPDATEs. > > ... I'd not be surprised if H is 90% of N. > Servus > Manfred