id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
9528	reactor_op_queue::get_descriptors O(N^2)	Evgeny.Panasyuk@…	chris_kohlhoff	"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();
}
}}}
"	Bugs	closed	To Be Determined	asio	Boost 1.55.0	Optimization	fixed