On Tue, Jun 30, 2009 at 01:00:13PM +0300, Marko Kreen wrote: [...] > The timeouts are kept in min-heap structure, whose goal is to make easy > to find smallest timeout. It does not store the event addition order > in a way that works 100% of the time, although it may happen to work 90% > of the time. This is expected and correct behaviour. > > To have a guarantee that order is followed 100% of the time means > replacing the structure with something more complex that can give such > guarantees. IMHO it is pointless.
Actually, there's a case to be made that we could augment our min-heap structure with something smarter. Check out the comments on the bugtracker entry at https://sourceforge.net/tracker/?func=detail&aid=1955777&group_id=50884&atid=461322 The idea is that min-heap performs at an asymptotically optimal O(lg n) in the case where you have a randomly distributed set of timeouts. But in practice, many programs have a large number of timers that cluster around a smalr sets of timeout intervals, and for a distribution like this, a doubly-linked queue could get O(1) insert/remove. But we wouldn't want a doubly-linked queue in general, since it has O(n) performance in the general case. So instead, we might want a facility to let application developers have some timeout values wind up queued, and others wind up heaped. This would probably be a tricky design challenge, and would want a fair bit of benchmarking to make sure it's a real win and doesn't actually hurt performance. -- Nick _______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users
