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 [EMAIL PROTECTED] ; go to
    if you want to subscribe.

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

Nick Mathewson

Attachment: pgph6MPLjfKJi.pgp
Description: PGP signature

Libevent-users mailing list

Reply via email to