search

boostorg / geometry

Boost.Geometry - Generic Geometry Library | Requires C++14 since Boost 1.75
http://boost.org/libs/geometry
Boost Software License 1.0
457 stars 216 forks source link

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

Open woodpenker opened 2 years ago

woodpenker commented 2 years ago

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: 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?

awulkiew commented 2 years ago

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