Fande Kong via petsc-dev <[email protected]> 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
