Triangulation_data_structure overhead with Dynamic_dimension_tag

[mglisse]

Using the Triangulation package with Dynamic_dimension_tag has a lot of overhead compared to Dimension_tag for the same dimension, and it would be helpful to reduce it. I've seen people instantiate the code with all fixed dimensions up to 10 and only fall back to dynamic for 11+, all behind a big switch...

I am just writing some notes here about possible improvements in TDS.

For a fixed dimension, everything is rather compact. We put full cells and vertices in a Compact_container, and each full cell contains 2-3 arrays, so there are hardly any allocations and few indirections. For a dynamic dimension, each full cell now contains 2-3 vectors, where each vector is already 3 pointers plus the heap-allocated buffers that actually contain the neighbors/vertices.
This is convenient for the implementation, we just have to switch between std::array and std::vector, and everything works the same. However, it is not so great for memory and performance.

1. std::vector is a great generic tool, but we do not need resize, etc, so the "capacity" pointer (or integer depending on the implementation) is just overhead. Even the "size" pointer is redundant since the 2 vectors have the same size, we could replace 2 vectors with one int (dimension) and 2 pointers (maybe unique_ptr). We could even drop the dimension, callers should always know it, although that means changing the interface a bit. We could also do a single allocation for neighbors+vertices(+mirror indexes) to reduce the overhead. Getting that right in all cases can be a bit tricky, but since here Vertex_handle and Full_cell_handle are both pointers (same size and alignment) it should be easy.
   We do a lot of allocations of buffers of the same size, so a specialized (pool?) allocator should work better than malloc+free.

2. (ignoring Compact_container) The overhead of allocating memory to store the neighbors could also be handled by... not allocating, i.e. including the neighbors directly in the Full_cell (as in the case of static dimension). One option for this would be to consider an upper bound on interesting dimensions, add a fixed-size buffer to Full_cell, and use only the part we need (similar to static_vector). Less wasteful would be a similar idea to C's flexible array member. That is, every time we create a Full_cell, we would actually allocate sizeof(Full_cell)+2*d*sizeof(void*), and the cell would know that its buffers immediately follow it in memory. This means that a cell can never be created by Full_cell c(...); but only through a factory function or a careful use of placement new. This now requires quite some changes in the interface, and does not work with Compact_container which expects "regular" objects. Care is also needed to include TDS_data and user data in the full cell.

3. Compact_container requires to know at compile-time the size of the objects it will hold. However, AFAIU, nothing in its implementation really needs that property. Providing a size during construction, storing it, and using it as a multiplier when incrementing pointers or allocating, would complicate the code but seems relatively straightforward. The result would be that the Compact_container would have exactly the same content as it currently does for a fixed dimension.

I don't think many people write their own implementation following the concept of Full_Cell, at most they instantiate it with their own data type, so a breaking change may not be that bad.

I am unlikely to implement all that for now (maybe parts of 1), but I am happy to discuss if someone is motivated.

Of course there is also overhead in the geometry part (points stored as vectors instead of arrays, not using static filters, etc), but that's a separate issue.