From owner-freebsd-current Mon Sep 22 14:14:09 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id OAA20585 for current-outgoing; Mon, 22 Sep 1997 14:14:09 -0700 (PDT) Received: from ns.mt.sri.com (SRI-56K-FR.mt.net [206.127.65.42]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id OAA20572 for ; Mon, 22 Sep 1997 14:14:02 -0700 (PDT) Received: from rocky.mt.sri.com (rocky.mt.sri.com [206.127.76.100]) by ns.mt.sri.com (8.8.7/8.8.7) with ESMTP id PAA15382; Mon, 22 Sep 1997 15:13:54 -0600 (MDT) Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id PAA03063; Mon, 22 Sep 1997 15:13:52 -0600 (MDT) Date: Mon, 22 Sep 1997 15:13:52 -0600 (MDT) Message-Id: <199709222113.PAA03063@rocky.mt.sri.com> From: Nate Williams MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: "Justin T. Gibbs" Cc: Nate Williams , Bruce Evans , 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 ... In-Reply-To: <199709222104.PAA01993@pluto.plutotech.com> References: <199709222046.OAA02778@rocky.mt.sri.com> <199709222104.PAA01993@pluto.plutotech.com> X-Mailer: VM 6.29 under 19.15 XEmacs Lucid Sender: owner-freebsd-current@freebsd.org X-Loop: FreeBSD.org Precedence: bulk > >> 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