reactor_op_queue::get_descriptors O(N^2)

[Evgeny.Panasyuk@…]

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:

// http://www.boost.org/doc/libs/1_55_0/boost/asio/detail/win_fd_set_adapter.hpp
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

// http://www.boost.org/doc/libs/1_55_0/boost/asio/detail/reactor_op_queue.hpp
typename operations_map::iterator i = operations_.begin();
while (i != operations_.end())
{
  Descriptor descriptor = i->first;
  ++i;
  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

// http://www.boost.org/doc/libs/1_55_0/boost/asio/detail/impl/select_reactor.ipp
for (int i = 0; i < max_select_ops; ++i)
    fd_sets_[i].reset(); // <------------------------------- RESET
fd_sets_[read_op].set(interrupter_.read_descriptor());
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();
}

[chris_kohlhoff]

Fixed on 'develop' in ​c06aa74f08a46dda05493f61d2b85cb7818e6f96.

Merged to 'master' in ​4e1e7d731fcc5c0104567856de476f7ce8806d72.