On Fri, 03 Sep 2010 17:28:55 +0200, Jed Brown <jed at 59A2.org> wrote: > FAST -O1: 2.0 seconds > FAST -O0: 5 seconds > SLOW -O1: 2.3 seconds > SLOW -O0: more than an hour
The issue here is that my -O0 cases above also had PETSC_USE_DEBUG set, which was sorting a problem-sized (2M) element array as a consistency check in AOCreateBasic. In the 102^3 case, it didn't trigger any bad behavior from quicksort, but in the 202x102x102 case, it degraded to quadratic (and eventually overflowed the stack, despite choosing the median-3 pivot). I have pushed a new quicksort which avoids this bad behavior for all the inputs I tried (and is faster than before on all of these inputs as well). Here is for the 202x102x102 test case with the new implementation: Debug: MatAssemblyBegin 8 1.0 5.3647e-0118.5 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 2 0 0 0 6 2 0 0 0 8 0 MatAssemblyEnd 8 1.0 1.3259e+00 1.0 0.00e+00 0.0 2.0e+01 2.9e+04 6.3e+01 8 0 38 0 31 8 0 38 0 42 0 MatGetSubMatrice 2 1.0 2.0135e+00 1.0 0.00e+00 0.0 2.0e+01 9.6e+06 1.0e+01 12 0 38 51 5 12 0 38 51 7 0 MatLoad 1 1.0 5.0351e+00 1.0 0.00e+00 0.0 2.1e+01 9.0e+06 4.7e+01 30 0 40 50 23 30 0 40 50 31 0 MatView 1 1.0 5.0372e+00 1.1 0.00e+00 0.0 1.9e+01 9.9e+06 2.9e+01 28 0 37 50 14 28 0 37 50 19 0 Optimized: MatAssemblyBegin 8 1.0 3.2006e-01 3.8 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 2 0 0 0 9 2 0 0 0 15 0 MatAssemblyEnd 8 1.0 8.3971e-01 1.0 0.00e+00 0.0 2.0e+01 2.9e+04 3.6e+01 9 0 38 0 26 9 0 38 0 44 0 MatGetSubMatrice 2 1.0 9.9702e-01 1.0 0.00e+00 0.0 2.0e+01 9.6e+06 1.0e+01 10 0 38 51 7 10 0 38 51 12 0 MatLoad 1 1.0 2.0991e+00 1.0 0.00e+00 0.0 2.1e+01 9.0e+06 2.6e+01 21 0 40 50 19 21 0 40 50 32 0 MatView 1 1.0 1.7195e+00 1.1 0.00e+00 0.0 1.9e+01 9.9e+06 1.9e+01 17 0 37 50 14 17 0 37 50 23 0 As a longer term matter, it's still possible to provide an input that degrades to O(n^2). Does PETSc really want to stick with quicksort, or would it be worth switching to e.g. heapsort to avoid this? It's usually not a performance-sensitive kernel for our use cases, so I'm not wild about going to a more sophisticated sort to eke out a few more percent. I have not changed any of the sort-with versions. Jed