From owner-freebsd-current Thu Sep 25 14:24:32 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id OAA14603 for current-outgoing; Thu, 25 Sep 1997 14:24:32 -0700 (PDT) Received: from whistle.com (s205m131.whistle.com [207.76.205.131]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id OAA14597 for ; Thu, 25 Sep 1997 14:24:29 -0700 (PDT) Received: (from smap@localhost) by whistle.com (8.7.5/8.6.12) id OAA09426 for ; Thu, 25 Sep 1997 14:23:53 -0700 (PDT) Received: from bubba.whistle.com(207.76.205.7) by whistle.com via smap (V1.3) id sma009422; Thu Sep 25 14:23:35 1997 Received: (from archie@localhost) by bubba.whistle.com (8.8.5/8.6.12) id OAA18665 for current@FreeBSD.ORG; Thu, 25 Sep 1997 14:23:35 -0700 (PDT) From: Archie Cobbs Message-Id: <199709252123.OAA18665@bubba.whistle.com> Subject: Re: timeout management (was: Re: cvs commit: ...) In-Reply-To: <199709242227.PAA17373@bubba.whistle.com> from Archie Cobbs at "Sep 24, 97 03:27:07 pm" To: current@FreeBSD.ORG Date: Thu, 25 Sep 1997 14:23:35 -0700 (PDT) X-Mailer: ELM [version 2.4ME+ PL31 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > > 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