Date: Thu, 25 Sep 1997 14:23:35 -0700 (PDT) From: Archie Cobbs <archie@whistle.com> To: current@FreeBSD.ORG Subject: Re: timeout management (was: Re: cvs commit: ...) Message-ID: <199709252123.OAA18665@bubba.whistle.com> In-Reply-To: <199709242227.PAA17373@bubba.whistle.com> from Archie Cobbs at "Sep 24, 97 03:27:07 pm"
next in thread | previous in thread | raw e-mail | index | archive | help
> > Another algorithm that Julian and I discussed the other day has > > these properties: > > > > FUNCTION TIMING (amortized) > > add new timeout O(1) > > check for timeout O(1) > > remove a timeout O(1) (requires a handle) > > process one timeout O(lg T) for T = number of ticks alive > > > > That is, if a timeout event lives for T ticks (whether it's cancelled > > or expires after T ticks), it requires O(lg T) total work. > > > > Therefore, any event that is cancelled before 1/2 of it's timeout > > period has expired only requires O(1) work. > > Oops.. what I meant was that if a timeout event was scheduled for > T ticks, and it lives for R ticks, then the amount of work spent > on the event is O( lg T ) if R == T, else O( lg T - lg (T - R) ) > (which makes that last sentence true again :-). (If anyone is still interested...) It occurs to me that if a function can tolerate a large granularity, it would be easy to take advantage of that in this algorithm. Just define T' to be T/G, where T is the (original) total number of ticks, and G is the maximum inaccurracy (measured in ticks) that the function can tolerate. Then you do only O( lg T' ) work per event. To acomplish this, when a timer event reaches the point at which the time remaining is less than G, you simply make the event happen immediately. -Archie ___________________________________________________________________________ Archie Cobbs * Whistle Communications, Inc. * http://www.whistle.com
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709252123.OAA18665>