From owner-freebsd-current  Mon Sep 22 14:46:00 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id OAA23319
          for current-outgoing; Mon, 22 Sep 1997 14:46:00 -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 OAA23301
          for <current@freebsd.org>; Mon, 22 Sep 1997 14:45:49 -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 PAA03221;
	Mon, 22 Sep 1997 15:45:28 -0600 (MDT)
Message-Id: <199709222145.PAA03221@pluto.plutotech.com>
X-Mailer: exmh version 2.0zeta 7/24/97
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 ... 
In-reply-to: Your message of "Mon, 22 Sep 1997 15:34:03 MDT."
             <199709222134.PAA03250@rocky.mt.sri.com> 
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Mon, 22 Sep 1997 15:45:17 -0600
From: "Justin T. Gibbs" <gibbs@plutotech.com>
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.  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).

Even in the high resolution timer case, the overhead is still much
smaller:
	O(hash chain) + O(1) ~= 2 * O(1)

>Nate

--
Justin T. Gibbs
===========================================
  FreeBSD: Turning PCs into workstations
===========================================