pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: qsort again
4+ messages / 4 participants
[nested] [flat]
* Re: qsort again
@ 2006-02-16 12:10 Florian Weimer <fw@deneb.enyo.de>
2006-02-16 12:49 ` Re: qsort again Martijn van Oosterhout <kleptog@svana.org>
2006-02-16 13:38 ` Re: [PERFORM] qsort again Ron <rjpeace@earthlink.net>
0 siblings, 2 replies; 4+ messages in thread
From: Florian Weimer @ 2006-02-16 12:10 UTC (permalink / raw)
To: Neil Conway <neilc@samurai.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Gary Doades <gpd@gpdnet.co.uk>; pgsql-performance; pgsql-hackers@postgresql.org
* Neil Conway:
> On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
>> It seems clear that our qsort.c is doing a pretty awful job of picking
>> qsort pivots, while glibc is mostly managing not to make that mistake.
>> I haven't looked at the glibc code yet to see what they are doing
>> differently.
>
> glibc qsort is actually merge sort, so I'm not surprised it avoids this
> problem.
qsort also performs twice as many key comparisons as the theoretical
minimum. If key comparison is not very cheap, other schemes (like
heapsort, for example) are more attractive.
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: qsort again
2006-02-16 12:10 Re: qsort again Florian Weimer <fw@deneb.enyo.de>
@ 2006-02-16 12:49 ` Martijn van Oosterhout <kleptog@svana.org>
2006-02-16 13:08 ` Re: [PERFORM] qsort again Sven Geisler <sgeisler@aeccom.com>
1 sibling, 1 reply; 4+ messages in thread
From: Martijn van Oosterhout @ 2006-02-16 12:49 UTC (permalink / raw)
To: Florian Weimer <fw@deneb.enyo.de>; +Cc: Neil Conway <neilc@samurai.com>; Tom Lane <tgl@sss.pgh.pa.us>; Gary Doades <gpd@gpdnet.co.uk>; pgsql-performance; pgsql-hackers@postgresql.org
On Thu, Feb 16, 2006 at 01:10:48PM +0100, Florian Weimer wrote:
> * Neil Conway:
>
> > On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
> >> It seems clear that our qsort.c is doing a pretty awful job of picking
> >> qsort pivots, while glibc is mostly managing not to make that mistake.
> >> I haven't looked at the glibc code yet to see what they are doing
> >> differently.
> >
> > glibc qsort is actually merge sort, so I'm not surprised it avoids this
> > problem.
>
> qsort also performs twice as many key comparisons as the theoretical
> minimum. If key comparison is not very cheap, other schemes (like
> heapsort, for example) are more attractive.
Last time around there were a number of different algorithms tested.
Did anyone run those tests while getting it to count the number of
actual comparisons (which could easily swamp the time taken to do the
actual sort in some cases)?
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.
Attachments:
signature.asc (application/pgp-signature, 188B) download
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: [PERFORM] qsort again
2006-02-16 12:10 Re: qsort again Florian Weimer <fw@deneb.enyo.de>
2006-02-16 12:49 ` Re: qsort again Martijn van Oosterhout <kleptog@svana.org>
@ 2006-02-16 13:08 ` Sven Geisler <sgeisler@aeccom.com>
0 siblings, 0 replies; 4+ messages in thread
From: Sven Geisler @ 2006-02-16 13:08 UTC (permalink / raw)
To: Martijn van Oosterhout <kleptog@svana.org>; +Cc: Florian Weimer <fw@deneb.enyo.de>; Neil Conway <neilc@samurai.com>; Tom Lane <tgl@sss.pgh.pa.us>; Gary Doades <gpd@gpdnet.co.uk>; pgsql-performance; pgsql-hackers@postgresql.org
Martijn van Oosterhout schrieb:
>
> Last time around there were a number of different algorithms tested.
> Did anyone run those tests while getting it to count the number of
> actual comparisons (which could easily swamp the time taken to do the
> actual sort in some cases)?
>
The last time I did such tests is almost 10 years ago. I had used
MetroWerks CodeWarrior C/C++, which had Quicksort as algorithm in the Lib C.
Anyhow, I tested a few algorithms including merge sort and heapsort. I
end up with heapsort because it was the fastest algorithm for our issue.
We joined two arrays where each array was sorted and run qsort to sort
the new array.
Sven.
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: [PERFORM] qsort again
2006-02-16 12:10 Re: qsort again Florian Weimer <fw@deneb.enyo.de>
@ 2006-02-16 13:38 ` Ron <rjpeace@earthlink.net>
1 sibling, 0 replies; 4+ messages in thread
From: Ron @ 2006-02-16 13:38 UTC (permalink / raw)
To: Florian Weimer <fw@deneb.enyo.de>; pgsql-performance; pgsql-hackers@postgresql.org
At 07:10 AM 2/16/2006, Florian Weimer wrote:
>* Neil Conway:
>
> > On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
> >> It seems clear that our qsort.c is doing a pretty awful job of picking
> >> qsort pivots, while glibc is mostly managing not to make that mistake.
> >> I haven't looked at the glibc code yet to see what they are doing
> >> differently.
> >
> > glibc qsort is actually merge sort, so I'm not surprised it avoids this
> > problem.
>
>qsort also performs twice as many key comparisons as the theoretical
>minimum.
The theoretical minimum number of comparisons for a general purpose
comparison based sort is O(lgN!).
QuickSort uses 2NlnN ~= 1.38NlgN or ~1.38x the optimum without tuning
(see Knuth, Sedgewick, Corman, ... etc)
OTOH, QuickSort uses ~2x as many =moves= as the theoretical minimum
unless tuned, and moves are more expensive than compares in modern systems.
See my other posts for QuickSort tuning methods that attempt to
directly address both issues.
Ron
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2006-02-16 13:38 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-02-16 12:10 Re: qsort again Florian Weimer <fw@deneb.enyo.de>
2006-02-16 12:49 ` Martijn van Oosterhout <kleptog@svana.org>
2006-02-16 13:08 ` Sven Geisler <sgeisler@aeccom.com>
2006-02-16 13:38 ` Ron <rjpeace@earthlink.net>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox