qsort implementaion in glibc-2.0.6
Paul_...@bigfoot.com
me know. Otherwise, here's my complaint 'o the day:
The qsort implementation in glibc-2.0.6 is not as fast as it could be.
Basically, when you call qsort(), it will call one of two internal
implementations, _msort() or _quicksort(). _msort() seems to require space
allocated equal to the size of the array being sorted.
The rules for deciding which to call go as follows:
if the total size to be sorted is under 1K
{
Get space on the stack
Call _msort
}
else
{
Try to allocate space
if this fails
call _quicksort()
else
{
call _msort()
free allocated space
}
}
In otherwords, if at all possible, call _msort.
The problem is, _msort seems to be slower. I haven't studied the _msort code
thouroughly, but it seems to be a merge sort implementation. _quicksort
looks like a carefully optimized implementation of quicksort. It was my
understanding that merge sort had a better worst-case running time that
quicksort, but that in practice quicksort had a much lower constant making
the average case run time much better. That, in fact, is what I'm seeing:
For my simple test of lists ranging from 100 items to 50 million, I did
timings calling either qsort as usual or _quicksort directly. _quicksort was
always faster. For the smallest case it was 5% faster. For the largest it
was 37% faster. These were just character arrays, so the smallest case
should fit within in the special "fit it on the stack frame" case the qsort
is designed to take advantage of.
I don't know if the extra time is a result of the allocation and freeing of
space, or if it is the algorithm itself.
Is there a compelling reason to keep the _msort implementation there under
the covers? If so, what are the situations where it makes sense?
Thanks,
Paul
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Nathan Myers
>Followup to: <73ch83$7u4$1...@nnrp1.dejanews.com>
>By author: Paul_...@bigfoot.com
>In newsgroup: comp.os.linux.development.system
>>
>> The qsort implementation in glibc-2.0.6 is not as fast as it could be.
>
>invented, that is as fast as quicksort in the common case but has none
>of the pathologies of quicksort. Sounds like a good candidate, if
>someone can find it...
Yes, this is the sort found in the latest SGI STL, which will
eventually find its way into libstdc++-v3. It was invented by
Dave Musser at Rennsaeler Polytechnic Institute in Troy, New York.
In fact it more-or-less *is* quicksort in the common case, but
detects when it has a pathological data set and uses a deterministic
(but still O(n*log(n))) alternative.
It shouldn't be *too* hard to translate from the C++ back to C. Ulrich
probably hasn't time, but it would be a good project for somebody else
to do and send him patches.
--
Nathan Myers
n...@nospam.cantrip.org http://www.cantrip.org/
H. Peter Anvin
By author: Paul_...@bigfoot.com
In newsgroup: comp.os.linux.development.system
>
> me know. Otherwise, here's my complaint 'o the day:
>
> implementations, _msort() or _quicksort(). _msort() seems to require space
> allocated equal to the size of the array being sorted.
>
As far as I know there is a new sorting algorithm that was just
invented, that is as fast as quicksort in the common case but has none
of the pathologies of quicksort. Sounds like a good candidate, if
someone can find it...
-hpa
--
PGP: 2047/2A960705 BA 03 D3 2C 14 A8 A8 BD 1E DF FE 69 EE 35 BD 74
See http://www.zytor.com/~hpa/ for web page and full PGP public key
I am Bahá'í -- ask me about it or see http://www.bahai.org/
"To love another person is to see the face of God." -- Les Misérables
Dave Platt
H. Peter Anvin <h...@transmeta.com> wrote:
>As far as I know there is a new sorting algorithm that was just
>invented, that is as fast as quicksort in the common case but has none
>of the pathologies of quicksort. Sounds like a good candidate, if
>someone can find it...
The method I was taught as "quickersort", somewhat over 20 years ago,
is basically a quicksort extended with a couple of modifications:
- Take care to choose a good median value. Rather than choosing one
value from the array, take three (e.g. first, last, middle of the
array) and choose the median of these three values as the
partitioning midpoint value. This helps reduce the risk of
degenerate behavior if the array is already sorted.
- Switch from quicksort to a simple deterministic-time algorithm (e.g.
double-loop exchange sort) when the size of the partition drops
below a specific threshold (I usually use 5-6 items as the
threshold). This switches the low levels of the sort from an
O(n log n) with a relatively high constant overhead (recursion isn't
necessarily cheap) to an O(n^2) with a lower constant overhead, and
can save significant amounts of time when n is small.
--
Dave Platt dpl...@feghoot.ml.org
Visit the Jade Warrior home page: http://feghoot.ml.org/jade-warrior/
I do _not_ wish to receive unsolicited commercial email, and I will
boycott any company which has the gall to send me such ads!
Markus Hoevener
|> > The qsort implementation in glibc-2.0.6 is not as fast as it could be.
|> > Basically, when you call qsort(), it will call one of two internal
|> > implementations, _msort() or _quicksort(). _msort() seems to require space
|> > allocated equal to the size of the array being sorted.
|> >
|>
|> As far as I know there is a new sorting algorithm that was just
|> invented, that is as fast as quicksort in the common case but has none
|> of the pathologies of quicksort. Sounds like a good candidate, if
|> someone can find it...
Hi,
I didn't hear anything about this new method, but why don't you try
heapsort (or better: bottom-up-heapsort)? It garantues O(n log(n)) for
worst case. And it's easy to implement.
By the way: there is no sorting algorithm being faster than O(n log(n))
(sorting algorithms based on comparing keys, not like bucketsort).
Bye,
Markus
Kevin Huber
H> As far as I know there is a new sorting algorithm that was just
H> invented, that is as fast as quicksort in the common case but has none
H> of the pathologies of quicksort. Sounds like a good candidate, if
H> someone can find it...
There is a Radix/Quicksort hybrid by Robert Sedgewick and Jon Bentley
that was recently published with source in Dr. Dobb's journal
(Nov. 1998.) It is supposed to compare well to quicksort (including
the modified ones).
http://www.ddj.com/ftp/1998/1998_11/aa118.txt
-Kevin
James Youngman
> There is a Radix/Quicksort hybrid by Robert Sedgewick and Jon Bentley
> that was recently published with source in Dr. Dobb's journal
> (Nov. 1998.) It is supposed to compare well to quicksort (including
> the modified ones).
>
> http://www.ddj.com/ftp/1998/1998_11/aa118.txt
Now, *that* is a collaboration. A collaboration between the authors
of "Algorithms" and one of the canonical works on efficient
programming in C.
--
ACTUALLY reachable as @free-lunch.demon.(whitehouse)co.uk:james+usenet
Akira Wada
in the article <73ch83$7u4$1...@nnrp1.dejanews.com>
Paul_...@bigfoot.com wrote:
>
> My apologies if this is the wrong forum for this type of message. Just let
> me know. Otherwise, here's my complaint 'o the day:
>
> Basically, when you call qsort(), it will call one of two internal
> implementations, _msort() or _quicksort(). _msort() seems to require space
> allocated equal to the size of the array being sorted
>
>
> In otherwords, if at all possible, call _msort.
>
(1) worst case behaviors, O(n^2) for peculiar input :
partially sorted, low variety of key-value, malicious arrangement etc.,
(2) non-stability :
unable to preserve the initial order of the elements with equal sort key,
by using mergesort, at the sacrifice of speed.
If you make much of speed and safety, try "qsortz.c" on my private web-site,
http://www.mars.dti.ne.jp/~a-wada/qsortlib.html
and peek for more information about quicksort.
Akira Wada <a-w...@mars.dti.ne.jp>
Asger K. Alstrup Nielsen
>In fact it more-or-less *is* quicksort in the common case, but
>detects when it has a pathological data set and uses a deterministic
>(but still O(n*log(n))) alternative.
>It shouldn't be *too* hard to translate from the C++ back to C. Ulrich
>probably hasn't time, but it would be a good project for somebody else
>to do and send him patches.
Did anybody investigate whether it pays to use some of the modern
sorting techniques that have O(n (log log n)^2) time behaviour, which
is better than O(n log n)?
See
http://data.mpi-sb.mpg.de/internet/reports.nsf/NumberView/97-1-016
Abstract:
The RAM complexity of deterministic linear space sorting of
integers in words is improved from O(n sqrt(log n)) to
O(n(log log n)^2). No better bounds are known for polynomial space.
In fact, the techniques give a deterministic linear space priority
queue supporting insert and delete in O((log log n)^2) amortized
time and find-min in constant time. The priority queue can be
implemented using addition, shift, and bit-wise boolean operations.
A "RAM" is what we program in C.
The last statement is in fact stronger: The algorithm can be implemented
using *only* those operations (in particular, no multiplication is needed
which was not the case for earlier deterministic sorts below O(n log n))).
Alternatively, there are randomized algorithms that perform in
expected O(n log log n) time:
M. Thorup. "Randomized sorting in O(n log log n) time and linear
space using addition, shift, and bit-wise boolean operations. In
Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms,
pages 352-359, 1997.
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-14.ps.gz
It will require some effort to understand the papers, but it should be
entirely possible to implement this and test-drive it. I'm not aware of
any implementations yet, and it would be cool to let glibc boast the fastest
sort in the world.
Greets,
Asger Alstrup