From owner-freebsd-current Mon Sep 22 15:41:32 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id PAA27104 for current-outgoing; Mon, 22 Sep 1997 15:41:32 -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 PAA27094 for ; Mon, 22 Sep 1997 15:41:27 -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 QAA16029; Mon, 22 Sep 1997 16:41:07 -0600 (MDT) Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id QAA04073; Mon, 22 Sep 1997 16:41:04 -0600 (MDT) Date: Mon, 22 Sep 1997 16:41:04 -0600 (MDT) Message-Id: <199709222241.QAA04073@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: <199709222155.PAA03743@pluto.plutotech.com> References: <199709222151.PAA03325@rocky.mt.sri.com> <199709222155.PAA03743@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 > >> 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