Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 23 Sep 1997 04:15:49 +0000 (GMT)
From:      Terry Lambert <tlambert@primenet.com>
To:        gibbs@plutotech.com (Justin T. Gibbs)
Cc:        tlambert@primenet.com, gibbs@plutotech.com, nate@mt.sri.com, 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
Message-ID:  <199709230415.VAA07549@usr08.primenet.com>
In-Reply-To: <199709230232.UAA09928@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 22, 97 08:31:59 pm

next in thread | previous in thread | raw e-mail | index | archive | help
> >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.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709230415.VAA07549>