Date: Wed, 24 Sep 1997 19:29:53 -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: <199709250229.TAA16784@bubba.whistle.com> In-Reply-To: <19970924181922.06828@hydrogen.nike.efn.org> from John-Mark Gurney at "Sep 24, 97 06:19:22 pm"
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, do you still have to do some work after each tick?? or were does this
> come into play??
Yes.. each tick you do up to O(N) work (N defined as above).
> > 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...
I don't, but here's the general idea: for every range of ticks
of the form 2^n .. 2^(n+1) - 1 you split the range into two
halves and create a doubly linked list ("box") for each half. This is
the situation at t=0. The two halves are 2^n .. 2^n + 2^(n-1) - 1
2^n + 2^(n-1) .. 2^(n+1) - 1.
When any event is scheduled, you put it in the linked list corrsponding
to the range into which it's timeout value falls.
Now here's where it starts getting complicated...
As ticks go by, the 2^n .. 2^n + 2^(n-1) - 1 box shifts "left",
that is, it becomes the 2^n - 1 .. 2^n + 2^(n-1) - 2 box, and
similarly the 2^n + 2^(n-1) .. 2^(n+1) - 1 box becomes the
2^n + 2^(n-1) - 1 .. 2^(n+1) - 2 box.
When the left edge of the first box (ie, 2^n .. 2^n + 2^(n-1) - 1)
reaches 2^(n-1) + 2^(n-2), it's time to "rotate". Take this box
and put it aside. Nothing in it will expire for another 2^(n-1)
ticks at least. Replace it with two new empty boxes of half the size.
2^(n-1) ticks later (or now, if referring to the same box 2^(n-1)
ago), it's time to deal with this box we put aside because the
2^(n-1) has now gone to zero. So take everything left in the box
and reinsert it into the structure based on it's new, updated,
now-at-most-half-as-big-as-it-originally-was timeout value.
Rinse & repeat.
At time t=X, you are rotating the boxes corresponding to the bit
transitions of X.
Now you can see that sometimes lots of boxes will rotate at the
same time, requiring a lot of work on a single tick. But if you
look at any single element with original expiry T, it gets
reinserted at most lg T times..
So maybe you could do the "rotation" at a lower priority.
-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?199709250229.TAA16784>