[Boost-bugs] [Boost C++ Libraries] #9528: reactor_op_queue::get_descriptors O(N^2)

Subject: [Boost-bugs] [Boost C++ Libraries] #9528: reactor_op_queue::get_descriptors O(N^2)
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-12-27 14:44:21

#9528: reactor_op_queue::get_descriptors O(N^2)
-------------------------------+----------------------------
 Reporter:  Evgeny.Panasyuk@…  |      Owner:  chris_kohlhoff
     Type:  Bugs               |     Status:  new
Milestone:  To Be Determined   |  Component:  asio
  Version:  Boost 1.55.0       |   Severity:  Optimization
 Keywords:                     |
-------------------------------+----------------------------
 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();
 }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9528>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.