Date: Mon, 22 Sep 1997 15:55:46 -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: <199709222155.PAA03743@pluto.plutotech.com> In-Reply-To: Your message of "Mon, 22 Sep 1997 15:51:03 MDT." <199709222151.PAA03325@rocky.mt.sri.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. Perform the measurements to prove this to yourself if you want. >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. >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?199709222155.PAA03743>