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 epoll/poll/select, etc). -cl _______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
