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
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
pgph6MPLjfKJi.pgp
Description: PGP signature
_______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
