Skip to content

Replace partial_sort with an iterative quick sort implementation

One of the bottlenecks that was identified is RayAggregator::get_next_ray which sorts rays using ::std::partial_sort which is significantly slower than ::std::sort. As ::std::sort can not be used due to recursion, an iterative sorting algorithm was needed.

While we do see some unexpected variations in our measurements (especially for the total runtime of each module) which we are still investigating, generally this set of patches improves the performance for us. For example, for our test system (Intel Core i7-6700HQ @ 2.60GHz × 8, 40 GB RAM, Ubuntu 18.04, ROS 2 Dashing, Autoware.auto (Hash: dba2158e)), the following performance improvements could be measured:

ray_ground_classifier: ~x1.7
velodyne_cloud: ~x1.7
(as a combination of the branches: walbroel.add_point, walbroel.iterative_quick_sort, walbroel.less_operator and walbroel.fast_atan2).

Merge request reports