[petsc-dev] Slowness of PetscSortIntWithArrayPair in MatAssembly

[Jed Brown]

Fande Kong via petsc-dev <petsc-dev at mcs.anl.gov> writes:

> Hi Developers,
>
> John just noticed that the matrix assembly was slow when having sufficient
> amount of off-diagonal entries. It was not a MPI issue since I was  able to
> reproduce the issue using two cores on my desktop, that is, "mpirun -n 2".
>
> I turned  on a profiling, and 99.99% of the time was spent
> on PetscSortIntWithArrayPair (recursively calling).   It took THREE MINUTES
>  to get the assembly done. And then changed to use the option
> "-matstash_legacy" to restore
> the code to the old assembly routine, and the same code took ONE SECOND to
> get the matrix assembly done.

Uff.

> Should write any better sorting algorithms?

It would be good to confirm (e.g., via debugger) that the problematic
array has some particular structure.  The naive quicksort in PETSc
degrades to quadratic for some ordered inputs data.  I (cheap) "fixed"
that in 2010, but never propagated it to the WithArray variants.  I
think we should do something similar (better median estimation) or
perhaps move to radix sorts.

https://bitbucket.org/petsc/petsc/commits/ef8e358335c5882e7d377b87160557d47280dc77