[gecode-users] Quicksort bug

[Michal D.]

Hi Christian,

>  - Gecode's quicksort uses O(log n) stackspace: it will always push the
> larger array onto the stack,
>   which will be at least n/2 long! That's O(log n).

I completely missed this, that's a very nice property to have! =)


>  - There is no difference (in principle) whether you use a strict or
> non-strict ordering (as the complement
>   will be the opposite).

Nevertheless, I think this is where the problem stems from. Strictness
can be a problem if the code makes assumptions about it. Partition()
seems to depend on strictness:

Suppose the array is completely sorted and consists of very many
duplicate elements. Specifically there are many elements past R that
have the same value as (*R). Then we can imagine a situation in which
line sort.icc:121 is executed many times and i goes arbitrarily far
past the R pointer (since (*i) == (*R) and thus (*i) <= (*R) and thus
lt(*i, R*)). This would be impossible if the comparison was strict.
Continuing the trace, we reenter quicksort() with L > R (ie. L is to
the right of R).


> The only problem I see is that 32 was not good enough.

Indeed, on 64-bit machines 32 is too small. I don't follow why the
"sizeof(int)"? I think this value should be something along the lines
of:

sizeof(void*) * std::numeric_limits<unsigned char>::digits

Ie. 64 on current 64bit systems.


> Could you be so kind
> and retry what happens with replacing 32 by "sizeof(int) * 64"?

The sort is still running after 10 minutes and counting.

Using my dynamic stack I recall that I left it running for longer than
30 minutes before finally killing it.


>
> Then, how much memory does your machine have?

4Gb of memory in the system + 8gb of pagefile. The program uses 600Mb
when I use the strict comparison operator and at a depth of about 30
spaces. Note that it works fine with a depth 32 stack so long as the
comparison operator is strict.


> Then, how deep does the stack
> grow for Quicksort and how many elements does the array have you try to
> sort?

The TupleSet contains 4728252 tuples. If you want, I can send you the data.

I recall that with the dynamic stack the stack depth exceeded 1024.

Cheers,

Michal


> --
> Christian Schulte, www.it.kth.se/~cschulte/
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Michal D.
> Sent: Saturday, December 13, 2008 7:03 PM
> To: users at gecode.org
> Subject: [gecode-users] Quicksort bug
>
> Hi All,
>
> I had one hell of a bug hunt recently. What started as a crash on winxp x64
> ended up in a "true" being changed to a "false" on freebsd (so I could
> sanely debug into the Gecode code base). The culprit was FullTupleCompare
> (gecode/int/extensional/tuple-set.cc) but quicksort also got hit in the
> cross-fire.
>
> FullTupleCompare implements a less than or equal (<=) operator and not a
> strict less than (<) operator. In effect, for the case where both tuples are
> identical up the arity it returns true instead of false.
> This causes quicksort massive problems. See tuple-set.cc.diff for the fix.
>
> The gecode quicksort assumes that its stack will never exceed a depth of 32.
> This was getting exceeded when used on a large tupleset with the above
> comparison operator. However, in general this assumption is wrong. Stack
> usage for quicksort is worst case O(n) depending on the values that are
> chosen for the pivot! Exceeding the stack current results in an outright
> crash as an out of bounds pointer is dereferenced. I toyed with two fixes:
>
> 1) make push return a success/failure code and if the push fails then call
> quicksort recursively instead of pushing onto the stack. See sort.icc.diff.
>
> 2) start off with an static stack and expand it dynamically if it's
> exceeded. I'm not sure if Memory::malloc() / Memory::free() are the right
> ways to go about grabbing memory. There is no performance penalty if the
> stack depth does not exceed 32 entries. See sort.icc.diff2.
>
> Both solutions have the overhead of checking if the stack is going to exceed
> 32 entries on a push. This doesn't seem significant especially since most of
> the work should be happening in partition. My vote is for fix # 2 as it
> seems to be the more robust solution (no potential stack overflow).
>
> Cheers,
>
> Michal
>
>