Date: Mon, 22 Sep 1997 16:41:04 -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: <199709222241.QAA04073@rocky.mt.sri.com> In-Reply-To: <199709222155.PAA03743@pluto.plutotech.com> References: <199709222151.PAA03325@rocky.mt.sri.com> <199709222155.PAA03743@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> >> I don't want to pay O(n) for anything. > > > >O(hash chain length) ~= O(n). > > Nope. It has worst case running time of O(n) but average running time of > O(h) where h << n. Assuming that the average is one element on the list, yes. > >See above. You aren't paying anything more for the 'high-resolution' > >timer case with the old code (with untimeout hash-table, not yet > >implemented) vs. the new code (with ordered insertion in the hash-table > >list, not yet implemented). > > With ordered insertion in timeout() (which is what I'd guess we'd do to > support HRTs), softclock becomes O(callouts due), the same as the old > scheme, which means the new implementation is always faster than the > old one. Only for scheduling timeouts, and I still don't buy that the advantage is *that* great to make us completely un-backwards compatible with old BSD systems. But, I'll shutup now until I have a better solution. Nate
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709222241.QAA04073>