Date: Wed, 24 Sep 1997 18:19:22 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: Archie Cobbs <archie@whistle.com> Cc: current@FreeBSD.ORG Subject: Re: timeout management (was: Re: cvs commit: ...) Message-ID: <19970924181922.06828@hydrogen.nike.efn.org> In-Reply-To: <199709242135.OAA11785@bubba.whistle.com>; from Archie Cobbs on Wed, Sep 24, 1997 at 02:35:51PM -0700 References: <19970924025515.60364@hydrogen.nike.efn.org> <199709242135.OAA11785@bubba.whistle.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Archie Cobbs scribbled this message on Sep 24: > > > 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, do you still have to do some work after each tick?? or were does this come into play?? > So if 99% of timeouts expire within the first half of their timeout > period, then this algorithm is "optimal". hmm.. if you have something typed up about the design of this algo, could you send it to me in private mail... > 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... I agree... it makes the different algorithms do what they were designed to do... I was quite surprised when I looked at my Fibonacci heap code and noticed that the current compiled object is only 2688 bytes large.. and this includes the new freelist code which drops 100,000/10 from 2.35 down to 1.9.. so about a 1/5th improvement.. it wasn't as much as I had hopped though... > 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. this is the true way to do it... I only proposed fibonacci heaps as a solution because I knew that they had good amortized times, and eliminated most of the work from softclock... of course this doesn't allow you from doing interesting things like keeping long term timeouts in a seperate queue.. then merge that queue when the time comes (by scheduling a callback for that event :) )... this is very possible because fibonacci heaps can be combined in O(1)... -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19970924181922.06828>