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.
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.
The heap insertion/removal is trivial.
(Most of the benchmark differences are, in fact, due to the heap vs.
rb-tree).
--
The choice of a Deliantra, the free code+content MORPG
-----==- _GNU_ http://www.deliantra.net
----==-- _ generation
---==---(_)__ __ ____ __ Marc Lehmann
--==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED]
-=====/_/_//_/\_,_/ /_/\_\
_______________________________________________
Libevent-users mailing list
Libevent-users@monkey.org
http://monkey.org/mailman/listinfo/libevent-users
