smuggling data in and out of alarm handlers and the like

[Keith Thompson]

[...]
And if you think that a sorting routine is simple enough that there's
no significant risk of getting it wrong, consider this (Jon Bentley,
"Programming Pearls"):

While the first binary search was published in 1946, the first
binary search that works correctly for all values of n did not
appear until 1962.

The most reliable code is the code that isn't there.

So you think compiler vendors implement qsort() without any code?

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions [*] of other programmers. That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library. Have you?

qsort() also mashes things through void * pointers, which means you
*LOSE* type safety -- so this introduces other risk to the code.

A valid point. You have to be careful in how you invoke qsort(), and
in how you write the comparison routine. I still think that using
qsort() is less error-prone than writing your own specialized sorting
routine (but sometimes the risk is worth it).

All this is besides the point that you just equated sorting with
binary search.

That was not my intent. I'd say that sorting and binary search are
tasks of comparable complexity. The observation that it took 16 years
to get binary search right was an illustration, not a proof.

[*] 1.21 zillion, on average, according to a recent survey.

 

[Eric Sosman]

[...]
I've never heard of a buggy qsort() in a released implementation of
the C standard library. Have you?

Once. (Well, almost: It was actually a pre-Standard C
and hence not part of "the C standard library." But there
was a problem with an attempted optimization: The qsort()
tried to use different item-swap functions internally, based
on the item size, qsort()'s third argument. Unfortunately,
it assumed that "item size divisible by four" meant "safe to
swap in units of `int' instead of units of `char'." This was
fine until you tried to qsort() an array of 4N-byte objects
that weren't aligned on four-byte boundaries ... A patch was
issued, and right rapidly, too.)

 

[Tor Rustad]

Keith Thompson wrote:

[...]

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions [*] of other programmers. That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library. Have you?

I wouldn't trust the system privided qsort() with my life, in such a
case, I would run my own implementation for sure.

A couple of years ago, I actually wrote a sort benchmark to compare the
performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

IMO, for serious sort jobs, qsort() is a bad candidate, since it's a QoI
issue, weather the standard library implementation is stable or not.
OTOH, I can agree that non-expert replacements of qsort(), often are
worse, just as non-expert replacements of rand() are.

 

[Keith Thompson]

Keith Thompson wrote:

[...]

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions [*] of other programmers. That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library. Have you?

I wouldn't trust the system privided qsort() with my life, in such a
case, I would run my own implementation for sure.

Hmm. I still think I'd trust a system qsort() more than something I
wrote myself. Either could have bugs, but a system qsort()'s bugs are
more likely to have been found and corrected.

On the other hand, a good *published* sorting routine could be better
than either.

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug. There's no requirement for qsort() to be a stable
sort (defined as one for which items with equal keys maintain their
original ordering).

IMO, for serious sort jobs, qsort() is a bad candidate, since it's a
QoI issue, weather the standard library implementation is stable or
not.

If you need a *stable* sort, then either you can't use qsort(), or you
need to give it a comparison function that uses the initial position
as a secondary key.

OTOH, I can agree that non-expert replacements of qsort(), often are
worse, just as non-expert replacements of rand() are.

Indeed.

 

[user923005]

Keith Thompson wrote:

[...]

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions [*] of other programmers.  That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library.  Have you?

I wouldn't trust the system privided qsort() with my life, in such a
case, I would run my own implementation for sure.

A couple of years ago, I actually wrote a sort benchmark to compare the
performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

The Microsoft qsort implementation is a version of Singleton's sort.
An older version had some safety checks in it for the quadratic cases:
1. In-order partition
2. Reversed partition
I noticed (several years ago) that the safety checks were removed. I
was working as a subcontractor at MS at the time, so I called the guy
who did it on the phone.
I asked him why the checks were removed. He said that they did not
make the code run any faster. I told him that the reason they were
there was for certain degenerate cases that can make the sort go
quadratic. He wasn't too interested. I looked today, and the checks
still are not in there (though there have been a few small
improvements since the last time I looked).

P. J. Plauger has written a very nice introspective sort. For a
general qsort() interface, I don't think you can do much better since
it never goes quadratic.

IMO, for serious sort jobs, qsort() is a bad candidate, since it's a QoI
issue, weather the standard library implementation is stable or not.
OTOH, I can agree that non-expert replacements of qsort(), often are
worse, just as non-expert replacements of rand() are.

You just got an 'Amen!' from the congregation.

 

[lawrence.jones]

Once. (Well, almost: It was actually a pre-Standard C
and hence not part of "the C standard library." But there
was a problem with an attempted optimization: The qsort()
tried to use different item-swap functions internally, based
on the item size, qsort()'s third argument. Unfortunately,
it assumed that "item size divisible by four" meant "safe to
swap in units of `int' instead of units of `char'." This was
fine until you tried to qsort() an array of 4N-byte objects
that weren't aligned on four-byte boundaries ... A patch was
issued, and right rapidly, too.)

There was a similar, but different problem with the same kind of
optimization in DEC's C library: the function correctly checked for both
alignment and size before setting the flag to swap by ints rather than
chars, but neglected to ever reset the flag.

-Larry Jones

I've got an idea for a sit-com called "Father Knows Zilch." -- Calvin

 

[Tor Rustad]

The Microsoft qsort implementation is a version of Singleton's sort.
An older version had some safety checks in it for the quadratic cases:
1. In-order partition
2. Reversed partition
I noticed (several years ago) that the safety checks were removed. I
was working as a subcontractor at MS at the time, so I called the guy
who did it on the phone.
I asked him why the checks were removed. He said that they did not
make the code run any faster. I told him that the reason they were
there was for certain degenerate cases that can make the sort go
quadratic. He wasn't too interested. I looked today, and the checks
still are not in there (though there have been a few small
improvements since the last time I looked).

Thank you for providing this very interesting information. I was
somewhat shocked at the time of discovery, but never reported the issue
to Microsoft.

 

[Tor Rustad]

Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

 

[Harald van Dijk]

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

If a program requires a stable sort, and uses qsort, it is the
responsibility of the program to pass qsort a comparison function that
takes into account the original order of the elements. If it does not, as
there is no guarantee that qsort performs a stable sort, it is the
program that has a bug, not the implementation, since it is the program
that makes unwarranted assumptions.

 

[jameskuyper]

Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

A program is buggy if it calls qsort() in a context where a stable
sort is required. An implementation of qsort() which fails to provide
a stable sort is not buggy (unless that particular implementation's
documentation claims that it does provide a stable sort). In both
cases, that's because there's no such requirement imposed on qsort()
by the C standard.

 

[Eric Sosman]

Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

It's not a bug *in qsort()* if the sort is non-stable,
because qsort()'s specification does not include stability.
It could well be a bug in the program, if the programmer
mistakenly assumed that qsort() sorts stably. If so, the
user of qsort() is at fault, not its implementor.

 

[Eric Sosman]

There was a similar, but different problem with the same kind of
optimization in DEC's C library: the function correctly checked for both
alignment and size before setting the flag to swap by ints rather than
chars, but neglected to ever reset the flag.

Y'know, I think you've got the story right and I had it
wrong. The buggy qsort() I encountered was DEC's (in the
pre-Standard VAXC library, not the later DECC edition), and
it's too much of a coincidence to think that DEC would have
made two such closely related mistakes. I think maybe a wild
pointer has overwritten some of my own personal memory cells,
which are beginning to merit the `volatile' qualifier ...

 

[user923005]

Keith Thompson wrote:
[...]
A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

I wish this article were online:
"J. L. Bentley. Software exploratorium: The trouble with qsort. UNIX
Review, 10(2):85-93, February 1992."

See also:
http://www.enseignement.polytechniq.../Luc.Maranget/421/09/bentley93engineering.pdf
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

 

[Keith Thompson]

Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

I wish this article were online:
"J. L. Bentley. Software exploratorium: The trouble with qsort. UNIX
Review, 10(2):85-93, February 1992."

Can you post a brief summary? Does Bentley descrebie problems with
qsort(), with existing implementations of qsort(), or with Quicksort?

See also:
http://www.enseignement.polytechniq.../Luc.Maranget/421/09/bentley93engineering.pdf
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

Based on a *very* quick look, both of those seem to be talking mostly
about the Quicksort algorithm; the first does acknowledge that qsort()
needn't be Quicksort, and proposes an implementation for qsort().

 

[user923005]

Keith Thompson wrote:
Keith Thompson wrote:
[...]
A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.
That's not a bug.
That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

I wish this article were online:
"J. L. Bentley. Software exploratorium: The trouble with qsort. UNIX
Review, 10(2):85-93, February 1992."

Can you post a brief summary?  Does Bentley descrebie problems with
qsort(), with existing implementations of qsort(), or with Quicksort?

This is from memory, and it was 15 years ago, so some of the details
will be off a bit.

Bentley was running an important job that typically took a couple of
hours or less and suddenly it started taking a whole weekend. Now,
this sort of thing was simply unacceptable, so they had to get to the
bottom of it. There are some types of distributions that give vanilla
quick sort fits. For example, already sorted data, reverse sorted
data or (in this case) organ-pipe ordered data. The solution they
came up with at the time was to switch to a rather snazzy heap-sort.
It did not perform as well as quick sort on average, but it never went
perverse. I used to have the code (I typed it in from the magazine
article) but I'll be darned if I can find it now. I'll keep looking
and if I find it, I will post it.

Based on a *very* quick look, both of those seem to be talking mostly
about the Quicksort algorithm; the first does acknowledge that qsort()
needn't be Quicksort, and proposes an implementation for qsort().

Right. Those articles are repairs for quicksort() but have a quick
sort algorithm under the covers in the final analysis.

--
Keith Thompson (The_Other_Keith) <[email protected]>
[...]
"We must do something.  This is something.  Therefore, we must do this.."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"- Hide quoted text -

- Show quoted text -

 

[Tor Rustad]

]

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

If a program requires a stable sort, and uses qsort, it is the
responsibility of the program to pass qsort a comparison function that
takes into account the original order of the elements. If it does not, as
there is no guarantee that qsort performs a stable sort, it is the
program that has a bug, not the implementation, since it is the program
that makes unwarranted assumptions.

Hmm, it appears I have been using the term "stable" incorrectly above,
what I was thinking about, was rather the worst-case performance of qsort().

 

[Tor Rustad]

Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

It's not a bug *in qsort()* if the sort is non-stable,
because qsort()'s specification does not include stability.
It could well be a bug in the program, if the programmer
mistakenly assumed that qsort() sorts stably. If so, the
user of qsort() is at fault, not its implementor.

Let us assume, that Sun used Eric as QA for a qsort implementation, to
be rolled out on every Solaris box on the planet.

The conforming qsort() implementation presented on your desk, has

* a recursive implementation
* best-case performance O(N²)
* average performance O(N²)
* worst-case performance O(N²)
* unstable

will you approve it?

 

[lawrence.jones]

Hmm, it appears I have been using the term "stable" incorrectly above,
what I was thinking about, was rather the worst-case performance of qsort().

Yes, "stable" in the context of sorting means that the ordering of items
that compare equal is preserved.

-Larry Jones

I just can't identify with that kind of work ethic. -- Calvin

 

[Keith Thompson]

Eric Sosman wrote: [...]

It's not a bug *in qsort()* if the sort is non-stable,
because qsort()'s specification does not include stability.
It could well be a bug in the program, if the programmer
mistakenly assumed that qsort() sorts stably. If so, the
user of qsort() is at fault, not its implementor.

Let us assume, that Sun used Eric as QA for a qsort implementation, to
be rolled out on every Solaris box on the planet.

The conforming qsort() implementation presented on your desk, has

* a recursive implementation
* best-case performance O(N²)
* average performance O(N²)
* worst-case performance O(N²)
* unstable

will you approve it?

The character follwing the 'N' didn't come through properly; it looks
like either "O(N )" or "O(N)". I *think* it was supposed to be a
superscript 2.

Not speaking for Eric, but a qsort() implementation that's O(N**2) in
the best, average, and worst cases would be unacceptable; one that's
merely O(N**2) in the worst case would be better, but probably still
unacceptable. This is a serious quality-of-implementation issue. But
since the standard says nothing about performance, it's not a
conformance issue at all. A qsort() that uses a bubblesort algorithm,
or even bogosort, would be conforming.

The C++ standard does specify Big-O performance requirements for such
things. I wouldn't mind of the C stnadard did so as well. But C++
defines so many algorithms, and C defines so few, that such a change
probably wouldn't make any real difference; nobody is *really* going
to provide an O(N**2) qsort().

As for stability (guaranteeing that items with equal keys retain their
original order), I don't see that as an issue. It would be nice for
qsort() to be stable *if* it can be done without hurting average or
worst-case performance. But the standard doesn't guarantee, or even
imply, stability, and as a programmer I just don't expect it. If I
want stability, I can either invoke qsort() with a comparison function
that looks at the original positions (which I'd have to store with the
items) or write my own -- or the implementation.

On obvious solution is for the implementation to provide an
alternative sorting routine that's guaranteed to be stable. I don't
recall any implementations doing this; perhaps that says something
about the demand for it.

This is just my opinion (O(N**2) is bad; instability is ok), but I
suspect that most people would agree.

 

[Eric Sosman]

Keith Thompson wrote:
Keith Thompson wrote:

[...]

A couple of years ago, I actually wrote a sort benchmark to compare
the performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

That's not a bug.

That depends on the program, I can think of more than one case where
such a thing would have been considered a serious bug.

It's not a bug *in qsort()* if the sort is non-stable,
because qsort()'s specification does not include stability.
It could well be a bug in the program, if the programmer
mistakenly assumed that qsort() sorts stably. If so, the
user of qsort() is at fault, not its implementor.

Let us assume, that Sun used Eric as QA for a qsort implementation, to
be rolled out on every Solaris box on the planet.
>
The conforming qsort() implementation presented on your desk, has

* a recursive implementation
* best-case performance O(N²)
* average performance O(N²)
* worst-case performance O(N²)
* unstable

will you approve it?

I'd file a bug report based on the second and third points,
with a likely mention of the fourth. The C Standard does not
require good "quality of implementation," but no self-respecting
organization would be happy about releasing something so very
far behind the state of the art.

The other two points would not figure in my hypothetical
bug report. The first is an implementation detail, something
that makes no never-mind if the sort performs correctly and
reasonably well. And the fifth is a non-issue.[*]

[*] Assuming "unstable" means what it usually means in the
literature on sorting. Elsethread, I see that there has been
some confusion on this point.