memory hungry straightSkeleton

[strk]

As reported in Oslandia/SFCGAL#118 I've a polygon with ~14k vertices in 362 rings (4.5K vertices in the shall, the others all in holes) that make the straightSkeleton computer use up to 16GB of RAM. This may or may not be expected, but I hadn't found documentation of space complexity for the CGAL algorithm.

@fcacciola is there any way to predict the amount of memory needed for a given input ?

[strk]

Adding some debugging lines I find this:

straightSkeleton with EPIC kernel computed, has:
 80694/18446744073709551615 half edges
 13089/18446744073709551615 faces
 26898/18446744073709551615 vertices
 7950392/7950392 bytes

I'm don't know what those huge numbers (18446....) mean, they are printed feeding capacity_of_{halfedges,faces,vertices}() to std::cout.

[strk]

The final "bytes" report is sk->bytes() and sk->bytes_reserved()

[strk]

I've found bytes_reserved to just be a proxy to bytes():

    std::size_t bytes_reserved() const { return bytes();}          
HalfedgeDS/include/CGAL/HalfedgeDS_list.h:700

[strk]

Ok and max_size is std::list::max_size, so just a theoretical limit of the addressing of memory itself: http://www.cplusplus.com/reference/list/list/max_size/

So we theoretically have ~8MB of size for the half-edges, faces and vertices elements of the straight skeleton, but empirically the process eats up to 16GB, where else could the memory be ? Could it be boost internal caches ?

[strk]

Valgrind (massif tool) reports total memory to be under 500MB:

    MB
448.2^                                                            :           
     |                                                         @@@#::::::@::::
     |                                                      @@@@@@#::::::@::::
     |                                                    @@@@@@@@#::::::@::::
     |                                                 @@@@@@@@@@@#::::::@::::
     |                                              @::@@@@@@@@@@@#::::::@::::
     |                                           :@@@: @@@@@@@@@@@#::::::@::::
     |                                        @@@:@@@: @@@@@@@@@@@#::::::@::::
     |                                     @@@@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                                  @@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                                ::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                             @@:::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                          @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                       @@@@@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                     @@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |                  @@@@@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |              @@@@@@@@@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |           @@@@@ @@@@@@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |         @@@@ @@ @@@@@@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
     |      @@@@@@@ @@ @@@@@@@@ @@@@ :::@@@@ @@@@:@@@: @@@@@@@@@@@#::::::@::::
   0 +----------------------------------------------------------------------->Gi
     0                                                                   36.19

Some stats about the last snapshot:

91.00% (425,241,756B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->52.92% (247,292,496B) 0x53ADAFF: CGAL::CGAL_SS_i::SS_converter<CGAL::Cartesian_converter<CGAL::Epick, CGAL::Epick, CGAL::NT_converter<double, double> > >::cvt_trisegment(boost::intrusive_ptr<CGAL::CGAL_SS_i::Trisegment_2<CGAL::Epick> > const&) const (Straight_skeleton_builder_traits_2_aux.h:462)
| ->52.92% (247,292,496B) 0x53C2810: boost::intrusive_ptr<CGAL::CGAL_SS_i::Trisegment_2<CGAL::Epick> > CGAL::CGAL_SS_i::Exceptionless_filtered_construction<CGAL::CGAL_SS_i::Construct_ss_trisegment_2<CGAL::Epick>, CGAL::CGAL_SS_i::Construct_ss_trisegment_2<CGAL::Simple_cartesian<CGAL::Gmpq> >, CGAL::CGAL_SS_i::Construct_ss_trisegment_2<CGAL::Epick>, CGAL::CGAL_SS_i::SS_converter<CGAL::Cartesian_converter<CGAL::Epick, CGAL::Simple_cartesian<CGAL::Gmpq>, CGAL::NT_converter<double, CGAL::Gmpq> > >, CGAL::CGAL_SS_i::SS_converter<CGAL::Cartesian_converter<CGAL::Epick, CGAL::Epick, CGAL::NT_converter<double, double> > >, CGAL::CGAL_SS_i::SS_converter<CGAL::Cartesian_converter<CGAL::Simple_cartesian<CGAL::Gmpq>, CGAL::Epick, CGAL::NT_converter<CGAL::Gmpq, double> > >, CGAL::CGAL_SS_i::SS_converter<CGAL::Cartesian_converter<CGAL::Epick, CGAL::Epick, CGAL::NT_converter<double, double> > >, true>::operator()<CGAL::Segment_2<CGAL::Epick>, CGAL::Segment_2<CGAL::Epick>, CGAL::Segment_2<CGAL::Epick> >(CGAL::Segment_2<CGAL::Epick> const&, CGAL::Segment_2<CGAL::Epick> const&, CGAL::Segment_2<CGAL::Epick> const&) const (Straight_skeleton_builder_traits_2_aux.h:499)
| | ->52.83% (246,854,160B) 0x53CC75E: CGAL::Straight_skeleton_builder_2<CGAL::Straight_skeleton_builder_traits_2<CGAL::Epick>, CGAL::Straight_skeleton_2<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> >, CGAL::Dummy_straight_skeleton_builder_2_visitor<CGAL::Straight_skeleton_2<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> > > >::CollectSplitEvent(CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::Straight_skeleton_vertex_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> >, CGAL::Point_2<CGAL::Epick>, double> >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::Straight_skeleton_vertex_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> >, CGAL::Point_2<CGAL::Epick>, double> > > >, CGAL::CGAL_SS_i::Triedge<CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_halfedge<CGAL::Straight_skeleton_halfedge_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> >, CGAL::Segment_2<CGAL::Epick> > >, std::allocator<CGAL::HalfedgeDS_in_place_list_halfedge<CGAL::Straight_skeleton_halfedge_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator<int> >, CGAL::Segment_2<CGAL::Epick> > > > > > const&) (Straight_skeleton_builder_2.h:354)

[strk]

why invalid ?

[strk]

I see 16GB used by the system monitor. Not sure where they come from, but they are taken up before the end of skeleton construction. Could be boost caches ? If so, any idea about how to disable them ?

[fcacciola]

Hello. Sorry for the late response but I just got back from a bussiness trip to Detroit.

This large memory consumption might be expected, and the "culprit" would be the priority-queue that is used to hold all potential events. Roughly speaking the algorithm requires quadratric storage (it isn't exactly that but close). Unlike many other geometric algorithms, this need to compute ALL potential split events for each reflex vertex and store them all in a priority queue. Almost ALL edges would have a potential split again any reflex vertex, so, we are facing an upper bound around of 10K x 10K split events on the PQ (that's estimating that 10K of the vertices are reflex and 10K of the edges produce a potential split event). On top of that add the space used to compute about 14K edge-events, plus all skeleton nodes, halfedges and faces (this part is signigicantly less memory consuming that the events PQ).
Furthermore, each of these objects (vertices, halfedges, faces, events, etc...) go to (and are removed from) the heap which produces memory fragmentation leading to a RAM consumption not directly reflecting the amount of bytes objetively used.
While there are several thecniques that can be used to deal with this, none of them have been implemented in the CGAL code.

[sgiraudot]

According to this explanation, this memory usage is expected and not a bug (although I understand this might be a limitation of the algorithm). I am closing the issue, please open a pull request if a better solution that requires less memory can be proposed.