Date: Mon, 22 Sep 1997 20:31:59 -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: <199709230232.UAA09928@pluto.plutotech.com> In-Reply-To: Your message of "Tue, 23 Sep 1997 02:14:32 -0000." <199709230214.TAA29871@usr01.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>> And timeout and untimeout would have just as many (most likely more since >> the hash table isn't very full) to walk through each time. > >The untimeout can easily be made O(1); just keep a backlink. This >is what you are doing, isn't it? Go read the code. >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?". Go read the code. 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. >If the answer is more than one, then it is a net loss. If the answer >is less than one, it's a net gain. From a cursory perusal, it seems to >me that the answer must be "more than one". What cursory perusal? You obviously haven't read the code or the paper. >> The code assumes nothing of the sort. My analysis of running time assumes >> that the frequency of calls to timeout or untimeout is >= the number of >> calls to softclock. > >You mean "the frequency of calls to timeout minus the calls untimeout >is < the number of calls to softclock". The point is to obtain a >relatively empty list at softclock, right? Nope. >Can you explain the insertion indeterminancy problem? Is it simply >that you want to take the hit at softclock rather than whereever the >timeout() is scheduled? Yup. >If so, I have a compromise suggestion, since the implication is that >timers *will* live across multiple softclocks (that they are, indeed, >measured in units of "number of softclocks"): > >Queue the entry for ordered insertion when timeout() is called, but >delay the ordered insertion until softclock(). Sounds like it will take additional space. >This allows you to take the traversal hit once: at the same time you >are timing out timers, in fact, so it's a non-hit relative to your >current algorithm. In fact it's O(n/2) instead of O(n), and then >only in the case that you have timers to insert. Nope. It's usually O(n) and not O(n/2) as most of the timeouts will be for the same amount of time in the future meaning a necessary tail insertion. If we keep the tail pointer, we can cut out this case though. > 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?199709230232.UAA09928>