[Libevent-users] announcing libev, towards a faster and more featureful libevent

[Christopher Layne]

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.

-cl