Date: Mon, 22 Sep 1997 15:29:05 -0600 From: "Justin T. Gibbs" <gibbs@plutotech.com> To: Nate Williams <nate@mt.sri.com> Cc: "Justin T. Gibbs" <gibbs@plutotech.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: <199709222129.PAA02701@pluto.plutotech.com> In-Reply-To: Your message of "Mon, 22 Sep 1997 15:13:52 MDT." <199709222113.PAA03063@rocky.mt.sri.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. > >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. And softclock will most likely be something approaching O(1). Remeber it doesn't walk everything, only the entries in the current bucket. But, I'll give you O(n) if you want which is worst case running time, and even allow you to use the average running time for the old code, which means you need only three calls in order to make the new scheme superior. >> 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. Build the array and measure the call frequency. I'm already convinced it's better, so I don't have much reason do to more measurements today. >> 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.) If we implement high resolution timers, we will probably pay the O(hash chain length) insertion sort price in timeout and schedule a one shot timer for the next event that needs to run meaning that softclock is no longer tied to hz. >Nate -- 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?199709222129.PAA02701>