Implement queued timeouts for case where many timeouts are the same.

Libevent's current timeout code is relatively optimized for the
randomly scattered timeout case, where events are added with their
timeouts in no particular order.  We add and remove timeouts with
O(lg n) behavior.

Frequently, however, an application will want to have many timeouts
of the same value.  For example, we might have 1000 bufferevents,
each with a 2 second timeout on reading or writing.  If we knew this
were always the case, we could just put timeouts in a queue and get
O(1) add and remove behavior.  Of course, a queue would give O(n)
performance for a scattered timeout pattern, so we don't want to
just switch the implementation.

This patch gives the user the ability to explicitly tag certain
timeout values as being "very common".  These timeout values have a
cookie encoded in the high bits of their tv_usec field to indicate
which queue they belong on.  The queues themselves are each
triggered by an entry in the minheap.

See the regress_main.c code for an example use.

svn:r1517

1 files changed, 2 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index 20987fbf..b06128fe 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -39,6 +39,8 @@ Changes in 2.0.3-alpha:
  o Remove compat/sys/_time.h.  It interfered with system headers on HPUX, and its functionality has been subsumed by event2/util.h and util-internal.h.
  o Add a new bufferevent_socket_connect_hostname() to encapsulate the resolve-then-connect operation.
  o Build kqueue.c correctly on GNU/kFreeBSD platforms. Patch pulled upstream from Debian.
+ o Alternative queue-based timeout algorithm for programs that use a large number of timeouts with the same value.
+
 
 Changes in 2.0.2-alpha:
  o Add a new flag to bufferevents to make all callbacks automatically deferred.