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, l...@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 <[email protected]> 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: [email protected] [mailto:[email protected]] On Behalf
> Of Michal D.
> Sent: Saturday, December 13, 2008 7:03 PM
> To: [email protected]
> 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
>
>
#include <iostream>
#define forceinline inline
#include "sort.icc"
using namespace std;
using namespace Gecode::Support;
const int SIZE = 21;
class comp {
public:
bool operator() (int rhs, int lhs) {
return rhs <= lhs;
//return rhs < lhs;
}
};
int main () {
int * v = new int[SIZE];
for (int i = 0; i < SIZE; ++i) {
v[i] = 5;
}
comp c;
quicksort(& v[0], SIZE, c);
cout << "done" << endl;
}
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
