[petsc-dev] DMPlexMarkBoundaryFaces is quadratic time

[Matthew Knepley]

On Wed, Nov 20, 2013 at 8:38 PM, Geoffrey Irving <irving at naml.us> wrote:

> On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <knepley at gmail.com>
> wrote:
> > On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <irving at 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.

  Thanks,

      Matt


>
> Geoffrey
>



-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20131120/b5d0ada2/attachment.html>