[petsc-users] PetscSortRealWithPermutation causes segfaults

[Jed Brown]

On Fri, May 6, 2011 at 18:59, S V N Vishwanathan <vishy at stat.purdue.edu>wrote:

> I did a bit more investigation and found that this worst case is
> happening when all the elements of the array are the same. I am
> detecting this in my code and avoid calling the sort as a stop gap
> measure.
>
> I don't think there will be trouble with a O(n) memory in a queue but a
> recursive call overflows the stack.
>

The problem is that if you are blowing the stack, then you are seeing
quadratic behavior which is not acceptable either. So "putting the stack on
the heap" (managing the stack manually) isn't an acceptable solution, the
quadratic complexity has to be fixed. I believe that this worst-case
behavior is pretty hard to hit with the pivot choice in
PetscSortInt_Private, I know it is a problem with the pivot choice in the
other variants, they just didn't get updated when PetscSortInt was updated.

Always dynamically allocating memory is not ideal because it costs more on
some architectures. Tracking the stack depth and switching to manual
management of the stack is about the same amount of programming effort as
falling back to heap sort, but the latter guarantees log-linear complexity
and no dynamic memory allocation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110506/4f7a6935/attachment.htm>