Triangulation_data_structure (dim d) speed enhancements

[mglisse]

Building a triangulation (for instance Triangulation for points on a sphere in dim 5, where every insertion is outside the convex hull) spends a lot of time in TDS operations, even when the dimension is fixed at compile-time (for dynamic dimension, see #8044). This issue is here to list ideas to speed it up (the list may evolve).

• Use TDS_full_cell_mirror_storage_policy by default (except maybe for dynamic dimension?) (mentioned in [[no_unique_address]] to compact Triangulation_ds_full_cell #8045)
• Replace queue<T> by stack<T>, or even stack<T,vector<T>> (most places don't seem to care about the order)
• clear_visited_marks: instead of walking through the graph again, maybe we could store the cells in a vector when we mark them, so it is easy to clear them all afterwards?
• we spend quite a bit of time testing if vertices are infinite, try to avoid calling is_infinite on a cell when we could find out by testing one specific vertex (Outside_convex_hull_traversal_predicate?). Investigate if we could force the infinite vertex to be always in first position in the vertices of a cell, to limit the required tests. (mentioned in Use 'if' rather than % #8027)
• insert_in_tagged_hole: we spend a lot of time around while (!is_boundary_facet(rot)) and rotate_rotor. A comment says this is the "easy" way, so maybe there is a faster way?

[afabri]

Concerning the clear_visited_marks() would it make sense to have a Full_cell_handle in the tds_data so that they form a list? Bigger than a char, currently used to mark as visited, but it avoids allocation (for 100K points on a perturbed sphere we visit 300-500 cells).

[afabri]

Is the queue better than a stack because it will be less filled?

[mglisse]

Is the queue better than a stack because it will be less filled?

Stack is faster, because it is easier to add and remove elements at the same extremity of the container, than it is to add elements on one side and remove them on the other. Plus, it allows changing deque to vector, which is faster.

I am not familiar enough with the algorithm to know if the order of queue or stack ends up filling more/less, or has more memory locality, or some other advantage. This is kind of like BFS vs DFS for a graph traversal. Best I can suggest is benchmarking, and on the only example I tried stack was faster...

[mglisse]

Concerning the clear_visited_marks() would it make sense to have a Full_cell_handle in the tds_data so that they form a list? Bigger than a char, currently used to mark as visited,

That's a possibility. Depending on what else is in the object (mirror index?), it may or not increase the size. Since we still need to check quickly if a cell has been visited, we would need

• a special value for "not visited" -> use the null / default constructed handle?
• a value for "visited and here is the next visited" -> just use that handle/pointer
• a value for "visited and this is the last one" -> make it point to itself? or to the first visited? or something else?

but it avoids allocation (for 100K points on a perturbed sphere we visit 300-500 cells).

I was thinking of adding a member vector<Full_cell_handle> visited; to Triangulation (visitation by marking cells is not reentrant or thread-safe anyway). It would be allocated the first time, but then it would be clear()ed and reused, so allocations wouldn't affect the running time. This seems simpler, and possibly a bit faster, than the linked list you suggest, although that's just my intuition (while I quickly checked that the first 2 items of the list seemed to speed things up, the rest is speculative).

[afabri]

I gave it a try with a thread local static variable. A data member is probably better, as one can then offer a clear function.

[afabri]

Note that the queue could also be replaced by a local variable to avoid the allocations

[afabri]

Concerning"try to avoid calling is_infinite on a cell" : Can we not add logic to set_vertex(i, v) which keeps track if the cell is finite or not?

[mglisse]

Concerning"try to avoid calling is_infinite on a cell" : Can we not add logic to set_vertex(i, v) which keeps track if the cell is finite or not?

We could probably store a boolean in each cell saying if it is infinite (though it may require some changes because TDS itself doesn't know anything about infinite vertices). That's starting to look rather specialized though, enlarging all cells for something which may only benefit people abusing Triangulation to compute convex hulls (but maybe there is extra space in cells that can be used without increasing the size, and maybe it also benefits "normal" uses of Triangulation, I don't know).

[afabri]

Maybe to start with, how and where did you observe the expensive or too many is infinite tests of full cells?

[mglisse]

Maybe to start with, how and where did you observe the expensive or too many is infinite tests of full cells?

Probably by profiling (linux perf) a benchmark that did the same thing as yours. Sorry, I don't have anything more precise to say. It could also be related to the last item, testing if we are on the boundary probably involves looking for the infinite vertex.