From owner-freebsd-current Mon Sep 22 07:42:03 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id HAA16666 for current-outgoing; Mon, 22 Sep 1997 07:42:03 -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 HAA16661 for ; Mon, 22 Sep 1997 07:42:00 -0700 (PDT) Received: (from bde@localhost) by godzilla.zeta.org.au (8.8.5/8.6.9) id AAA18001; Tue, 23 Sep 1997 00:40:34 +1000 Date: Tue, 23 Sep 1997 00:40:34 +1000 From: Bruce Evans Message-Id: <199709221440.AAA18001@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 >>>requests. Thats 630 pending callouts and an O(n) hit for insert >>>and removal... >> >>Assuming that the timeout length is not very critical, and that timeouts >>rarely expire, this setup could be optimized well using "queues" >>consisting of two (pointers to) arrays of bits, and counters for the >>number of items set in each array: > >Now make it scale during usage. There are lots of schemes available, >but very few are easily scalable by mallocing small chunks of free >memory. This one is: when attaching a drive, find a free drive number and malloc more storage if the new number is at the end. Rarely free anything. The main point is that it is easy to build a perfect hash function (drive_number, transaction_number) -> timeout_slot_number because we only need one timeout per (drive_number, transaction_number). Bruce