Re: Bugs in our qsort implementation

Peter Geoghegan <pg@heroku.com> writes:
> On Thu, Jul 16, 2015 at 5:05 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> It's possible that this issue can only manifest on 9.4 and up where
>> we have the ability for tuplesort to allocate work arrays approaching
>> INT_MAX elements.  But I don't have a lot of faith in that; I think the
>> worst-case stack depth for the way we have it now could be as bad as O(N),
>> so in principle a crash could be possible with significantly smaller input
>> arrays.  I think we'd better back-patch this all the way.

> +1.

> If you want to generate a worst case, McIlroy wrote a program that
> will generate one [1]. AFAIR, it will generate a series of
> self-consistent comparisons in the "gas" comparator that produce a
> worst-case outcome (as opposed to producing a simple worse-case input,
> which would be more convenient in this kind of scenario). This is
> known specifically to affect the Bentley & McIlroy implementation, as
> the paper goes into.
> [1] http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

Wow, interesting article.  I stuck that into a test program with our
qsort, and found out that

(1) our "presort" check totally beats that oracle, because it causes
the oracle to freeze the "gas" in perfectly sequential order, so that
the presort run gets all the way through and decides that the input
is sorted.  Hence, N-1 comparisons and no recursion.

(2) if you dike out the presort check, you do see quadratic comparison
behavior but the max recursion depth is only 1.  Apparently, the oracle
effectively always makes the right-hand partition as large as possible,
so that recursing on the left partition is the optimal policy as far
as stack depth goes.

However, you can trivially modify this oracle to break our code: just
negate its comparison result, ie

-    return val[x] - val[y];        /* only the sign matters */
+    return -(val[x] - val[y]);    /* only the sign matters */

This stops the presort check immediately, since now the data looks
to be reverse-sorted instead of correctly ordered; and now it makes
the left-hand partition as large as possible, instead of the right.

With our unmodified code and the tweaked oracle, I see maximum recursion
depth in the vicinity of N/4.  So it's definitely possible to get O(N)
stack growth without a fix, though it may take very unusual input.  With
the correction to recurse to the smaller partition, we get max recursion
depth of just 1, since that always chooses a very small partition to
recurse to.
        regards, tom lane