Performance question: `boost::geometry::intersection` seems not reserving vector's memory space for Section inside
- Dominant language
- C++
- Stars
- 517
- Forks
- 232
- PR merge metrics
- No merged PRs in 30d
Description
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 >, 2ul>, std::allocator >, 2ul> > >::_M_realloc_insert >, 2ul> const&>(__gnu_cxx::__normal_iterator >, 2ul>*, std::vector >, 2ul>, std::allocator >, 2ul> > > >, boost::geometry::section >, 2ul> const&)
void boost::geometry::detail::sectionalize::sectionalize_part, std::integer_sequence >::apply<__gnu_cxx::__normal_iterator const*, std::vector, std::allocator > > >, boost::geometry::detail::no_rescale_policy, boost::geometry::sections >, 2ul>, boost::geometry::strategy::envelope::cartesian, boost::geometry::strategy::expand::cartesian_segment>(boost::geometry::sections >, 2ul>&, __gnu_cxx::__normal_iterator const*, std::vector, std::allocator > > >, __gnu_cxx::__normal_iterator const*, std::vector, std::allocator > > >, boost::geometry::detail::no_rescale_policy const&, boost::geometry::strategy::envelope::cartesian 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, std::integer_sequence >::apply >, boost::geometry::detail::no_rescale_policy, boost::geometry::sections >, 2ul>, boost::geometry::strategy::envelope::cartesian, boost::geometry::strategy::expand::cartesian_segment>(Curve > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::sections >, 2ul>&, boost::geometry::strategy::envelope::cartesian const&, boost::geometry::strategy::expand::cartesian_segment const&, boost::geometry::ring_identifier, unsigned long)
void boost::geometry::sectionalize, Curve >, boost::geometry::sections >, 2ul>, boost::geometry::detail::no_rescale_policy, boost::geometry::strategy::envelope::cartesian, boost::geometry::strategy::expand::cartesian_segment>(Curve > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::sections >, 2ul>&, boost::geometry::strategy::envelope::cartesian const&, boost::geometry::strategy::expand::cartesian_segment const&, int, unsigned long)
void boost::geometry::detail::get_turns::get_turns_generic >, std::vector, std::allocator > >, false, false, boost::geometry::detail::get_intersection_points::get_turn_without_info, GPVec, boost::geometry::detail::overlay::turn_info, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> > > >::apply, boost::geometry::detail::no_rescale_policy, std::deque, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> >, std::allocator, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> > > >, boost::geometry::detail::get_turns::no_interrupt_policy>(int, Curve > const&, int, std::vector, std::allocator > > const&, boost::geometry::strategy::intersection::cartesian_segments const&, boost::geometry::detail::no_rescale_policy const&, std::deque, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> >, std::allocator, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> > > >&, boost::geometry::detail::get_turns::no_interrupt_policy&)
void boost::geometry::get_intersection_points >, std::vector, std::allocator > >, boost::geometry::detail::no_rescale_policy, std::deque, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> >, std::allocator, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> > > >, boost::geometry::strategy::intersection::cartesian_segments >(Curve > const&, std::vector, std::allocator > > const&, boost::geometry::detail::no_rescale_policy const&, std::deque, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> >, std::allocator, boost::geometry::segment_ratio, boost::geometry::detail::overlay::turn_operation, boost::geometry::segment_ratio >, boost::array, boost::geometry::segment_ratio >, 2ul> > > >&, boost::geometry::strategy::intersection::cartesian_segments const&)
boost::geometry::range::back_insert_iterator, std::allocator > > > boost::geometry::detail::intersection::intersection_linestring_linestring_point >::apply >, std::vector, std::allocator > >, boost::geometry::detail::no_rescale_policy, boost::geometry::range::back_insert_iterator, std::allocator > > >, boost::geometry::strategy::intersection::cartesian_segments >(Curve > const&, std::vector, std::allocator > > const&, boost::geometry::detail::no_rescale_policy const&, boost::geometry::range::back_insert_iterator, std::allocator > > >, boost::geometry::strategy::intersection::cartesian_segments const&)
bool boost::geometry::dispatch::intersection >, std::vector, std::allocator > >, boost::geometry::linestring_tag, boost::geometry::linestring_tag, false>::apply, std::allocator > >, boost::geometry::strategy::intersection::cartesian_segments >(Curve > const&, std::vector, std::allocator > > const&, boost::geometry::detail::no_rescale_policy const&, std::vector, std::allocator > >&, boost::geometry::strategy::intersection::cartesian_segments const&)
bool boost::geometry::resolve_strategy::intersection::apply >, std::vector, std::allocator > >, std::vector, std::allocator > > >(Curve > const&, std::vector, std::allocator > > const&, std::vector, std::allocator > >&, boost::geometry::default_strategy)
bool boost::geometry::resolve_variant::intersection >, std::vector, std::allocator > > >::apply, std::allocator > >, boost::geometry::default_strategy>(Curve > const&, std::vector, std::allocator > > const&, std::vector, std::allocator > >&, boost::geometry::default_strategy const&)
bool boost::geometry::intersection >, std::vector, std::allocator > >, std::vector, std::allocator > > >(Curve > const&, std::vector, std::allocator > > const&, std::vector, std::allocator > >&)
```
After reading the codes, I guess it may caused by `Section` at this line: https://github.com/boostorg/geometry/blob/c011ebfb4f095fabb0f770c9c09c59a6eacba0a7/include/boost/geometry/algorithms/detail/overlay/get_turns.hpp#L533.
Is it right and does we need to consider the reallocation performance cost?
Contributor guide
Assessment
This issue has not been assessed yet.