Date: Tue, 23 Sep 1997 17:32:12 +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: <199709231732.KAA15236@usr01.primenet.com> In-Reply-To: <199709231653.KAA24904@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 23, 97 10:53:11 am
next in thread | previous in thread | raw e-mail | index | archive | help
> Actually lets look at the full context: Thanks! > >>For timeouts that live across softclock calls, as Nate is suggesting, > >>the list is traversed and the entry counts against the implementation > >>based on how many softclocks it lives across, on average. For ordered > >>insertion, the entry is counted against, once, at insertion time. > >> > >>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. > > That's not how I read it. And where do you come up with 8? 256 hash buckets divided by 30 expected entries is 8.53 softclocks before a given entry is hit. > >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. > > A MAXUSERS of 32 creates a callwheel size of 1024. A MAXUSERS of 10 > creates a callwheel size of 256. GENERIC results in 10. I was actually going by what you said to Nate here, and not the code. > >> 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. > > How can my average be 256/30 if 256 * 256 / 30 != 30? Total number of callouts outstanding. > >If an entry lives greater than 8.53 ticks, it will get hit twice. > >On average, for the algorithm to be less than O(n), any single entry > >must live 8 or less softclock ticks. > > You're digging a hole Terry. An entry must live for callwheel size > ticks in order to be touched twice during it's lifetime. The "twice" here refers to the number of entries that will be hit in a given bucket on average. On average, if I have 30 entries with an expected lifetime of 8.53 softclocks with a 256 bucket hash, then I have one lifetime per hash bucket. > Wow! Of course the point is that in the example, the hash chain length > is greater than 1 which nullifies your assertion. It nullifies it only if the timeout is used for 30 or less entries of 8.53 sofclocks diration or less for a 256 bucket hash. I think both yout duration and the number of events you expect to be outstanding at one time are low estimates based on who you think will be using the code. Julian actually made a number of good arguments for higher persistance timers. I think we have been arguing based on our own expected use of timers, so we haven't really been communicating very effectively because our initial conditions are different. Sorry. 8-(. > >You still haven't answered the question about the expected average > >lifetime of an entry. > > Yes I have. I said earlier that I expect most callouts to live only for > one or two ticks for my application. Here is the key: what about for other applications? For select() and poll() timeouts, or for FIN_2_WAIT, etc.? I think our expected usages are different. > >Do the callouts that are outstanding live more than 8 ticks? > > The question should be, do they live longer than 256 ticks. No. The question is "do they live longer than 256/number_outstanding"; for 30 entries, that's still 8. You actually answered this above with your expectation that the average lifetime is only one or two ticks. > >This calculation is incorrect, since I am suggesting not using a hash > >in the case of an ordered list. > > So you want softclock to become q * O(n) and ditch the hash table. For n entries queued since the last softclock, yes. Let's not confuse this with the number of entries, total, in the ordered list. > I think I'd rather pay the space to have an unordered queue for each > head in the hash table which means that only the current bucket and > the next non-empty bucket must have it's entries insertion sorted > in order to schedule the next one shot instead of all new entries that > have come in since the last softclock regardless of how they would be > distributed. This is more true to your desire to perform lazy > scheduling of timeouts. Hm. If on average, a hash bucket is empty (which it would be if you have 30 out of 256 entries), insertion is O(1). If on the other hand, you're wrong, and the usage is much higher (as I expect it will be), then you degrade to O(n/256) ordered insertion on a collision. I'm not sure I like my original insertion degradation enough to want to degrade to it during enqueueing. 8-). When you say "an unordered queue for each head in the hash table", do you mean that if there is an entry in both the ordered and unordered lists, the unordered list entries will be inserted into the ordered list on a per bucket basis? This is the O(n/256) (again, assuming perfect hash) degradation, but at softclock instead of at insertion; insertion is still O(1). This is probably the best we can hope for, unless we take Julian up on full queue migration, or pre-qualify by adding an expectation value for when we thing it will be dequeued to the call. I like it. I reserve the right to not like it later when there are a very large number of timer entries enqueued relative to the number of buckets and/or timers live agorss a larger number of softclocks. ;-). > I'm not worried about time in softclock as long as it isn't unnecessarily > excessive (O(n) is excessive) and it drops from splhigh at deterministic > intervals. Cool. I agree. > >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? > > But the calls to timeout and untimeout during softclock execution would > not be putting those entries into the ordered list; remember, we're > delaying all ordered insertion until softclock runs. I think this is only a problem for timeouts of 0; everything else should expect to be delayed 0-1 softclocks. If this isn't high enough resoloution, then we need to increase the softclock frequency. > >You were also the one that argued that insertion and deletion were > >relatively rare. > > I argued exactly the opposite. Insertion and deletion are the common > case, expiration is rare. Ugh. What I meant to say was that the number of entries outstanding at one time relative to the number of insertions and deletions that take place is small in proportion to the number of hash buckets. This would make it relatively rare that a softclock would ever hit an entry. It was this rarity I meant to reference, but my fingers were too fast. Hitting an unexpired entry is a bigger problem for me, with unordered lists per hash bucket, than hitting an expired entry. For the ordered list case, it's O(e + 1) compares (e == number of expored timers) vs. O(n). Again, we're talking persistant timers, so the argument isn't really applicable to your expected usage. Man, this is work. 8-(... Regards, 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?199709231732.KAA15236>