Date: Wed, 24 Sep 1997 14:35:51 -0700 (PDT) From: Archie Cobbs <archie@whistle.com> To: gurney_j@resnet.uoregon.edu Cc: current@FreeBSD.ORG Subject: Re: timeout management (was: Re: cvs commit: ...) Message-ID: <199709242135.OAA11785@bubba.whistle.com> In-Reply-To: <19970924025515.60364@hydrogen.nike.efn.org> from John-Mark Gurney at "Sep 24, 97 02:55:15 am"
next in thread | previous in thread | raw e-mail | index | archive | help
> well... I proposed that we used a fibonacci heap as a solution to this > problem... the fibonacci heap will do: > FUNCTION TIMING (amortized) > add new timeout O(1) > check for timeout O(1) > expire x timeouts O(x lg n) for n = number of timeouts > remove a timeout O(lg n) for n = number of timeouts > > now, you have to take into account that this is amortized time... so > at points in time, they may take longer.. but all the major work is > actually done when you remove a timeout... 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. The disadvantage is that you can do a lot of work duiring a single tick: O(N), where N is the number of timeout events still alive in the queue after 1/2 of their timeout periods. So if 99% of timeouts expire within the first half of their timeout period, then this algorithm is "optimal". The larger point is that given some assumption about what kind of behavior to expect, and what restrictions are required, you can design the "best" algorithm for those conditions. I agree with Julian's original point that we should have more than one timeout() function -- one for each "type" of timeout, e.g. the "high probability of being cancelled quickly" timeout() for disk errors, the "medium probability of timing but low granularity" for TCP retransmissions, etc... Some parameters are: - Are their lots of timeouts expected or just a few? - What is the probability distribution of the cancellation time as a percentage of total time (e.g., how far along the timeout period is an event likely to be cancelled?) Here 100% means the timeout event occurred. - What is sufficient granularity for the timeout? I'd be interested to see a catalog of all the clients of timeout() in the code, and what they look like in terms of the above questions. -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?199709242135.OAA11785>