From owner-freebsd-current Mon Sep 22 14:51:23 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id OAA23800 for current-outgoing; Mon, 22 Sep 1997 14:51:23 -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 OAA23789 for ; Mon, 22 Sep 1997 14:51:17 -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 PAA15650; Mon, 22 Sep 1997 15:51:05 -0600 (MDT) Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id PAA03325; Mon, 22 Sep 1997 15:51:03 -0600 (MDT) Date: Mon, 22 Sep 1997 15:51:03 -0600 (MDT) Message-Id: <199709222151.PAA03325@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: <199709222145.PAA03221@pluto.plutotech.com> References: <199709222134.PAA03250@rocky.mt.sri.com> <199709222145.PAA03221@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 > >> 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. > > > >Then, why implement the darn thing at all, when we could simply add a > >hash-table to make untimeout more effecient, and not lose backwards > >compatability with all of the BSD code? I don't see what else the new > >code buys us that couldn't be done simply and with less overhead (in > >terms of code and new structure overhead)? > > > >Then, we'd be O(n) for timeout, O(1) for softclock, and O(1) for > >untimeout, which would be the same but with complete backwards > >compatability. The best of both worlds. :) > > I don't want to pay O(n) for anything. O(hash chain length) ~= O(n). > Perhaps I'm greedy. I can > perform upwards of 200 (real life, seek bound) transactions a second > with bonnie on a single Atlas II with the CAM code. I can perform > even more if I'm doing sequential reads. I can pretty much sustain > that rate to multiple drives meaning even a higher rate of timeout/ > untimeout calls. Going from 2 * O(n) to O(n) is not anywhere near > the same as going to 2 * O(1). 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). Nate