From owner-freebsd-current Mon Sep 22 14:56:25 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id OAA24229 for current-outgoing; Mon, 22 Sep 1997 14:56:25 -0700 (PDT) Received: from pluto.plutotech.com (root@mail.plutotech.com [206.168.67.137]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id OAA24215 for ; Mon, 22 Sep 1997 14:56:11 -0700 (PDT) Received: from narnia.plutotech.com (narnia.plutotech.com [206.168.67.130]) by pluto.plutotech.com (8.8.5/8.8.5) with ESMTP id PAA03743; Mon, 22 Sep 1997 15:55:57 -0600 (MDT) Message-Id: <199709222155.PAA03743@pluto.plutotech.com> X-Mailer: exmh version 2.0zeta 7/24/97 To: Nate Williams cc: "Justin T. Gibbs" , 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: Your message of "Mon, 22 Sep 1997 15:51:03 MDT." <199709222151.PAA03325@rocky.mt.sri.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Mon, 22 Sep 1997 15:55:46 -0600 From: "Justin T. Gibbs" 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. 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 ===========================================