From owner-freebsd-current  Mon Sep 22 10:25:57 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id KAA01082
          for current-outgoing; Mon, 22 Sep 1997 10:25:57 -0700 (PDT)
Received: from godzilla.zeta.org.au (godzilla.zeta.org.au [203.2.228.19])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id KAA01052
          for <current@FreeBSD.ORG>; Mon, 22 Sep 1997 10:25:53 -0700 (PDT)
Received: (from bde@localhost) by godzilla.zeta.org.au (8.8.5/8.6.9) id DAA23286; Tue, 23 Sep 1997 03:23:55 +1000
Date: Tue, 23 Sep 1997 03:23:55 +1000
From: Bruce Evans <bde@zeta.org.au>
Message-Id: <199709221723.DAA23286@godzilla.zeta.org.au>
To: bde@zeta.org.au, gibbs@plutotech.com
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 ...
Cc: current@FreeBSD.ORG, nate@mt.sri.com
Sender: owner-freebsd-current@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

>>only 2 bits.  This is 96 times denser than the current callout table.
>
>And runs in roughly O(n) time every time the interval timer expires. You

No, it is O(1) in the usual case where the hardware has not timed out,
and O(n/32) (sic) otherwise (the bitmap can be scanned 32 bits at a time,
so 630 entries can be scanned in < 1us on a P5).

>also leave out the part about being able to index to transaction whose
>timer actually expired which will take additional space.

Maybe.  I know the drive number and the transaction number, and there's
presumably at worst a linked list of transactions attached to the drive
somehow (at best there's an array), and a linear search of this list
shouldn't take too long for an exceptional action.

Bruce