Many deadline_timer objects triggers worst-case vector reallocation in timer_queue

[chris_kohlhoff]

Using the g++ 4.4.5 on linux x86_64, the following program:

#include <boost/asio/deadline_timer.hpp>

boost::asio::io_service io_service;

struct timer
{
  boost::asio::deadline_timer t;
  timer() : t(io_service) {}
} timers[100000];

void handler(boost::system::error_code) {}

int main()
{
  for (std::size_t i = 0; i < 100000; ++i)
  {
    timers[i].t.expires_from_now(boost::posix_time::seconds(1000));
    timers[i].t.async_wait(handler);
  }
}

takes a very long time to run:

$ time ./a.out 

real	0m48.504s
user	0m21.469s
sys	0m27.038s

This is due to the vector<>-based heap in asio::detail::timer_queue reserve()-ing one element at a time.

[chris_kohlhoff]

(In [66158]) Fix vector reallocation performance problem. Refs #4780.

[chris_kohlhoff]

Performance of test program after fix:

$ time ./a.out 

real	0m0.096s
user	0m0.084s
sys	0m0.012s

[chris_kohlhoff]

(In [66173]) Merge from trunk. ........

r66075 | chris_kohlhoff | 2010-10-18 23:27:12 +1100 (Mon, 18 Oct 2010) | 2 lines

Fix unused parameter warnings.

........

r66143 | chris_kohlhoff | 2010-10-22 23:07:36 +1100 (Fri, 22 Oct 2010) | 2 lines

Redefine Protocol and id to avoid clashing with Objective-C++ keywords. Fixes #4191.

........

r66144 | chris_kohlhoff | 2010-10-22 23:20:52 +1100 (Fri, 22 Oct 2010) | 2 lines

Version check not required.

........

r66156 | chris_kohlhoff | 2010-10-24 11:26:10 +1100 (Sun, 24 Oct 2010) | 2 lines

Fix for IBM C++ compiler.

........

r66158 | chris_kohlhoff | 2010-10-24 13:06:46 +1100 (Sun, 24 Oct 2010) | 2 lines

Fix vector reallocation performance problem. Fixes #4780.

........

r66159 | chris_kohlhoff | 2010-10-24 18:58:23 +1100 (Sun, 24 Oct 2010) | 2 lines

Fix kqueue_reactor so that it compiles on NetBSD. Fixes #4662.

........

r66162 | chris_kohlhoff | 2010-10-25 00:15:46 +1100 (Mon, 25 Oct 2010) | 2 lines

Fix failure in socket_base test on NetBSD.

........