Date: Mon, 22 Sep 1997 15:13:52 -0600 (MDT) From: Nate Williams <nate@mt.sri.com> To: "Justin T. Gibbs" <gibbs@plutotech.com> Cc: Nate Williams <nate@mt.sri.com>, Bruce Evans <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 src/sys/i386/eisa 3c5x9.c aha1742.c aic7770.c bt74x.c eisaconf.c eisaconf.h if_fea.c if_vx_eisa.c src/sys/i386/i386 autoconf.c ... Message-ID: <199709222113.PAA03063@rocky.mt.sri.com> In-Reply-To: <199709222104.PAA01993@pluto.plutotech.com> References: <199709222046.OAA02778@rocky.mt.sri.com> <199709222104.PAA01993@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> >> The timeout and untimeout calls do not need to be paired for this to be > >> the case. > > > >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. Not quite, because in the old scheme, they are sorted. It's really O(n/2) on average. The new scheme is forced to walk every element at softclock. > I was comparing > the new softclock with time O(n) (which is worse than it really is) and that > of the original timeout and untimeout, O(n). The calls don't need to > be paired for this analysis to be valid. Again, it would be nice to get some 'Real(tm)' #'s so all of us could quit guessing at things, and have something to point out other than the code. > >The whole assumption of this code is that the frequency of paird > >timeout/untimeout calls happen *much* more frequently than the frequency > >of softclocks, right? If that isn't the case (the clock frequency is > >increased, or timeouts are long), then the new system is a lose, because > >the # of callouts in the list at softclock() time starts to effect the > >effeciency of the system. > > > >Is this a correct assumption? If so, then Terry's concerns about > >high-resolution timers is still valid, even though the design wasn't > >designed for this, it negatively affects it *IF* high-resolution timers > >are a future goal. > > 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. If that changes, then my analysis of the code suggests that the current scheme could be a deteriment, rather than a help if we implement high resolution timers, because the time in softclock() becomes dominant instead of the time in timeout/untimeout. Simply put, if softclock is called more than timeout/untimeout, then the new system is a lose. (No matter how many callouts are outstanding.) Nate
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709222113.PAA03063>