Strand service scheduling is hurting ASIO scalability

[Chris White <chriswhitemsu@…>]

This problem will be explained best by walking through a scenario:

I have an io_service being run with one thread per CPU core. The CPU has 4 cores. I also have a strand. I then post 10 one-second operations to the strand, and 30 one-second operations to the io_service. That's 40 cumulative seconds of work, and since there are 4 cores, that work should optimally take 10 seconds when performed in parallel.

However, that's not what happens. The work in the io_service is given precedence over the work in the strand. So first, the 30 seconds of cumulative work in the io_service is performed in parallel which takes roughly 7.5 seconds (30 seconds / 4 cores). Only after that work is complete does the 10 seconds of work on the strand get performed. So it ends up taking a total of 17.5 seconds to do all the work because CPU time wasn't distributed optimally.

If we think of the strand and the io_service as queues, what we have here is a queue within a queue. The outer queue's work can be performed in parallel, the inner queue's work is performed serially. It seems to make a whole lot of sense that when control reaches the inner queue, that queue should be serviced until it's empty. After all, there are other threads that can still service the outer queue while that's happening. The opposite is not true. By giving the outer queue priority, ASIO is crippling the concurrency potential of the work in the inner queue i.e. the strand.

This simplified scenario is a very real performance problem for my companies server application. As far as I can tell, the only options for me to address the problem are to implement my own strand that doesn't give control back to the io_service until it's work queue is empty -or- put all of my strands onto one io_service and post all non-strand work to a second, separate io_service.

I attached a sample application that demonstrates the scenario above, complete with timings and a visual print out of the order of operations. It also includes a stripped down strand implementation that demonstrates how the problem could be addressed. The application was built in Visual Studio 2013 with boost version 1.60.0.

[Chris White <chriswhitemsu@…>]

To shed a little more light...if I post 10 operations to a strand in quick succession, my first operation goes into the ready_queue_, the strand gets scheduled, and then my other 9 operations go into waiting_queue_. When strand_service::do_complete() is called, it services the ready_queue_, then it appends the waiting_queue_ and reschedules the strand for the remaining work. So basically, whenever multiple operations are posted to a strand, the strand will have to be scheduled at least twice to perform all of the work.

Instead, the waiting_queue_ should be drained at least once when do_complete is called in order to perform all the operations that were posted from the time the strand was scheduled until the time the strand was serviced. Here is one possible solution. I inlined some code and added comments for clarity:

void strand_service::do_complete(io_service_impl* owner, operation* base,
    const boost::system::error_code& ec, std::size_t /*bytes_transferred*/)
{
  if (owner)
  {
    strand_impl* impl = static_cast<strand_impl*>(base);

    call_stack<strand_impl>::context ctx(impl);

    // ONLY THE FIRST POSTED OPERATION IS IN THE READY QUEUE.
    // SERVICE IT NOW WITHOUT HAVING TO LOCK THE MUTEX.

    while (operation* o = impl->ready_queue_.front())
    {
      impl->ready_queue_.pop();
      o->complete(*owner, ec, 0);
    }

    // SUBSEQUENT OPERATIONS ARE IN THE WAITING QUEUE.
    // SERVICE THEM NOW INSTEAD OF RESCHEDULING!

    impl->mutex_.lock();
    impl->ready_queue_.push(impl->waiting_queue_);
    bool more_handlers = impl->locked_ = !impl->ready_queue_.empty();
    impl->mutex_.unlock();
    if (!more_handlers)
      return;

    while (operation* o = impl->ready_queue_.front())
    {
      impl->ready_queue_.pop();
      o->complete(*owner, ec, 0);
    }

    // ONLY NOW WE RESCHEDULE IF MORE WORK HAS SINCE BEEN POSTED.

    impl->mutex_.lock();
    impl->ready_queue_.push(impl->waiting_queue_);
    more_handlers = impl->locked_ = !impl->ready_queue_.empty();
    impl->mutex_.unlock();
    if (more_handlers)
      owner->post_immediate_completion(impl, true);
  }
}

I was originally thinking that this could loop as long as there is work in either of the queues, but that might introduce concerns about a single strand monopolizing a thread, so I backed off from that solution. The implementation above is enough to addresses the problem in my attached sample application.