Date: Tue, 23 Sep 1997 13:19:15 -0600 From: "Justin T. Gibbs" <gibbs@plutotech.com> To: Terry Lambert <tlambert@primenet.com> Cc: gibbs@plutotech.com (Justin T. Gibbs), 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: <199709231919.NAA28306@pluto.plutotech.com> In-Reply-To: Your message of "Tue, 23 Sep 1997 17:32:12 -0000." <199709231732.KAA15236@usr01.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>256 hash buckets divided by 30 expected entries is 8.53 softclocks >before a given entry is hit. Not "before a given entry is hit", "before any entries are hit". Your argument is that every 8.53 softclocks the hash chain will not be empty. So, just because a callout lives longer than 8.53 softclocks, does not mean that this callout will be the one touched by softclock. The assertion that a particular callout must live callwheel size ticks in order to be touched more than once still holds. >> 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. Then you missed the post where I actually posted the code correcting my first comment on the size to Nate. I posted the correction almost immediately after I said the size for MAXUSERS of 32 was 256. >> >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. I don't understand what you are trying to say. If I have 30 entries outstanding, then there are 30 entries outstanding when softclock runs regardless of the frequency of insertion or removal, or their lifetime. >> 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 still have the question wrong. >> >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. My calculation was for q being the numbered of entries queued since the last softclock and n outstanding entries already in the sorted list. I don't see how you can make this O(q) instead of O(n). >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? If there are entries in the unordered list, they are insertion sorted into the ordered list. Whether there are entries in the ordered list or not has no effect on whether the insertions are made. If you don't do the insertion, you may miss the proper next entry to schedule the one shot for as it may be in the unordered list. >This is the O(n/256) (again, assuming perfect hash) degradation, but >at softclock instead of at insertion; insertion is still O(1). Right. >> >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. I don't know how rare it is really. You'd have to do some statistics relating which bucket softclock is currently looking at and the likelihood of a new timeout being scheduled "close" to that position. I do know that it is going to be quite rare to have a callout touched more than once during it's lifetime. 256 ticks is a long time. 1024 ticks is even longer. > Regards, > Terry Lambert > terry@lambert.org >--- >Any opinions in this posting are my own and not those of my present >or previous employers. -- Justin T. Gibbs =========================================== FreeBSD: Turning PCs into workstations ===========================================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709231919.NAA28306>