Menu ▾ ▴

#7 Improve octree performance

1.0
open
Václav Šmilauer
None
2016-03-31
2015-11-13
Václav Šmilauer
No

Based on Olli's report, there are performance issues when using octree with larger meshes. Based on his silicone2.xxx pickle and a short testing/profiling script (attached), the following profiling data were gathered (sorted by cumulative time, the first line is total test time; unpickling the field takes about 5s). The changes were merged in https://sourceforge.net/p/mupif/code/ci/5e6bcd3beaf44471f1e86ce3fb4fb8f5ffcdf6db/ .

@Olli, please test if you are getting a reasonable speedup, and whether some further tunin/rewriting would help you.

To use minieigen.AlignedBox3, do "apt-get install python-minieigen" (Debian/Ubuntu), "pip install minieigen" (Linux). For Windows, just skip it, unless you are fluent with distutils. Docs at http://eudoxos.github.io/minieigen/ , it is a wrapper around Eigen (http://eigen.tuxfamily.org).

The lookup itself seems to be quite fast (something like 10k/sec for small random bboxes), the initial localizer construction is quite slow (34s in the last version).

Cheers, Václav

original

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  145.422  145.422 <string>:1(<module>)
        1    0.018    0.018  145.422  145.422 octest.py:4(testOctree)
        1    0.589    0.589  138.229  138.229 Mesh.py:308(giveCellLocalizer)
    69994    0.043    0.000  122.429    0.002 Octree.py:240(insert)
3798050/69994    9.670    0.000  122.386    0.002 Octree.py:107(insert)
  3814658    2.628    0.000   61.938    0.000 Octree.py:101(containsBBox)
  1737460   21.848    0.000   51.911    0.000 Cell.py:109(getBBox)
 16228554    5.384    0.000   31.870    0.000 newrange.py:140(__iter__)
  3814659   11.890    0.000   30.634    0.000 Octree.py:87(giveMyBBox)
  3853331   10.458    0.000   28.938    0.000 BBox.py:67(intersects)
 16228554   17.207    0.000   26.486    0.000 newrange.py:149(__init__)
 16228554   21.680    0.000   25.157    0.000 newrange.py:37(__init__)
 54479486   11.447    0.000   16.439    0.000 newrange.py:155(next)

use minieigen.AlignedBox3

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  132.569  132.569 <string>:1(<module>)
        1    0.022    0.022  132.569  132.569 octest.py:4(testOctree)
        1    1.284    1.284  125.698  125.698 Mesh.py:308(giveCellLocalizer)
    69994    0.042    0.000  107.593    0.002 Octree.py:240(insert)
3798050/69994   10.477    0.000  107.552    0.002 Octree.py:107(insert)
  1741983   25.050    0.000   55.990    0.000 Cell.py:109(getBBox)
  3815090    3.084    0.000   42.533    0.000 Octree.py:101(containsBBox)
  3815091   17.479    0.000   36.392    0.000 Octree.py:87(giveMyBBox)
 12389602    4.201    0.000   25.086    0.000 newrange.py:140(__iter__)
 12389602   13.498    0.000   20.884    0.000 newrange.py:149(__init__)
 12389602   17.298    0.000   20.428    0.000 newrange.py:37(__init__)
 46279839   10.000    0.000   14.618    0.000 newrange.py:155(next)

cache Cell.bbox

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   78.486   78.486 <string>:1(<module>)
        1    0.021    0.021   78.486   78.486 octest.py:4(testOctree)
        1    0.904    0.904   73.277   73.277 Mesh.py:308(giveCellLocalizer)
    69994    0.032    0.000   68.863    0.001 Octree.py:240(insert)
3798050/69994   10.274    0.000   68.831    0.001 Octree.py:107(insert)
  3814786    2.934    0.000   42.534    0.000 Octree.py:101(containsBBox)
  3814787   17.946    0.000   36.620    0.000 Octree.py:87(giveMyBBox)
  7373065    2.418    0.000   14.832    0.000 newrange.py:140(__iter__)
  7373065    7.919    0.000   12.414    0.000 newrange.py:149(__init__)
  7373065   10.309    0.000   12.252    0.000 newrange.py:37(__init__)
 26213957    5.809    0.000    8.403    0.000 newrange.py:155(next)

cache Octant.bbox

  ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   39.334   39.334 <string>:1(<module>)
        1    0.021    0.021   39.334   39.334 octest.py:4(testOctree)
        1    0.890    0.890   34.235   34.235 Mesh.py:308(giveCellLocalizer)
    69994    0.029    0.000   29.840    0.000 Octree.py:243(insert)
3798050/69994    8.732    0.000   29.810    0.000 Octree.py:110(insert)
  3560426    1.216    0.000    7.061    0.000 newrange.py:140(__iter__)
  3560426    3.834    0.000    5.845    0.000 newrange.py:149(__init__)
  3813994    1.691    0.000    5.670    0.000 Octree.py:104(containsBBox)
1 Attachments
octest.py

Discussion

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-13
    • Description has changed:

    Diff:

    --- old
+++ new
@@ -3,6 +3,8 @@
 @Olli, please test if you are getting a reasonable speedup, and whether some further tunin/rewriting would help you.

 To use minieigen.AlignedBox3, do "apt-get install python-minieigen" (Debian/Ubuntu), "pip install minieigen" (Linux). For Windows, just skip it, unless you are fluent with distutils. Docs at http://eudoxos.github.io/minieigen/ , it is a wrapper around Eigen (http://eigen.tuxfamily.org).
+
+The lookup itself seems to be quite fast (something like 10k/sec for small random bboxes), the initial localizer construction is quite slow (34s in the last version).

 Cheers, Václav
     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-13

    Reporting some further improvements (results were not tested, but they seem to be correct). The following results do NOT include unpickling, so add 5s to make it commensurable with the above profiles:

    remove nested loops

    https://sourceforge.net/p/mupif/code/ci/43743999c32f1cfcd157a279c6de8ee6ce9e7878/

       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.967    0.967   23.406   23.406 build/bdist.linux-x86_64/egg/mupif/Mesh.py:308(giveCellLocalizer)
    69994    0.026    0.000   18.602    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:239(insert)
3798050/69994    3.260    0.000   18.576    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:118(insert)
   467979    2.903    0.000    9.523    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:66(childrenIJK)
  3814826    1.539    0.000    4.764    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:112(containsBBox)

    better cell bbox loop

    https://sourceforge.net/p/mupif/code/ci/5cd90e3b5a0a5423c982940e9d7c2859cf2169bc/

    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.150    0.150   20.493   20.493 build/bdist.linux-x86_64/egg/mupif/Mesh.py:308(giveCellLocalizer)
    69994    0.026    0.000   17.619    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:239(insert)
3800850/69994    3.227    0.000   17.593    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:118(insert)
   468259    2.498    0.000    8.763    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:66(childrenIJK)
  3817066    1.569    0.000    4.669    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:112(containsBBox)
  1620085    0.567    0.000    3.375    0.000 /usr/local/lib/python2.7/dist-packages/future-0.15.2-py2.7.egg/future/types/newrange.py:140(__iter__)
  1314078    1.623    0.000    3.098    0.000 build/bdist.linux-x86_64/egg/mupif/Cell.py:109(getBBox)

    use c++ mupif.fastOctant.Octant

    https://sourceforge.net/p/mupif/code/ci/ba933cdf82ba0004f44f1470a7c73f02af4def40/

       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.128    0.128    3.619    3.619 build/bdist.linux-x86_64/egg/mupif/Mesh.py:308(giveCellLocalizer)
  1321300    1.383    0.000    2.792    0.000 build/bdist.linux-x86_64/egg/mupif/Cell.py:109(getBBox)
    69994    0.488    0.000    0.918    0.000 build/bdist.linux-x86_64/egg/mupif/Octree.py:239(insert)

    In here, the hotspot (2.792s/3.619s) is calls to getBBox from within c++ for cells (it needs to go through python).

    As explained in README.md, fastOctant must be manually enabled in setup.py (useCxx=True) and will only work on Linux. Needs Eigen installed in /usr/include/eigen3 (that's what package managers do), boost_python and a compiler understanding -std=c++11.

    I did not test the result for correctness, but it is returning something quite sensible (a few hits for random boxes).

    Improved profiling script attached.

     

    Last edit: Václav Šmilauer 2015-11-13
    octest.py

  • Olli Tapaninen

    Olli Tapaninen - 2015-11-13

    I can see some nice improvement in speed in my code also:

    Original was about 1 hour:

    Original(On linux):
2015-11-13 11:14:57,877 - mmpraytracer -     INFO - Tracing successful!
2015-11-13 11:14:58,096 - mmpraytracer -    DEBUG - Converting point data (n=37078) to mesh (cells=69994)...
2015-11-13 12:12:14,144 - mmpraytracer -    DEBUG - Points not found to be in mesh: 397
2015-11-13 12:12:14,147 - mmpraytracer -    DEBUG - Post processing done!

    On the improved version(https://sourceforge.net/p/mupif/code/ci/009b1e460211bb85ec7562f47bf473a6cbd59d36/)
    about 7 minutes.

    Improved method(On linux):
2015-11-13 14:51:22,871 - mmpraytracer -     INFO - Tracing successful!
2015-11-13 14:51:23,051 - mmpraytracer -    DEBUG - Converting point data (n=37146) to mesh (cells=69994)...
2015-11-13 14:58:01,912 - mmpraytracer -    DEBUG - Points not found to be in mesh: 360
2015-11-13 14:58:01,914 - mmpraytracer -    DEBUG - Post processing done!
     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-13

    Olli, thanks. Are the new (faster) results correct, based your quick look at them? As said, I did not test the implementation (it is mostly 1:1 from python), but I am happy if it works.

    Did you encounter any problems installing minieigen or compiling the fastOctree module? It is something we would like to iron out before other people start using it.

     

  • Olli Tapaninen

    Olli Tapaninen - 2015-11-17

    I did not check the results yet. I had no problem in installing.

    Using the most recent FastOctant-C++ module I see so degredation in performance to 9 minutes.

    Fast Octant C++ extension (On Linux)
2015-11-17 10:21:48,227 - mmpraytracer -     INFO - Tracing successful!
2015-11-17 10:21:48,435 - mmpraytracer -    DEBUG - Converting point data (n=37387) to mesh (cells=69994)...
mupif.fast: using mupif.fastOctant
2015-11-17 10:30:50,830 - mmpraytracer -    DEBUG - Points not found to be in mesh: 325
2015-11-17 10:30:50,833 - mmpraytracer -    DEBUG - Post processing done!
     

  • Olli Tapaninen

    Olli Tapaninen - 2015-11-17

    Also FastOctant does not support pickling. Could this cause problems with Pyro4?

    RuntimeError: Pickling of "mupif.fastOctant.Octant" instances is not enabled (http://www.boost.org/libs/python/doc/v2/pickle.html)
     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-17

    Using the most recent FastOctant-C++ module I see so degredation in performance to 9 minutes.
    That means you see no improvement with the latest version? There can be 2 causes. Either the problem is 2d (for degenerate 3d, the non-fast variant is used, since FastOctant was not tested with that yet). Or you forgot to set useCxx=True in setup.py. If it is something else, I need more details.

    Pickling should definitely be supported, I will add it just now. The question coming to my mind is what happens if a machine without fastOctact unpickles fastOctact.Octant sent over the wire.

     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-17

    Alright, I commited pickling support for fastOctant.

    I think though that supporting the same pickle/unpickle interface for both Octant and fastOctant will be pain, and that mesh should really NOT transfer its own locator over the wire (it can be reconstructed locally, probably faster than transferred). For that, Mesh.__getstate__ would have to be defined, returning __dict__ without vertexLocalizer and cellLocalizer.

    Another option: make everybody using the platform have proper compiler & boost::python? Including those on Windows.

     

  • Olli Tapaninen

    Olli Tapaninen - 2015-11-17

    I think making everyone use compiler on windows is just painful. Even with mingw and msys2 there will be compatibility issues. I think your suggestion not to pickle the localizers is the best way to go.

     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-19

    (Field pickling fixed by Vit just now. Please open a separate ticket for new issues next time.)

     

  • Václav Šmilauer

    Václav Šmilauer - 2015-11-19

    For compiler under Windows: I've been using (rarely, fortunately) mingw-w64-compiled modules (also with boost::python) in MSVC (official) python builds, and there were no issues. But it was painful to set up, agreed.

     

  • Václav Šmilauer

    Václav Šmilauer - 2016-03-31

    A belated note to the discussion, localizers were made to be not pickled with Mesh long time ago. Are there some outstanding issues with this ticket? The one I can think of is supporting non-3d domains (like 2d or such) which will be represented as 3d with fastOctant. Is that a problem?

     

Log in to post a comment.

veeam logo