Hi Christian, > - 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).
I completely missed this, that's a very nice property to have! =) > - There is no difference (in principle) whether you use a strict or > non-strict ordering (as the complement > will be the opposite). Nevertheless, I think this is where the problem stems from. Strictness can be a problem if the code makes assumptions about it. Partition() seems to depend on strictness: Suppose the array is completely sorted and consists of very many duplicate elements. Specifically there are many elements past R that have the same value as (*R). Then we can imagine a situation in which line sort.icc:121 is executed many times and i goes arbitrarily far past the R pointer (since (*i) == (*R) and thus (*i) <= (*R) and thus lt(*i, R*)). This would be impossible if the comparison was strict. Continuing the trace, we reenter quicksort() with L > R (ie. L is to the right of R). > The only problem I see is that 32 was not good enough. Indeed, on 64-bit machines 32 is too small. I don't follow why the "sizeof(int)"? I think this value should be something along the lines of: sizeof(void*) * std::numeric_limits<unsigned char>::digits Ie. 64 on current 64bit systems. > Could you be so kind > and retry what happens with replacing 32 by "sizeof(int) * 64"? The sort is still running after 10 minutes and counting. Using my dynamic stack I recall that I left it running for longer than 30 minutes before finally killing it. > > Then, how much memory does your machine have? 4Gb of memory in the system + 8gb of pagefile. The program uses 600Mb when I use the strict comparison operator and at a depth of about 30 spaces. Note that it works fine with a depth 32 stack so long as the comparison operator is strict. > Then, how deep does the stack > grow for Quicksort and how many elements does the array have you try to > sort? The TupleSet contains 4728252 tuples. If you want, I can send you the data. I recall that with the dynamic stack the stack depth exceeded 1024. Cheers, Michal > -- > 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 > > _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
