On Sun, Nov 04, 2007 at 06:00:56PM -0800, Christopher Layne <[EMAIL PROTECTED]> wrote: > 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 important. (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 Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
