smuggling data in and out of alarm handlers and the like

[Tor Rustad]

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.

I wrote O (N ^ 2), i.e. O(N**2) or O(N*N) all places.

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.

I can't speak for Eric either, but as QA, I would consider more than if
the implementation is conforming or not. If major institutions, running
critical business applications on Solaris, suddenly started running into
a O(N*N) wall, that would generate a lot of noise.


I can remember a somewhat similar real-life problem we had at work once.
On file close of full log files, the disk went busy... for a long time
(ca. 1 minute), which was totally unacceptable for this an online
system. I would be surprised, if no one else filed a bug-report, we for
sure did, and marked it *critical*.


Merge sort has worst-case O(N*log(N)) and is stable, but require O(N)
memory. Before approving any qsort() implementation, I would require a
comparison between different candidates, and not dream about allowing a
worst-case of O(N*N), unless significant performance gains otherwise,
and the worst-case was highly unlikely.

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().

Microsoft qsort() can go O(N*N), and according to "user", their qsort()
still can do that.

Instead of changing qsort(), the standard could add e.g. msort() or
stable_sort(), which had QoI requirements.

 

[Tor Rustad]

Eric Sosman wrote:

[...]

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

My bad.

After realizing the err, I looked up Sedgewick's definition of "stable"
sort, which made me understand the responses I got far better.

 

[Keith Thompson]

Keith Thompson wrote: [...]

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.

I can't speak for Eric either, but as QA, I would consider more than
if the implementation is conforming or not. If major institutions,
running critical business applications on Solaris, suddenly started
running into a O(N*N) wall, that would generate a lot of noise.

I agree completely. My point is that an O(N*N) qsort() is conforming,
not that it would be acceptable.

[...]

Microsoft qsort() can go O(N*N), and according to "user", their
qsort() still can do that.

Since it's easy enough to avoid such problems, I'd say that's a bug,
or at least a potentially serious problem.

Instead of changing qsort(), the standard could add e.g. msort() or
stable_sort(), which had QoI requirements.

I certainly wouldn't object to that.

 

[Tor Rustad]

Keith Thompson wrote: [...]
I can't speak for Eric either, but as QA, I would consider more than
if the implementation is conforming or not. If major institutions,
running critical business applications on Solaris, suddenly started
running into a O(N*N) wall, that would generate a lot of noise.

I agree completely. My point is that an O(N*N) qsort() is conforming,
not that it would be acceptable.
Agreed.

Microsoft qsort() can go O(N*N), and according to "user", their
qsort() still can do that.

Since it's easy enough to avoid such problems, I'd say that's a bug,
or at least a potentially serious problem.

Yes, it could, I do remember I had to abort the benchmark, sorts
expected to take a couple of seconds, took forever.