On 6/30/09, Nick Mathewson <ni...@freehaven.net> wrote: > 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.
Hm. How about this - keep using min-heap, but let each slot contain doubly-linked list of events. So equal (abs) timeout values would share the same slot. This would bring minimal additional complexity to codebase. Also, although cached per-base tv_cache should already create some amount of equal timeouts, this can be increased by rounding abs timeout values to fixed granularity positions, depending how far in the future they are: 0.. 1s -> 1ms? 1..10s -> 100ms >10s -> 1s This would result in minimal amount of slots in use in min-heap. -- marko _______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users
