Benchmarks

[msokalski]

Hi!
Today I made benchmarks comparing CDT, Delabella (DLB) and Delaunator (DEL) performance.
(Yep, no Jonathan Richard Shewchuk's Triangle this time, sorry).

Interesting observations:

• CDT's duplicates removal / edge indices mapping speed drops significantly when number of points >= 1M.
• Erasing super-triangle (ES) is sometimes more expensive than erasing outer faces and holes (FF) in CDT.
• DLB's triangulation performance improves when shifting entire point cloud away from (0,0).
• DEL becomes unreliable and insanely slow on asymmetric distributions (i.e. gamma).

I'm also very curious how much DCT's performance would benefit from using lighter containers and directly linking faces with vertices and neighbor faces using pointers instead of indices.

Attached timing results and screenshots of input distributions. If you're interested in obtaining input files (in CDT's visualizer format), drop me a note.
bench.zip

Here's zoomed in sample output (constraint edges are triangulation of input's random subset):

[artem-ogre]

Neat and thanks for sharing! I’ll take a closer look when I’m back at the keyboard. Could you share the benchmarks code somehow?

[msokalski]

No problem, but it's ugly has heck.
https://github.com/msokalski/delabella/blob/IDelaBella3/delabella-sdl2.cpp#L2471
I didn't consider, anyone would look into it :) requires uncommenting bench_* things tho.

[msokalski]

Hi @artem-ogre !
There's option for randomized or 'as is goes' vertices insertion order in CDT.
Have you investigated other orderings that could theoretically speed up triangulation like in this paper:
https://www.researchgate.net/publication/257505494_A_new_insertion_sequence_for_incremental_Delaunay_triangulation
Any thoughts / conclusions?

[msokalski]

You're welcome. BTW, how do you produce such nice SVG flamegraphs?
Is this also possible on windows?

[artem-ogre]

You're welcome. BTW, how do you produce such nice SVG flamegraphs? Is this also possible on windows?

I am using google perftools in combination with Brendan Gregg's FlameGraph scripts.
I also had success using it with perf. It should also work with other profiles and it looks like Visual Studio profiles are supported.
Let me know if you are interested in some particular details.

[msokalski]

Thank you

[artem-ogre]

Hi, @msokalski, I finally managed to do the final bug fixing and merged the new insertion sequence. Thank you for your suggestion and help!
I also took the liberty to add you to the contributors list in README.

[msokalski]

Oh! Hi @artem-ogre .
I'm so glad you managed to finalize this part. 🎖 I've noticed latest activity on your project but I didn't expect you adding me to the contributors, thanks!
I should have some time for testing / benchmarking in second half of March, currently I'm quite busy with other boring things.

[artem-ogre]

Hi @msokalski,
No, I did not investigate other options and I was not aware of this paper.

My gut feeling is that by itself it will likely not provide significant speedups on most of the real-world data. But it is definitely an interesting topic to investigate and benchmark.

[msokalski]

Hey @artem-ogre,
I've added benchmark charts to my repo including your CDT timings. If you're interested it's here: https://github.com/msokalski/delabella/blob/master/bench/bench.md
Interestingly, CDT performance seams to be almost insensitive to the input points, it runs as a tank :)

[artem-ogre]

@msokalski Thanks! :) It is great to have snippets to reproduce inputs too.
As for performance, it’s a pity that it seems to not be that fast (comparatively) but asymptotically things are looking good.

Maybe switching from vertex lists to something like half-edge and pre-calculating kd-tree can give a good boost. It would be great to get some time for profiling/optimization. What are your thoughts on constant factor difference? Is there something you do differently?

[msokalski]

I'm glad you like it. I've observed slightly better performance of CDT on linux, where heap management is a bit lighter than on windows so maybe, at least partially, it's matter of allocators used in std::vector or so, especially on small number of points (100-10K).

Kd style pre-sorting helped me to overcome poor performance in edge cases like for Symmetry or Circle (it was terrible with original algorithm pre-sorting with X^2+Y^2 comparator) but It didn't speed up anything in general, actually it slowed down initial phase significantly.

Main difference I can see is probably the locator, I don't have it :) If I'm right, you use it for locating already inserted point nearby currently being inserted one? In contrast I lookup triangles from youngest to oldest assuming (requiring) vertices were pre-sorted nicely so with high probability latest triangle contains a point which is close to the current point being inserted.

Finally it's hard to tell if that constant factor would hold for other test cases, I've spent some time optimizing my code just on those tests and ended up with quite opposite pre-sorting order than in the paper I post you a link.