Opened 5 years ago

Closed 5 years ago

#9528 closed Bugs (fixed)

reactor_op_queue::get_descriptors O(N^2)

Reported by: Evgeny.Panasyuk@… Owned by: chris_kohlhoff
Milestone: To Be Determined Component: asio
Version: Boost 1.55.0 Severity: Optimization
Keywords: Cc:


I have simple P2P node. For benchmarking, it tries to open many tcp connections (as well as some small I/O on established connections) in single thread via boost::asio::ip::tcp::socket::async_connect - ~1000 per second. On Windows 7 it fully loads one CPU core. Profiler showed that ~75% of time is spent at following cycle of win_fd_set_adapter::set:

for (u_int i = 0; i < fd_set_->fd_count; ++i)
   if (fd_set_->fd_array[i] == descriptor)
       return true;

In my case it never finds descriptor in fd_array. And if comment that cycle then next hot spot is NtDeviceIoControlFile? - which consumes ~88% of time.

win_fd_set_adapter::set basically does linear search O(N), and if not find then it appends descriptor. At hotspot case it was called by reactor_op_queue::get_descriptors

typename operations_map::iterator i = operations_.begin();
while (i != operations_.end())
  Descriptor descriptor = i->first;
  if (!descriptors.set(descriptor))
    boost::system::error_code ec(error::fd_set_failure);
    cancel_operations(descriptor, ops, ec);

It calls descriptors.set for every element which results in quadratic overall complexity.

Moreover, caller of get_descriptors is select_reactor::run - it clears fd_set before call of reactor_op_queue::get_descriptors

for (int i = 0; i < max_select_ops; ++i)
    fd_sets_[i].reset(); // <------------------------------- RESET
socket_type max_fd = 0;
bool have_work_to_do = !timer_queues_.all_empty();
for (int i = 0; i < max_select_ops; ++i)
    have_work_to_do = have_work_to_do || !op_queue_[i].empty();
    op_queue_[i].get_descriptors(fd_sets_[i], ops);
    if (fd_sets_[i].max_descriptor() > max_fd)
      max_fd = fd_sets_[i].max_descriptor();

Change History (1)

comment:1 Changed 5 years ago by chris_kohlhoff

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.