[gecode-users] Quicksort bug

[Michal D.]

Hi Christian,

Put the attached file in the same directory as sort.icc. Compile with
"g++ -ggdb main.cpp".

The program uses quicksort on an array of 21 uniform elements. I get a
seg fault right on line 121 as predicted (hehe, can't believe my luck,
or rather bad luck).  It only happens with the "<" comparison. I
haven't tried on a 32 bit system but I don't imagine it would make any
difference.

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400dda in Gecode::Support::partition<int, comp>
(l=0x800d01084, r=0x800d010cc, lt=@0x7fffffffea9f) at sort.icc:121
121           while (lt(*(++i),v)) {}

Does Gecode admit the use of asserts? Maybe it should have a simple
check "assert(! lt(L[i], L[i]))" for all elements in the array in
debug mode before launching into the sort? I know the std library
containers do this type of thing (at least in MSVC).

Cheers,

Michal

On Mon, Dec 15, 2008 at 4:32 PM, Christian Schulte <cschulte at kth.se> wrote:
> 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
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cpp
Type: text/x-c++src
Size: 410 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20081215/0f898e2e/attachment.cpp>