Date: Tue, 23 Sep 1997 02:14:32 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: gibbs@plutotech.com (Justin T. Gibbs) Cc: nate@mt.sri.com, gibbs@plutotech.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: <199709230214.TAA29871@usr01.primenet.com> In-Reply-To: <199709222104.PAA01993@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 22, 97 03:04:20 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> >Sure they do. If you have a bunch of timeout calls, and the untimeouts > >for them don't occur until *after* softclock, you have lots of entries > >to walk through. > > 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? 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?". 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". As far as non-deterministic insertion tine, as I said before, unless you are using delta intervals, the value for the timeout will be invariant across the list length. Since this is true, then it doesn't matter how long it takes: insertion can *be* indeterminate without ill effects. > 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? > If we decide to do high resolution timers, the > analysis may change as will most likely the implementation although > probably not by much. I agree. The implementation is very close to whats needed for either approaches model. 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? 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(). 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. This returns your insertion to O(1), removal is O(1), and timer list traversal is O(1) for most cases, where the timer inerval is some multiple of the softclock interval. 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?199709230214.TAA29871>