From owner-freebsd-current Mon Sep 22 21:17:33 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id VAA14102 for current-outgoing; Mon, 22 Sep 1997 21:17:33 -0700 (PDT) Received: from usr08.primenet.com (tlambert@usr08.primenet.com [206.165.6.208]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id VAA14097 for ; Mon, 22 Sep 1997 21:17:29 -0700 (PDT) Received: (from tlambert@localhost) by usr08.primenet.com (8.8.5/8.8.5) id VAA07549; Mon, 22 Sep 1997 21:15:49 -0700 (MST) From: Terry Lambert Message-Id: <199709230415.VAA07549@usr08.primenet.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 To: gibbs@plutotech.com (Justin T. Gibbs) Date: Tue, 23 Sep 1997 04:15:49 +0000 (GMT) Cc: tlambert@primenet.com, gibbs@plutotech.com, nate@mt.sri.com, bde@zeta.org.au, current@FreeBSD.ORG In-Reply-To: <199709230232.UAA09928@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 22, 97 08:31:59 pm X-Mailer: ELM [version 2.4 PL23] Content-Type: text Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > >The untimeout can easily be made O(1); just keep a backlink. This > >is what you are doing, isn't it? > > Go read the code. It was a rhetorical question. > >For timeouts that live across softclock calls, as Nate is suggesting, > >the list is traversed and the entry counts against the implementation > >based on how many softclocks it lives across, on average. For ordered > >insertion, the entry is counted against, once, at insertion time. > > > >So the question to as is "how many softclocks does the average timer > >entry live across?". > > Go read the code. This one was less rhetorical, and required an empirical judgement on your part to get the same conclusion I had already made. It's called a Socratic Dialectic. The real answer is "it depends on what timer intervals you use and with what frequency a timer is dequeud before it fires" to answer the question. It seems the answer is "a given entry is traversed by many softclock() events; how many depends on the expected duration of the entry divided by the number of hash buckets". For 10 users, this is much less than 256. You still haven't stated how amny timers are expected to be enqueued in all buckets, on average, when a softclock hits, in common usage. > An entry will only have it's count decremented if, during it's lifetime, > softclock traverses the list of callouts in it's hash bucket. It may > take numerous calls to softclock before it touches the bucket where > a particular callout is placed. Nate's point was that this assumes one entry per hash bucket, on average. For the default of 10 users in GENERIC, I think this is a bad assumption. Even for 32 users (256 buckets), it's stretching things if the timers see any real use at all. > >If so, I have a compromise suggestion, since the implication is that > >timers *will* live across multiple softclocks (that they are, indeed, > >measured in units of "number of softclocks"): > > > >Queue the entry for ordered insertion when timeout() is called, but > >delay the ordered insertion until softclock(). > > Sounds like it will take additional space. No. It will take two additional pointers and a trivial amount of code identical to the code you would need anyway. > >This allows you to take the traversal hit once: at the same time you > >are timing out timers, in fact, so it's a non-hit relative to your > >current algorithm. In fact it's O(n/2) instead of O(n), and then > >only in the case that you have timers to insert. > > Nope. It's usually O(n) and not O(n/2) as most of the timeouts will > be for the same amount of time in the future meaning a necessary tail > insertion. If we keep the tail pointer, we can cut out this case though. Which you would, if you had an inverse pointer. That's the second of the two pointers, above. The first of them is the head for the list of "queued-but-not-yet-order-inserted" entries that you will insert (in order) at the first softclock after they are enqueued. The enqueuing itself is O(1), returning your insertion back down to the required O(1) to make it determinant for interrupt routines. Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.