[petsc-dev] DMPlexMarkBoundaryFaces is quadratic time

[Geoffrey Irving]

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

Great, thanks.  I will look at next before future critiques. :)

Geoffrey