eraseSuperTriangle is slow #84
Comments
|
Hello, @msokalski, and thanks for creating the issue. This is a very interesting find, and I will look into it when I get some spare time. |
|
Here are some profiling data. Code: namespace
{
template <typename T>
Vertices<T> genData(const std::size_t size)
{
Vertices<T> vv;
vv.reserve(size + 1);
vv.push_back(V2d<T>::make(0, 1e-15));
const std::array<T, 2> range = {-1, 1};
std::uniform_real_distribution<T> unif(range[0], range[1]);
std::default_random_engine re;
for(std::size_t i = 0; i < size; ++i)
vv.push_back(V2d<T>::make(unif(re), 0));
return vv;
}
} // namespace
TEST_CASE("For_profiling_100k", "")
{
const auto vv = genData<double>(1e5);
auto cdt = Triangulation<double>();
cdt.insertVertices(vv);
cdt.eraseSuperTriangle();
}Flamegraph: flamegraph_100k.zip
|
|
Flamegraph for 1M points: flamegraph_1m.zip |
|
@msokalski |
ProfilingBeforeAfter |
|
Excellent boost! Thank you. before: after: |
- Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be done with new `calculateTrianglesByVertex` helper - Detect if triangulation was finalized and throw exceptions if it was when adding new vertices or edges
|
@msokalski |
|
after after: Well well, excellent job! Thanks. |
- Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be done with new `calculateTrianglesByVertex` helper - Detect if triangulation was finalized and throw exceptions if it was when adding new vertices or edges
- Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be done with new `calculateTrianglesByVertex` helper - Detect if triangulation was finalized and throw exceptions if it was when adding new vertices or edges
|
@msokalski |
|
Thank you! |
|
@msokalski |
|
New issue works as well |
I'm very happy with a stability and overall performance of CDT, great job!
The only one pitfall I'm suffering from is a performance of
eraseSuperTriangle().Looks like its time complexity grows quadratically with number of triangles it actually has to remove.
I think it's worth looking into it for optimization possibilities.
Please find below my experiment results:
My 'malicious' data set is many many points spread along X axis (x=[+1..-1], y=0), and 1 point just tiny bit above them all (x=0, y=1.E-15).
100K points:
1M points:
10M points:
The text was updated successfully, but these errors were encountered: