Date: Mon, 22 Sep 1997 23:23:57 +1000 From: Bruce Evans <bde@zeta.org.au> To: gibbs@plutotech.com, nate@mt.sri.com Cc: 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 ... Message-ID: <199709221323.XAA15020@godzilla.zeta.org.au>
next in thread | raw e-mail | index | archive | help
>In performing the conversion of all the client code, it became quite
>obvious that the common case is to schedule a timeout that will be
>canceled before it expires and that the lifetime of a timeout is quite
>short. If this continues to be the case, we'll be bounded by the
>insert and removal time, not by the work in softclock as a single
>callout entry will be inserted and removed multiple times during one
>rotation of the callwheel.
timeout() was not very suitable for that case. It was better to use
a periodic timeout per subsystem and walk subsystem-specific timer
queues. The queues can probably be optimized better than any general
purpose queues. The cost of periodic timeouts and nested walking of
queues is very small.
>Take a server with 10 Seagate disks. Each one of these disks can
>handle 63 transactions at a time. If you split the disks across
>controllers correctly, you can readily keep them saturated with
>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:
/*
* a1 gives the transactions that will timeout on the next tick.
* a2 gives the transactions that will timeout on the next+1 tick.
* This is pseudocode. C doesn't have arrays of bits...
*/
insert(n): if (a2[n] == 0) { a2[n] = 1; ++count2; }
delete(n): if (a1[n] == 1) { a1[n] = 0; --count1; }
if (a2[n] == 1) { a2[n] = 0; --count2; }
periodic timeout:
if (count1 != 0) {
/*
* We expect that this case is rare, and it is only
* moderately expensive when it occurs (we just have
* to search 630 bits for set bits), so we optimized
* for it not happening.
*/
for (n = 0; ; ++n)
if (a1[n] == 1) {
handle_problem(n);
a1[n] = 0;
if (--count1 == 0)
break;
}
}
tmpa = a1; a1 = a2; a2 = tmpa1;
count1 = count2; count2 = 0;
Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709221323.XAA15020>