On Mon, Nov 05, 2007 at 02:42:16AM +0100, Marc Lehmann wrote:
> On Sun, Nov 04, 2007 at 05:19:36PM -0800, Christopher Layne <[EMAIL 
> PROTECTED]> wrote:
> > 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.
> No, because a red-black tree is much more complex in management, so even if
> both operations are O(log n), the heap usually wins hands down.
> Both insertion and removal are of the same complexity, on average, in a
> heap, of the data is random.
> However, libev has an interface (ev_timer_again) that incrementally
> updates the heap. Also, for repeating timers in general, there is no
> removal/insertion but only an incremental update.

Right, which is not due to an inherent advantage of heap vs rbtree - but due
to our luck in time always going in one direction. I believe similar code was
present in libevent as it was. This in itself should be no different.

> Regarding pending events, this is solved in the same way for all events
> (not unlike how libevent does it): There is only one place where a pending
> event can be, and that is on its associated pending list.
> When an event gets stopped, and is found pending, it will be removed form
> the pending queue by nulling out its pointer.

My point was that an event_del() on an event which has been called before it's
timer has expired *or* an event_add() with a new timer will require reheapifying
atleast part of the timer heap. Having an intrinsically sorted collection of
elements and then altering a value within the middle of said collection before
it has sifted to the top will require a reheap from that point on.

Which isn't really that big a deal as similar time is spent in the present RB
implementation as it is.

I'm all for a binary-heap rather than a RB-tree personally. I think the
performance will benefit primarily for heap_min() (which is done before every
re-entry into the event backend to reset the max-wait timer for 

Libevent-users mailing list

Reply via email to