<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Nov 20, 2013 at 8:38 PM, Geoffrey Irving <span dir="ltr"><<a href="mailto:irving@naml.us" target="_blank">irving@naml.us</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>> wrote:<br>

> On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <<a href="mailto:irving@naml.us">irving@naml.us</a>> wrote:<br>
>><br>
>> Was there any particular reason for making DMPlexMarkBoundaryFaces a<br>
>> quadratic time algorithm?  I realize it's hard to write a subquadratic<br>
>> time algorithm on top of DMLabelSetValue; maybe PETSc needs some basic<br>
>> integer hash tables?<br>
><br>
> Why is it quadratic time? I just looked again, and it seems to be linear<br>
> time to me.<br>
<br>
</div>It calls DMLabelSetValue for each boundary face.  Each call to<br>
DMLabelSetValue seems to be O(log n) if the value is already set<br>
(binary search) and O(n/2) if the value is missing, since it does a<br>
PetscMemmove to shift roughly half the existing values over by one in<br>
order to insert the new entry in the middle of a sorted list.</blockquote><div><br></div><div>Yes that is correct. This is fixed in knepley/fix-hash-scaling which is merged to next.</div><div><br></div><div>  Thanks,</div>
<div><br></div><div>      Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="HOEnZb"><font color="#888888"><br>
Geoffrey<br>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener
</div></div>