[Libevent-users] announcing libev, towards a faster and more featureful libevent

[William Ahern]

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 <clayne at anodized.com> 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.