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