CGAL users discussion list

[Andrew Cunningham <>]

I am surprised no-one has pulled out a profiler. The following are the
top functions "bottom-up" when running your test case ( after
commenting out the per-loop std::cout functions). Processor 13th Gen
Intel(R) Core(TM) i7-13850HX, 2100 Mhz, 20 Core(s), 28 Logical
Processor(s)

Function CPU Time
std::this_thread::sleep_for<__int64,struct std::ratio<1,1000> > 91.174ms
malloc_base 17.495ms
free_base 9.611ms
CxxThrowException 8.341ms
std::deque<CGAL::Polygon_2<CGAL::Epeck,std::vector<CGAL::Point_2<CGAL::Epeck>,std::allocator<CGAL::Point_2<CGAL::Epeck>
> > >,std::allocator<CGAL::Polygon_2<CGAL::Epeck,std::vector<CGAL::Point_2<CGAL::Epeck>,std::allocator<CGAL::Point_2<CGAL::Epeck>
> > > > >::{dtor} 6.631ms

On Wed, Jan 10, 2024 at 1:28 PM Valentin Pi <> wrote:
>
> Hi Efi,
>
> Thank you very much for taking the time. I am glad to seemingly have 
> discovered some unnecessary overhead. I have tried the patch and your 
> snippet, as well as averaged the runtime over 10000 samples. For some 
> reason I now have ~400µs instead of 200µs for the first Minkowski sum, and 
> then the runtime gets quickly down to about 10µs with a i5-1135G7 2.40GHz 
> processor on my laptop. Since I suspected that this is due to caching or 
> some other system effects, I have now randomized the triangles (and renamed 
> them to triangles in the code, sorry for possible confusion) and introduced 
> a delay between each step of the loop. This gives the following source for 
> main.cpp.
>
> #include <CGAL/Polygon_2.h>
> #include <CGAL/Polygon_convex_decomposition_2.h>
> #include <CGAL/Polygon_nop_decomposition_2.h>
> #include <CGAL/Polygon_triangulation_decomposition_2.h>
> #include <CGAL/minkowski_sum_2.h>
> #include <CGAL/version_macros.h>
>
> #include <chrono>
> #include <iostream>
> #include <random>
> #include <thread>
> #include <vector>
>
> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
> typedef CGAL::Point_2<Kernel> Point;
> typedef CGAL::Polygon_2<Kernel> Polygon;
> typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes;
>
> using Container = std::vector<Point>;
> using Arr_segment_traits = CGAL::Arr_segment_traits_2<Kernel>;
> using Traits = CGAL::Gps_segment_traits_2<Kernel, Container, 
> Arr_segment_traits>;
>
> int main(int argc, char** argv) {
>     using std::vector;
>     using std::chrono::high_resolution_clock;
>     using namespace std::chrono_literals;
>
>     std::cout << CGAL_VERSION_STR << std::endl;
>
>     std::default_random_engine gen;
>     std::uniform_int_distribution<uint64_t> dist(0, 10000);
>     auto rand_coord = std::bind(dist, gen);
>     Traits traits;
>     size_t acc = 0;
>     size_t n = 1000;
>     for (int i = 0; i < n; i++) {
>         Polygon triangle_1;
>         Polygon triangle_2;
>         while (true) {
>             vector triangle_1_points({Point(rand_coord(), rand_coord()), 
> Point(rand_coord(), rand_coord()),
>                                       Point(rand_coord(), rand_coord())});
>             vector triangle_2_points({Point(rand_coord(), rand_coord()), 
> Point(rand_coord(), rand_coord()),
>                                       Point(rand_coord(), rand_coord())});
>             triangle_1 = Polygon(triangle_1_points.begin(), 
> triangle_1_points.end());
>             triangle_2 = Polygon(triangle_2_points.begin(), 
> triangle_2_points.end());
>             if (triangle_1.is_clockwise_oriented()) {
>                 triangle_1.reverse_orientation();
>             }
>             if (triangle_2.is_clockwise_oriented()) {
>                 triangle_2.reverse_orientation();
>             }
>             if (triangle_1.is_simple() && triangle_2.is_simple()) {
>                 break;
>             }
>         }
>         auto t1 = high_resolution_clock::now();
>         Polygon_with_holes result =
>             CGAL::minkowski_sum_2(triangle_1, triangle_2, 
> CGAL::Polygon_nop_decomposition_2<Kernel>(), traits);
>         auto t2 = high_resolution_clock::now();
>         std::cout << 
> std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() << 
> "µs" << std::endl;
>         acc += std::chrono::duration_cast<std::chrono::microseconds>(t2 - 
> t1).count();
>         if (i == 0) {
>             std::cout << acc << "µs" << std::endl;
>         }
>         std::this_thread::sleep_for(1ms);
>     }
>     const size_t avg = acc / n;
>     std::cout << avg << "µs" << std::endl;
>
>     return EXIT_SUCCESS;
> }
>
> Running this, I get about 600µs for the first Minkowski sum on the most 
> recent branch with the patch you provided me, as well as about 150µs on 
> average for each Minkowski sum. In our main project we get about 300µs for 
> each Minkowski sum. I suspect that allocations are slowing down the 
> Minkowski sum significantly, but I cannot prove it.
>
> Best
> Valentin
>
> Am 10.01.24 um 13:34 schrieb Efi Fogel ( via cgal-discuss 
> Mailing List):
>
> Hi Valentin,
>
> I've decided to look into it, cause the timings seemed odd, and I found a 
> few things.
>
> I'm running an i7 core clocked at 2.20GHz:
> cat /proc/cpuinfo  | grep 'name'| uniq
> model name : Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz
>
> I changed the single call to a loop and added the traits parameter.
> I get ~20us on average on my machine per minkowski sum.
> However, even with this I wasn't satisfied.
> It turns out that there is some overhead that consumes some unexplained 
> significant amount of time.
> Attached is a patch that avoids (some of) the overhead.
> It applies to 2 files:
> modified:   
> Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
> modified:   Minkowski_sum_2/include/CGAL/minkowski_sum_2.h
> It is based on the most recent version, so if the automatic application of 
> the patch fails for you, apply it manually. It is rather simple.
> Also, make sure to use the following snippet:
>
> using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
> using Point = CGAL::Point_2<Kernel>;
> using Container = std::vector<Point>;
> using Arr_segment_traits = CGAL::Arr_segment_traits_2<Kernel>;
> using Traits = CGAL::Gps_segment_traits_2<Kernel, Container, 
> Arr_segment_traits>;
> using Nop = CGAL::Polygon_nop_decomposition_2<Kernel, Container>;
> Traits traits;
> CGAL::minkowski_sum_by_decomposition_2(square_1, square_2, nop, traits);
>
> which knocks out almost ~2/3 of the computation time, and I get ~7us.
>
> Naturally, I'll continue to investigate the issue and fix the code base.
>
> Best,
> Efi
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
>
> On Tue, 9 Jan 2024 at 19:22, Valentin Pi <> wrote:
>>
>> You are right, I didn't try that yet. This cuts about 25µs of the runtime 
>> to about 175µs.
>>
>> Am 09.01.24 um 15:57 schrieb Efi Fogel ( via 
>> cgal-discuss Mailing List):
>>
>> If so, then use the decomposition Minkowski-sum method, with a nop 
>> decomposition operation; see 
>> https://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__nop__decomposition__2.html
>>
>> Try something like this:
>>
>> Polygon_with_holes result = CGAL::minkowski_sum_2(square_1, square_2, 
>> CGAL::Polygon_nop_decomposition_2<Kernel>());
>>
>>    ____  _        ____             _
>>   /_____/_) o    /__________  __  //
>>  (____ (   (    (    (_/ (_/-(-'_(/
>>                          _/
>>
>>
>>
>>
>> On Tue, 9 Jan 2024 at 12:58, Valentin Pi <> wrote:
>>>
>>> Yes, I just checked. Would be surprising to me if not, since there are 
>>> unique coordinates for each triangle in the code.
>>>
>>> Am 09.01.24 um 11:31 schrieb Efi Fogel ( via 
>>> cgal-discuss Mailing List):
>>>
>>> Do you have any guarantee about the input polygons being convex?
>>>    ____  _        ____             _
>>>   /_____/_) o    /__________  __  //
>>>  (____ (   (    (    (_/ (_/-(-'_(/
>>>                          _/
>>>
>>>
>>>
>>>
>>> On Tue, 9 Jan 2024 at 10:41, Valentin Pi <> wrote:
>>>>
>>>> Thanks for the quick reply.
>>>> 1. I have now tried a couple of versions, but only from the header-only 
>>>> versions. Denoted with the tag names each, I give the following table of 
>>>> observed average times. The numbers I gave initially were with v5.6, as 
>>>> already said.
>>>>
>>>> Release tag - Observed average runtime
>>>> 6.0-dev [1] - 200µs
>>>>        v5.6 - 200µs
>>>>        v5.5 - 185µs
>>>>        v5.4 - 275µs
>>>>        v5.3 - 300µs
>>>>        v5.2 - 275µs
>>>>        v5.1 - 250µs
>>>>
>>>> [1] The current version at commit 
>>>> a15af8ef645c414956640348d036609b9a0a5c38.
>>>>
>>>> I do not detect a degradation with any particular version, except for a 
>>>> slight jump from 275µs to 185µs between v5.4 and v5.5. For the 
>>>> complexity of the problem anything over a couple of µs is too much for 
>>>> our application, so all of these times are problematic for us. I could 
>>>> try older versions if you think it would make a difference.
>>>> 2. I have tried convolution (in v5.6) and it gives about the same time.
>>>>
>>>> Am 09.01.24 um 08:10 schrieb Efi Fogel ( via 
>>>> cgal-discuss Mailing List):
>>>>
>>>> 1. Have you measured it with a different version? I mean, are you 
>>>> detecting a degradation?
>>>> 2. Have you tried other implemented alg, or at least other decomposition 
>>>> methods?
>>>> The call without a decomposition method invokes the partial-convolution 
>>>> method, which is the most efficient in most cases:
>>>> CGAL::minkowski_sum_2(square_1, square_2);
>>>>    ____  _        ____             _
>>>>   /_____/_) o    /__________  __  //
>>>>  (____ (   (    (    (_/ (_/-(-'_(/
>>>>                          _/
>>>>
>>>>
>>>>
>>>>
>>>> On Tue, 9 Jan 2024 at 01:09, Valentin Pi <> wrote:
>>>>>
>>>>> Hello everyone,
>>>>>
>>>>> I hope this issue fits this list. In our current project we need to 
>>>>> compute a lot of small Minkowski sums, and I wanted to ask if someone 
>>>>> could please give me some help in speeding that process up. The 
>>>>> following CGAL program computing the Minkowski sum of two small 
>>>>> polygons demonstrates the problem.
>>>>>
>>>>> main.cpp:
>>>>>
>>>>> #include <CGAL/Polygon_2.h>
>>>>> #include <CGAL/Polygon_convex_decomposition_2.h>
>>>>> #include <CGAL/Polygon_triangulation_decomposition_2.h>
>>>>> #include <CGAL/minkowski_sum_2.h>
>>>>>
>>>>> #include <chrono>
>>>>> #include <iostream>
>>>>> #include <vector>
>>>>>
>>>>> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
>>>>> typedef CGAL::Point_2<Kernel> Point;
>>>>> typedef CGAL::Polygon_2<Kernel> Polygon;
>>>>> typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes;
>>>>>
>>>>> int main(int argc, char** argv) {
>>>>>     using std::vector;
>>>>>     using std::chrono::high_resolution_clock;
>>>>>
>>>>>     vector square_1_points({Point(0, 0), Point(4, 0), Point(4, 4)});
>>>>>     vector square_2_points({Point(2, 1), Point(3, 1), Point(3, 2)});
>>>>>     Polygon square_1(square_1_points.begin(), square_1_points.end());
>>>>>     Polygon square_2(square_2_points.begin(), square_2_points.end());
>>>>>     auto t1 = high_resolution_clock::now();
>>>>>     Polygon_with_holes result =
>>>>>         CGAL::minkowski_sum_2(square_1, square_2, 
>>>>> CGAL::Hertel_Mehlhorn_convex_decomposition_2<Kernel>());
>>>>>     auto t2 = high_resolution_clock::now();
>>>>>     std::cout << 
>>>>> std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() 
>>>>> << "µs" << std::endl;
>>>>>
>>>>>     return EXIT_SUCCESS;
>>>>> }
>>>>>
>>>>> CMakeLists.txt:
>>>>>
>>>>> cmake_minimum_required(VERSION 3.19.1)
>>>>> # SotMS: "Slowness of the Minkowski Sum"
>>>>> project(sotms)
>>>>> find_package(CGAL 5.6 REQUIRED COMPONENTS Core)
>>>>>
>>>>> add_compile_options(-O2)
>>>>> set(CMAKE_BUILD_TYPE Release)
>>>>>
>>>>> add_executable(sotms src/main.cpp)
>>>>> target_link_libraries(sotms CGAL::CGAL_Core)
>>>>>
>>>>> Compilation and execution (move the main.cpp in a folder named src and 
>>>>> the CMakeLists.txt in a folder above before):
>>>>>
>>>>> $ cd src
>>>>> $ cmake ..
>>>>> $ make -j
>>>>> $ ./sotms
>>>>>
>>>>> I have observed the following:
>>>>> 1. The execution times for CGAL::minkowski_sum_2 for the above program 
>>>>> lie around 200µs. This gives room for about 5000 Minkowski sums per 
>>>>> second, which is not a lot, given the complexity of the above problem.
>>>>> 2. In the main project we usually have runtimes of about 1500µs. In 
>>>>> some executions of our main project program the runtime jumps to 
>>>>> several seconds up to minutes, but I cannot reproduce that well yet.
>>>>> 3. Repeating the above code (by introducing a for loop wrapping around 
>>>>> the lines 23-27) yields runtimes of about 20µs, but I think this is due 
>>>>> to optimizations, but 20µs is still too much.
>>>>> 4. Disabling optimizations (-O0) gives runtimes of about 1000µs for the 
>>>>> first Minkowski sum, which then upon repetition of the computation 
>>>>> breaks down to about 200µs again for some reason.
>>>>>
>>>>> I have already tried changing the kernel to an inexact kernel, which 
>>>>> still gives poor performance and does not suit our use case, since it 
>>>>> often crashes. I am on an Arch Linux (x64) laptop, CGAL is compiled 
>>>>> with GMP and MPFR, everything is up to date. The CGAL version in the 
>>>>> Arch repository is 5.6
>>>>>
>>>>> Best
>>>>> Valentin
>>>>>
>>>>>
>>>>> --
>>>>> You are currently subscribed to cgal-discuss.
>>>>> To unsubscribe or access the archives, go to
>>>>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>>>>
>>>>
>>>> --
>>>> You are currently subscribed to cgal-discuss.
>>>> To unsubscribe or access the archives, go to
>>>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>>>
>>>>
>>>> --
>>>> You are currently subscribed to cgal-discuss.
>>>> To unsubscribe or access the archives, go to
>>>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>>>
>>>
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>>
>>>
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>>
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>