[petsc-users] PetscSortRealWithPermutation causes segfaults

[Jed Brown]

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

> I am using PetscSortRealWithPermutation to sort an array with around
> 200K elements and it causes a segfault.
>
> STL sort is able to handle this array without any problems.
>
> I looked at the gdb backtrace. It primarily seems to be because the
> stack is exhausted because of recursive calls to
> PetscSortRealWithPermutation_Private. I am wondering if it might not be
> a better idea to implement PetscSortRealWithPermutation_Private without
> recursion to avoid these errors?
>

Non-recursive may still need O(n) memory because a "stack" needs to be
stored, and it just masks the real problem which is decay to quadratic
behavior.

This issue of hitting worst case of quicksort came up before with
PetscSortInt. It would be interesting to know if the pivot selection in
PetscSortInt_Private would fix the worst-case behavior that you see? If so,
then the same changes could be made to the other sorting routines.

Better solutions involve putting real work into finding good pivots or
falling back to heap sort ("introsort") when bad behavior is detected.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110506/3bc5c7cf/attachment.htm>