[gecode-users] Quicksort bug

[Christian Schulte]

Hi Michal,

you are absolutely right, our quicksort implementation only handles strict
comparison! And actually, I did it that way because partitioning becomes
more efficient that way.

However, the bug was in the docs which omitted that piece of information
(quicksort is actually one of the oldest parts of Gecode and existed before
Gecode got its documentation)! That's now fixed together with the assertions
you suggested and works for arrays that have more than 2^32 elements (I
chose sizeof(int) * CHAR_BITS, as you can only use integers to specify the
number of elements to sort).

I also fixed the order for TupleSet but not the duplicate issue (just make
the order strict), I'll leave that to Mikael who will be back tomorrow.

Thanks again for your kind effort!

Cheers
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: Michal D. [mailto:michal.dobrogost at gmail.com] 
Sent: Tuesday, December 16, 2008 5:24 AM
To: Christian Schulte
Cc: users at gecode.org
Subject: Re: [gecode-users] Quicksort bug

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