On Sun, Nov 04, 2007 at 06:00:56PM -0800, Christopher Layne <[EMAIL PROTECTED]> 
> 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.

Hmm, I do not see why this would ever be the case. Removing a timer that
hasn't expired yet might actually be much cheaper than removing the one at
the top element because it isn't at the root, so the n in the O(log n) is
potentially much smaller.

> 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.

Not sure what you mean with "re-heap", but the opertaion you describe is the
same O(log n) operation as for removing elements elsewhere in the heap. And
given that you take the latets timer and insert it at that point, removing a
timer that hasn't expired is usually faster.

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

No, I still maintain that the RB tree is slower because its rebalancing
operations are frequent and very complex. Heap code is trivial. Yes, they
have the same asymptotic growth behaviour, but the practical cases are
all very far away from infinity, and the hidden C in O(log n) is quite

(Again, please refer to the benchmark at
http://libev.schmorp.de/bench.html which directly contrasts behaviour
of libevent and libev with timers and no timers, especially look at the
difference in runtime when timers are being used).

> 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).

I thought so, too, until recently but in fact the event loop is run pretty
rarely (except in benchmarks), and if you handle hundreds of clients
within each run (very typical of busy servers), then you can have hundreds
of timer updates, and these do show up in timing measurements.

                The choice of a       Deliantra, the free code+content MORPG
      -----==-     _GNU_              http://www.deliantra.net
      ----==-- _       generation
      ---==---(_)__  __ ____  __      Marc Lehmann
      --==---/ / _ \/ // /\ \/ /      [EMAIL PROTECTED]
      -=====/_/_//_/\_,_/ /_/\_\
Libevent-users mailing list

Reply via email to