On Wed, Nov 20, 2013 at 6:44 PM, Matthew Knepley <knep...@gmail.com> wrote: > On Wed, Nov 20, 2013 at 8:38 PM, Geoffrey Irving <irv...@naml.us> wrote: >> >> On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <knep...@gmail.com> >> wrote: >> > On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <irv...@naml.us> wrote: >> >> >> >> Was there any particular reason for making DMPlexMarkBoundaryFaces a >> >> quadratic time algorithm? I realize it's hard to write a subquadratic >> >> time algorithm on top of DMLabelSetValue; maybe PETSc needs some basic >> >> integer hash tables? >> > >> > Why is it quadratic time? I just looked again, and it seems to be linear >> > time to me. >> >> It calls DMLabelSetValue for each boundary face. Each call to >> DMLabelSetValue seems to be O(log n) if the value is already set >> (binary search) and O(n/2) if the value is missing, since it does a >> PetscMemmove to shift roughly half the existing values over by one in >> order to insert the new entry in the middle of a sorted list. > > Yes that is correct. This is fixed in knepley/fix-hash-scaling which is > merged to next.
Great, thanks. I will look at next before future critiques. :) Geoffrey