[gecode-users] Quicksort bug

[Christian Schulte]

Hi Michal,

I think that your reasoning is not fully correct: 
 - 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).
 - There is no difference (in principle) whether you use a strict or
non-strict ordering (as the complement
   will be the opposite).

The only problem I see is that 32 was not good enough. Could you be so kind
and retry what happens with replacing 32 by "sizeof(int) * 64"? 

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

Thanks
Christian
 

--
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