[gecode-users] Quicksort bug

[Michal D.]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tuple-set.cc.diff
Type: application/octet-stream
Size: 833 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20081213/61408fd1/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort.icc.diff
Type: application/octet-stream
Size: 2954 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20081213/61408fd1/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort.icc.diff2
Type: application/octet-stream
Size: 2937 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20081213/61408fd1/attachment-0002.obj>