On Mon, Nov 05, 2007 at 03:29:34AM +0100, Marc Lehmann wrote: > On Sun, Nov 04, 2007 at 06:00:56PM -0800, Christopher Layne <[EMAIL > PROTECTED]> wrote: <snip> > > 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. >
RB balancing isn't that complex. Maybe you're thinking of AVL trees? The problem with using heaps in network software is you must be careful adversaries cannot dictate any of the parameters. Certainly when you're dealing with timers triggered by I/O latencies you've at least theoretically exposed yourself to complexity attacks. (This is a guess based on intuition; I haven't yet looked at your code.) Nice thing about RB trees is you get a cap on worst case performance, smooth cost spreading (i.e. no rehashing; not that it would be needed here), and don't have to worry about pathological or malicious scenarios. Sure you pay a small price. But for peace of mind its well worth it. _______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
