Heap-based timer implementation (was Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent)

[Nick Mathewson]

On Sun, Nov 04, 2007 at 05:19:36PM -0800, Christopher Layne wrote:
> On Sun, Nov 04, 2007 at 05:04:25PM -0800, Scott Lamb wrote:
> > > * timers are managed by a priority queue (O(1) for important operations
> > >   as opposed to O(log n) in libevent, also resulting in much simpler code).
> > 
> > In terms of concrete data types, you appear to have used a binary heap?
> > So by "important operations" you mean removal, correct? Insertion is
> > still O(log n)? The asymptotic behavior is no different, then, as
> > insertion happens at least as often as removal.
> 
> Not to put on my O-face, but binary heap insert is *average*
> O(1). There should be a performance win for libevent, when it comes
> to timer checking, as using a heap will also be O(1) for heap_min()
> - which will benefit pending timer calculation code. However, early
> delete w/ pending timer will need some rigging or tombstone games. I
> wouldn't be surprised that, in a case where one is consistently
> resetting timers (think read/write before x time passes) and
> re-adding said event, that in the end it will be the same amount of
> CPU time.

In case anybody here isn't watching the commits list [1], Niels
applied a patch from Maxim Yegorushkin to make the timeout
implementation based on a heap, rather than a RB-tree.  Thanks, Maxim!

This will probably need some testing; if anybody wants to play around
with it, just check out the SVN trunk [2] and send in any bugs you run
into, or any improvements that we should make.

[1] The list is levent-commits at lists.sourceforge.net ; go to
      https://lists.sourceforge.net/lists/listinfo/levent-commits
    if you want to subscribe.

[2] The subversion repository is at
          https://levent.svn.sourceforge.net/svnroot/levent
    To check out trunk, make sure you have subversion installed, and type
     svn co https://levent.svn.sourceforge.net/svnroot/levent/trunk libevent-trunk

yrs,
-- 
Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
Url : http://monkeymail.org/archives/libevent-users/attachments/20071105/80e33b7a/attachment.bin