The principal computational cost of the main loop is due to fine-grained memory allocations. These allocations are generally in the clip and split procedures that allocate new GeneralPolytope at each execution.
In order to reduce these allocations, it may be convenient to add an optional cache to clip and split. The caches must be created outside the main loop of subtriangulate. We need to take into account that the number of polytopes per background cell is not bounded. Thus, the cache is indeed an array of caches.
Additionally, it is convenient to eliminate the recursivity of decompose using a stack instead.
We note that this is a major refactoring of the code that involve many procedures. In addition, before proceeding, an extensive profiling should be done to identify other memory allocations.
The principal computational cost of the main loop is due to fine-grained memory allocations. These allocations are generally in the
clipandsplitprocedures that allocate newGeneralPolytopeat each execution.In order to reduce these allocations, it may be convenient to add an optional cache to
clipandsplit. The caches must be created outside the main loop ofsubtriangulate. We need to take into account that the number of polytopes per background cell is not bounded. Thus, the cache is indeed an array of caches.Additionally, it is convenient to eliminate the recursivity of
decomposeusing a stack instead.We note that this is a major refactoring of the code that involve many procedures. In addition, before proceeding, an extensive profiling should be done to identify other memory allocations.