boostorg / boostorg/geometry

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

Open
#1,037 1 comment 0 reactions 0 assignees View on GitHub
enhancement question
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.