From owner-freebsd-current  Wed Sep 24 15:28:17 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id PAA03105
          for current-outgoing; Wed, 24 Sep 1997 15:28:17 -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 PAA03100
          for <current@FreeBSD.ORG>; Wed, 24 Sep 1997 15:28:10 -0700 (PDT)
Received: (from smap@localhost) by whistle.com (8.7.5/8.6.12) id PAA01427; Wed, 24 Sep 1997 15:27:08 -0700 (PDT)
Received: from bubba.whistle.com(207.76.205.7) by whistle.com via smap (V1.3)
	id sma001425; Wed Sep 24 15:27:07 1997
Received: (from archie@localhost) by bubba.whistle.com (8.8.5/8.6.12) id PAA17373; Wed, 24 Sep 1997 15:27:07 -0700 (PDT)
From: Archie Cobbs <archie@whistle.com>
Message-Id: <199709242227.PAA17373@bubba.whistle.com>
Subject: Re: timeout management (was: Re: cvs commit: ...)
In-Reply-To: <199709242135.OAA11785@bubba.whistle.com> from Archie Cobbs at "Sep 24, 97 02:35:51 pm"
To: current@FreeBSD.ORG
Date: Wed, 24 Sep 1997 15:27:07 -0700 (PDT)
Cc: gurney_j@resnet.uoregon.edu
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


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