Date: Tue, 23 Sep 1997 16:13:06 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: gibbs@plutotech.com (Justin T. Gibbs) Cc: tlambert@primenet.com, gibbs@plutotech.com, nate@mt.sri.com, bde@zeta.org.au, current@FreeBSD.ORG Subject: Re: cvs commit: src/sys/conf files src/sys/dev/vx if_vx.c if_vxreg.h src/sys/i386/apm apm.c src/sys/i386/conf GENERIC files.i386 Message-ID: <199709231613.JAA09972@usr01.primenet.com> In-Reply-To: <199709230630.AAA13505@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 23, 97 00:30:25 am
next in thread | previous in thread | raw e-mail | index | archive | help
> >> >So the question to as is "how many softclocks does the average timer > >> >entry live across?". > >> > >> Go read the code. > > > >This one was less rhetorical, and required an empirical judgement on > >your part to get the same conclusion I had already made. It's called > >a Socratic Dialectic. > > Bullshit. You stated that every entry would be touched on each softtick. No I did not. Look at my sentence you quote in your response: > >> >So the question to as is "how many softclocks does the average timer > >> >entry live across?". This has nothing to do with claiming that every entry would be touched on every softclock. It has to do with an entry living, on average, 8 or more softclocks. This is being generous, since it accepts your number of users (32) instead of the GENERIC number of users (10) to obtain a total of 256 buckets. > Sure I have. On each softclock, the number of timers enqueued in > all buckets is the number of callouts outstanding which I've said > is around 30 for a typical workstation. Of course you probably > meant to ask what the average length of a hash chain is and to > answer that question for the loads I'm interested in, I'd have to > instrument the code. I expect it to be h where h << n and n is > the total number of callouts outstanding. Well duh, or it wouldn't be a hash; the actual *average* would be 256/30 assuming a *perfect* hash. If an entry lives greater than 8.53 ticks, it will get hit twice. On average, gor the algorithm to be less than O(n), any single entry must live 8 or less softclock ticks. > > >> An entry will only have it's count decremented if, during it's lifetime, > >> softclock traverses the list of callouts in it's hash bucket. It may > >> take numerous calls to softclock before it touches the bucket where > >> a particular callout is placed. > > > >Nate's point was that this assumes one entry per hash bucket, on average. > > No it doesn't. For example, here is a 4 bucket call wheel: > > 1 2 3 4 > + + + + > x a b d > + + + > y c f > + + > z e > > Lets say that softclock is currently at bucket 2. When will entries > x, y, and z next be referenced? During the call to softclock 3 ticks > in the future. If any of x, y, or z are removed before that time, > they will not be referenced. The average hash chain length in this > callwheel is a little over 2. 2.25. Even I can accurately divide 9 by 4. You still haven't answered the question about the expected average lifetime of an entry. Is an entry expected to be hit by one or more softclocks in its lifetime? *THAT* is the question. The x in O(x) is the average number of times that any given entry can expect to be hit by a softclock. > >For the default of 10 users in GENERIC, I think this is a bad assumption. > >Even for 32 users (256 buckets), it's stretching things if the timers > >see any real use at all. > > The hash table size is still larger than the total number of callouts > that can be outstanding. Do the callouts that are outstanding live more than 8 ticks? > >> >Queue the entry for ordered insertion when timeout() is called, but > >> >delay the ordered insertion until softclock(). > >> > >> Sounds like it will take additional space. > > > >No. It will take two additional pointers and a trivial amount of > >code identical to the code you would need anyway. > > Two pointers is additional space. Now who is really picking nits? It's a hell of a lot less space than you are already using, and it's statically allocated. > It also makes softclock become q * O(h) + O(c) where q is the number > of defered insertion entries, h is the hash chain length and c is > the number of empty buckets that are traversed to find the next > timeout for scheduling the next one shot. This calculation is incorrect, since I am suggesting not using a hash in the case of an ordered list. If you will remember, this was a compromise for your complaint that insertion at interrupt was not O(1). You weren't worried about time in softclock until I figured out how to move the overhead there. Even so, you're still not worried about determinism in softclock; one indeterminate value is as good as any other. > Then there is the additional code in softclock to ensure > that none of the timeouts queued while softclock is running are > supposed to expire in the current tick which you would need to > check every time softclock drops from splhigh to let other interrupts > run as there is nothing to prevent a timeout handler or interrupt > handler from scheduling such an entry. Softclock need only check the tick values from the head, and may stop when it hits the first entry whose tick value exceeds the current tick value; remember, the list under discussion is ordered? You were also the one that argued that insertion and deletion were relatively rare. > Sure, it's do-able, but > the current implementation doesn't have any of this mess and still > gets the O(1) insertion and softclock pays a single O(h). O(h * (avg lifetime in ticks of any entry / 8)) If you can show the average lifetime to be less than 8, then this means your algorithm is even better than you initially claimed... Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709231613.JAA09972>