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"; then
AC_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(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

"Bruce Momjian" <pgman(at)candle(dot)pha(dot)pa(dot)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(at)samurai(dot)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(at)sss(dot)pgh(dot)pa(dot)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(at)cs(dot)toronto(dot)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(at)candle(dot)pha(dot)pa(dot)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 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. 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(at)gmail(dot)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

Qingqing,

On 12/13/05 10:28 AM, "Qingqing Zhou" <zhouqq(at)cs(dot)toronto(dot)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(at)pervasive(dot)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(at)mit(dot)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

[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(at)cs(dot)toronto(dot)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

Luke Lonergan wrote:
> Tom,
>
> On 12/12/05 2:47 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)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(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

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

Luke Lonergan wrote:
> Qingqing,
>
>
> On 12/15/05 6:33 PM, "Qingqing Zhou" <zhouqq(at)cs(dot)toronto(dot)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