Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Why does adding N entities to a CallbackGroup take N^2, i.e. quadratic time ?

Aperta
  • Qualcosa non va?
#2,942 0 commenti 0 reazioni 1 assegnatario Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

@wjwwood ci sta già lavorando.

Dal 12/9/2025.

  • #3109 di @PavelGuzenfeld — chiusa senza merge
  • #3166 di @PavelGuzenfeld — chiusa senza merge

Valutazione

Questa issue non è ancora stata valutata.

Descrizione

enhancement
Description

Adding many timers in a for-loop is very slow since it takes overall quadratic time.

Motivation

So I stumbled upon this issue when I was creating 10.000 timers in a for-loop (I was benchmarking events throughput).
perf shows 96% of the time is spent in CallbackGroup::add_timer.

Design / Implementation Considerations

So I looked what is going on and saw this:

CallbackGroup::add_timer(const rclcpp::TimerBase::SharedPtr timer_ptr)
{
  std::lock_guard<std::mutex> lock(mutex_);
  timer_ptrs_.push_back(timer_ptr);
  timer_ptrs_.erase(
    std::remove_if(
      timer_ptrs_.begin(),
      timer_ptrs_.end(),
      [](rclcpp::TimerBase::WeakPtr x) {return x.expired();}),
    timer_ptrs_.end());
}

So every time we add a timer, we do a linear search over the list of all existing timers to find and remove timers that have been destroyed meanwhile. This takes (N^2+N)/2 operations, i.e. is a quadratic time algorithm, which is quite bad.

The same is done for all entities, i.e. not only timers but also subscriptions, publishers etc.
Tested on Humble, but the code is the same in rolling, so the issue is still present in rolling as well.

Discussion and possible fixes

The offending linear search was added as a fix for an otherwise growing memory demand, i.e. memory leak issue in https://github.com/ros2/rclcpp/pull/814.
I think the root cause of having to add such a fix is generally the ownership of entities. Since they are owned by the user and not by the rclcpp::Node, the rclcpp::Node does not get to know when an entity is destroyed. But since the rclcpp::Node and its associated classes such as the CallbackGroup work with these entities, they must hold references to them. Therefore, when an entity is destroyed, there will always be an invalid (weak) reference to this entity stored in the CallbackGroup, and potentially many other internal classes. This reference needs to be cleaned up somehow. And currently, since we do not know which entities were destroyed, we need to check all entities on each occasion.

This issue was discussed already in the API Review 2020.

I think the best solution to this problem, fixing the root cause, is to move the ownership of entities to a central class (e.g. rclcpp::Node)
which has methods for deleting entities.

But since that's a big API-breaking change, here are some alternative proposals (including their downsides)

  • The executor cleans up the CallbackGroups regularly (ignores separation of concerns)
  • Every entity calls a newly added callback clean_up_all_referencesin its destructor: Entities already clean up things in their destructors, but still has to be implemented for every entity (complexity)
  • Add an CallbackGroup::add_entities method: Does one instead of N linear searches (hacky)
  • Make the cleanup optional and switchable at runtime: Since entities almost always live for as long as the node, users can opt-in to not perform any cleanup to gain performance
Additional Information

ROS 2 Humble on Ubuntu 22.04. rclcpp v16.0.12. RMW used is rmw_cyclonedds_cpp, v1.3.4.
Image
Reproducer code:

Reproducer 

#include <atomic>
#include <chrono>
#include <iostream>
#include <memory>
#include <vector>

#include "rclcpp/rclcpp.hpp"

using namespace std::chrono_literals;

class TimerBenchmarkNode : public rclcpp::Node {
public:
  TimerBenchmarkNode(size_t total_timers, std::chrono::milliseconds period)
      : Node("timer_benchmark"), total_timers_(total_timers), completed_(0) {
    timers_.reserve(total_timers_);
    start_time_ = std::chrono::steady_clock::now();

    for (size_t i = 0; i < total_timers_; ++i) {
      auto timer = this->create_wall_timer(period, [this, i]() {
        // Cancel the timer inside the callback
        timers_[i]->cancel();

        // Count completions
        if (++completed_ == total_timers_) {
          auto end_time = std::chrono::steady_clock::now();
          auto duration_ms =
              std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time_).count();

          RCLCPP_INFO(this->get_logger(), "Processed %zu timers in %ld ms (%.0f timers/sec)",
                      total_timers_, duration_ms, (total_timers_ * 1000.0) / duration_ms);

          // Destroy timers explicitly
          // timers_.clear();
        }
      });

      timers_.push_back(timer);
    }
  }

private:
  size_t total_timers_;
  std::vector<rclcpp::TimerBase::SharedPtr> timers_;
  std::atomic<size_t> completed_;
  std::chrono::time_point<std::chrono::steady_clock> start_time_;
};

int main(int argc, char** argv) {
  rclcpp::init(argc, argv);
  getchar();
  size_t total_timers = 10000;
  auto node = std::make_shared<TimerBenchmarkNode>(total_timers, 0ms);

  rclcpp::spin(node);
  rclcpp::shutdown();
  return 0;
}
Lingua principale
C++
Stelle
814
Fork
572
Merge medio
5g 3h
PR unite (30g)
17

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di ros2/rclcpp

Tutte le issue di ros2/rclcpp

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.