<div dir="ltr">On Sun, Nov 10, 2013 at 12:47 PM, Jed Brown <span dir="ltr"><<a href="mailto:jedbrown@mcs.anl.gov" target="_blank">jedbrown@mcs.anl.gov</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="im">Matthew Knepley <<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>> writes:<br>

> Okay, here is the clearly quadratic performance, and its in next. Build<br>
> SNES ex12 and run using<br>
><br>
> /PETSc3/petsc/petsc-dev/arch-c-opencl-opt-next/lib/ex12-obj/ex12 -run_type<br>
> perf -refinement_limit 0.00000625 -variable_coefficient field<br>
> -petscspace_order 1 -mat_petscspace_order 0 -show_initial 0 -show_solution<br>
> 0 -petscfe_type basic -log_summary -interpolate<br>
><br>
> -refinement_limit 0.000625     DMPlexInterpolate       4 1.0 1.7443e-02 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 12  0  0  0 24  12  0  0  0 24     0<br>
> -refinement_limit 0.0003125    DMPlexInterpolate       4 1.0 3.3111e-02 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 13  0  0  0 24  13  0  0  0 24     0<br>
> -refinement_limit 0.0000625    DMPlexInterpolate       4 1.0 2.3465e-01 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 21  0  0  0 24  21  0  0  0 24     0<br>
> -refinement_limit 0.00003125   DMPlexInterpolate       4 1.0 7.7508e-01 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 30  0  0  0 24  30  0  0  0 24     0<br>
> -refinement_limit 0.000015625  DMPlexInterpolate       4 1.0 2.7267e+00 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 42  0  0  0 24  42  0  0  0 24     0<br>
> -refinement_limit 0.0000078125 DMPlexInterpolate       4 1.0 1.0175e+01 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 58  0  0  0 24  58  0  0  0 24     0<br>
> -refinement_limit 0.00000625   DMPlexInterpolate       4 1.0 3.8912e+01 1.0<br>
> 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 72  0  0  0 24  72  0  0  0 24     0<br>
<br>
</div>Testing in optimized mode, I have<br>
<br>
-refinement_limit 0.00001<br>
DMPlexInterpolate       4 1.0 2.1803e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 56  0  0  0 24  56  0  0  0 24     0<br>
DMPlexStratify         9 1.0 2.0112e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 52  0  0  0 24  52  0  0  0 24     0<br>
DMPlexPreallocate       1 1.0 5.3650e-01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 6.0e+00 14  0  0  0 12  14  0  0  0 12     0<br>
DMPlexResidualFEM       1 1.0 5.6863e-01 1.0 3.54e+06 1.0 0.0e+00 0.0e+00 0.0e+00 15 54  0  0  0  15 54  0  0  0     6<br>
<br>
-refinement_limit 0.000005<br>
DMPlexInterpolate       4 1.0 9.0466e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 72  0  0  0 24  72  0  0  0 24     0<br>
DMPlexStratify         9 1.0 8.6705e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 69  0  0  0 24  69  0  0  0 24     0<br>
DMPlexPreallocate       1 1.0 1.0999e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 6.0e+00  9  0  0  0 12   9  0  0  0 12     0<br>
DMPlexResidualFEM       1 1.0 1.1739e+00 1.0 7.08e+06 1.0 0.0e+00 0.0e+00 0.0e+00  9 54  0  0  0   9 54  0  0  0     6<br>
<br>
-refinement_limit 0.0000025<br>
DMPlexInterpolate       4 1.0 3.9527e+01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 85  0  0  0 24  85  0  0  0 24     0<br>
DMPlexStratify         9 1.0 3.8794e+01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 83  0  0  0 24  83  0  0  0 24     0<br>
DMPlexPreallocate       1 1.0 2.1816e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 6.0e+00  5  0  0  0 12   5  0  0  0 12     0<br>
DMPlexResidualFEM       1 1.0 2.4221e+00 1.0 1.42e+07 1.0 0.0e+00 0.0e+00 0.0e+00  5 54  0  0  0   5 54  0  0  0     6<br>
<br>
These are coming from DMLabelSetValue(), which is O(N) when the point<br>
does not yet exist.  To insert/modify these entries with storage bounded<br>
by the number of points rather than the number of times you mutate them,<br>
either use a hash (perhaps compressing to sorted array later) or a tree.<br>
(The guy that wrote khash also wrote kbtree, which has the same<br>
interface, though it tends to use more memory and be slower.)<br></blockquote><div><br></div><div>I rewrote insertion for DMLabel to use the hash table, and convert to flat arrays after insertion. Now its all linear:</div>
<div><br></div><div><div>-refinement_limit 0.000625     DMPlexInterpolate       4 1.0 1.1356e-02 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01  9  0  0  0 24   9  0  0  0 24     0</div><div>-refinement_limit 0.0003125    DMPlexInterpolate       4 1.0 2.2995e-02 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01  9  0  0  0 24   9  0  0  0 24     0</div>
<div>-refinement_limit 0.0000625    DMPlexInterpolate       4 1.0 9.0071e-02 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01  9  0  0  0 24   9  0  0  0 24     0</div><div>-refinement_limit 0.00003125   DMPlexInterpolate       4 1.0 1.7823e-01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01  9  0  0  0 24   9  0  0  0 24     0</div>
<div>-refinement_limit 0.000015625  DMPlexInterpolate       4 1.0 3.7626e-01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01  9  0  0  0 24   9  0  0  0 24     0</div><div>-refinement_limit 0.0000078125 DMPlexInterpolate       4 1.0 8.7979e-01 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 11  0  0  0 24  11  0  0  0 24     0</div>
<div>-refinement_limit 0.00000625   DMPlexInterpolate       4 1.0 1.7574e+00 1.0 0.00e+00 0.0 0.0e+00 0.0e+00 1.2e+01 10  0  0  0 24  10  0  0  0 24     0</div><div><br></div><div>Time (sec):           1.275e-01      1.00000   1.275e-01</div>
<div>Time (sec):           2.476e-01      1.00000   2.476e-01</div><div>Time (sec):           9.859e-01      1.00000   9.859e-01</div><div>Time (sec):           1.993e+00      1.00000   1.993e+00</div><div>Time (sec):           4.032e+00      1.00000   4.032e+00</div>
<div>Time (sec):           8.257e+00      1.00000   8.257e+00</div><div>Time (sec):           1.674e+01      1.00000   1.674e+01</div></div><div><br></div><div>This should help Karl running his GPU test now :)</div><div><br>
</div><div>   Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<a href="https://github.com/attractivechaos/klib/blob/master/kbtree.h" target="_blank">https://github.com/attractivechaos/klib/blob/master/kbtree.h</a><br>
<br>
<br>
If you run in a debugger, you'll find that your stack is pretty much always here:<br>
<br>
(gdb) bt<br>
#0  0x00007ffff51314be in __memmove_ssse3_back () from /usr/lib/libc.so.6<br>
#1  0x00007ffff751bca4 in PetscMemmove (a=0x26a0030, b=0x26a002c, n=979520) at src/sys/utils/memc.c:94<br>
#2  0x00007ffff78f51b6 in DMLabelSetValue (label=0x4529b0, point=404548, value=<optimized out>) at src/dm/impls/plex/plexlabel.c:279<br>
#3  0x00007ffff78ad27f in DMPlexStratify (dm=0x429350) at src/dm/impls/plex/plex.c:1440<br>
#4  0x00007ffff78e8b63 in DMPlexInterpolateFaces_Internal (cellDepth=<error reading variable: Cannot access memory at address 0x2>, dm=<optimized out>, idm=<optimized out>) at src/dm/impls/plex/plexinterpolate.c:290<br>

#5  DMPlexInterpolate (dm=0x428370, dmInt=0x7fffffffbda0) at src/dm/impls/plex/plexinterpolate.c:331<br>
#6  0x00007ffff78a629a in DMPlexCreateFromCellList (comm=<optimized out>, dim=<optimized out>, numCells=262144, numVertices=131585, numCorners=<optimized out>, interpolate=<optimized out>, cells=<optimized out>, spaceDim=40501292, vertexCoords=0x26ac3a4, dm=0x7fffffffc520) at src/dm/impls/plex/plexcreate.c:945<br>

#7  0x00007ffff78ba14d in DMPlexRefine_Triangle (dm=<optimized out>, maxVolumes=0x42e9f0, dmRefined=0x7fffffffc520) at src/dm/impls/plex/plex.c:3639<br>
#8  0x00007ffff78baae0 in DMRefine_Plex (dm=0x42cb40, comm=40501292, dmRefined=0x7fffffffc520) at src/dm/impls/plex/plex.c:4313<br>
#9  0x00007ffff791d9cc in DMRefine (dm=0x42cb40, comm=40501292, dmf=0x7fffffffc520) at src/dm/interface/dm.c:1498<br>
#10 0x0000000000404c64 in CreateMesh (comm=1140850688, user=0x7fffffffc608, dm=0x7fffffffd740) at /home/jed/petsc/src/snes/examples/tutorials/ex12.c:311<br>
#11 0x0000000000406e60 in main (argc=21, argv=0x7fffffffd858) at /home/jed/petsc/src/snes/examples/tutorials/ex12.c:648<br>
<br>
<br>
<br>
<br>
DMPlexStratify also calls ISGetIndices, but forgets ISRestoreIndices.<br>
</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>