Date: Wed, 24 Sep 1997 15:27:07 -0700 (PDT) From: Archie Cobbs <archie@whistle.com> To: current@FreeBSD.ORG Cc: gurney_j@resnet.uoregon.edu Subject: Re: timeout management (was: Re: cvs commit: ...) Message-ID: <199709242227.PAA17373@bubba.whistle.com> In-Reply-To: <199709242135.OAA11785@bubba.whistle.com> from Archie Cobbs at "Sep 24, 97 02:35:51 pm"
next in thread | previous in thread | raw e-mail | index | archive | help
I wrote: > > 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 :-). -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?199709242227.PAA17373>