Performance question: `boost::geometry::intersection` seems not reserving vector's memory space for Section inside

[woodpenker]

We found that using boost::geometry::intersection will lead to a lot of _M_realloc_insert for std::vector. The callstacks may like this:

void std::vector<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul>, std::allocator<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul> > >::_M_realloc_insert<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul> const&>(__gnu_cxx::__normal_iterator<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul>*, std::vector<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul>, std::allocator<boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul> > > >, boost::geometry::section<boost::geometry::model::box<GPVec<double> >, 2ul> const&)
	void boost::geometry::detail::sectionalize::sectionalize_part<GPVec<double>, std::integer_sequence<unsigned long, 0ul, 1ul> >::apply<__gnu_cxx::__normal_iterator<GPVec<double> const*, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >, boost::geometry::detail::no_rescale_policy, boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>, boost::geometry::strategy::envelope::cartesian<void>, boost::geometry::strategy::expand::cartesian_segment>(boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>&, __gnu_cxx::__normal_iterator<GPVec<double> const*, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >, __gnu_cxx::__normal_iterator<GPVec<double> const*, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >, boost::geometry::detail::no_rescale_policy const&, boost::geometry::strategy::envelope::cartesian<void> const&, boost::geometry::strategy::expand::cartesian_segment const&, boost::geometry::ring_identifier, unsigned long)
	void boost::geometry::detail::sectionalize::sectionalize_range<(boost::geometry::closure_selector)1, false, GPVec<double>, std::integer_sequence<unsigned long, 0ul, 1ul> >::apply<Curve<GPVec<double> >, boost::geometry::detail::no_rescale_policy, boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>, boost::geometry::strategy::envelope::cartesian<void>, boost::geometry::strategy::expand::cartesian_segment>(Curve<GPVec<double> > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>&, boost::geometry::strategy::envelope::cartesian<void> const&, boost::geometry::strategy::expand::cartesian_segment const&, boost::geometry::ring_identifier, unsigned long)
	void boost::geometry::sectionalize<false, std::integer_sequence<unsigned long, 0ul, 1ul>, Curve<GPVec<double> >, boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>, boost::geometry::detail::no_rescale_policy, boost::geometry::strategy::envelope::cartesian<void>, boost::geometry::strategy::expand::cartesian_segment>(Curve<GPVec<double> > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::sections<boost::geometry::model::box<GPVec<double> >, 2ul>&, boost::geometry::strategy::envelope::cartesian<void> const&, boost::geometry::strategy::expand::cartesian_segment const&, int, unsigned long)
	void boost::geometry::detail::get_turns::get_turns_generic<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, false, false, boost::geometry::detail::get_intersection_points::get_turn_without_info<GPVec<double>, GPVec<double>, boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> > > >::apply<boost::geometry::strategy::intersection::cartesian_segments<void>, boost::geometry::detail::no_rescale_policy, std::deque<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> >, std::allocator<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> > > >, boost::geometry::detail::get_turns::no_interrupt_policy>(int, Curve<GPVec<double> > const&, int, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, boost::geometry::strategy::intersection::cartesian_segments<void> const&, boost::geometry::detail::no_rescale_policy const&, std::deque<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> >, std::allocator<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> > > >&, boost::geometry::detail::get_turns::no_interrupt_policy&)
	void boost::geometry::get_intersection_points<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, boost::geometry::detail::no_rescale_policy, std::deque<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> >, std::allocator<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> > > >, boost::geometry::strategy::intersection::cartesian_segments<void> >(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, boost::geometry::detail::no_rescale_policy const&, std::deque<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> >, std::allocator<boost::geometry::detail::overlay::turn_info<GPVec<double>, boost::geometry::segment_ratio<double>, boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, boost::array<boost::geometry::detail::overlay::turn_operation<GPVec<double>, boost::geometry::segment_ratio<double> >, 2ul> > > >&, boost::geometry::strategy::intersection::cartesian_segments<void> const&)
	boost::geometry::range::back_insert_iterator<std::vector<GPVec<double>, std::allocator<GPVec<double> > > > boost::geometry::detail::intersection::intersection_linestring_linestring_point<GPVec<double> >::apply<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, boost::geometry::detail::no_rescale_policy, boost::geometry::range::back_insert_iterator<std::vector<GPVec<double>, std::allocator<GPVec<double> > > >, boost::geometry::strategy::intersection::cartesian_segments<void> >(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::range::back_insert_iterator<std::vector<GPVec<double>, std::allocator<GPVec<double> > > >, boost::geometry::strategy::intersection::cartesian_segments<void> const&)
	bool boost::geometry::dispatch::intersection<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, boost::geometry::linestring_tag, boost::geometry::linestring_tag, false>::apply<boost::geometry::detail::no_rescale_policy, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, boost::geometry::strategy::intersection::cartesian_segments<void> >(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, boost::geometry::detail::no_rescale_policy const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > >&, boost::geometry::strategy::intersection::cartesian_segments<void> const&)
	bool boost::geometry::resolve_strategy::intersection::apply<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > >&, boost::geometry::default_strategy)
	bool boost::geometry::resolve_variant::intersection<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >::apply<std::vector<GPVec<double>, std::allocator<GPVec<double> > >, boost::geometry::default_strategy>(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > >&, boost::geometry::default_strategy const&)
	bool boost::geometry::intersection<Curve<GPVec<double> >, std::vector<GPVec<double>, std::allocator<GPVec<double> > >, std::vector<GPVec<double>, std::allocator<GPVec<double> > > >(Curve<GPVec<double> > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > > const&, std::vector<GPVec<double>, std::allocator<GPVec<double> > >&)

After reading the codes, I guess it may caused by Section at this line:

geometry/include/boost/geometry/algorithms/detail/overlay/get_turns.hpp

Line 533 in c011ebf

sections_type sec1, sec2;

.
Is it right and does we need to consider the reallocation performance cost?

[awulkiew]

What is the goal?
How did you discover that this may be an issue?
Could you describe why do you think this is the part of the algorithm that is troublesome?
Could you share your performance testing methodology?
Could you share an example of the data?
Etc.

My point is that depending on a use case various part of the algorithm are going to be slower or faster. I'm curious why do you think that reallocations are the cause of your problems if there are any.

Reallocations are of course bad in general so we could think about avoiding them. They are in push_backs:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/sections/sectionalize.hpp#L492
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/sections/sectionalize.hpp#L545
which use _M_realloc_insert
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h#L1287

If you're willing to do some testing:

Sectionalize is called here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/overlay/get_turns.hpp#L531-L539
Sections used there are defined here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/sections/sectionalize.hpp#L134

You can try deriving them from std::deque instead of std::vector.

Or you can try calling reserve(), e.g.:

sec1.reserve(geometry::num_points(geometry1) / 2);
sec2.reserve(geometry::num_points(geometry2) / 2);
// or use some other estimate