Chris G Demetriou <Chris_G_Demetriou@ux2.sp.cs.cmu.edu> writes:

> 
> So, i guess my first objection is, it's not been adequately shown that
> it needs optimization.  I'd like a profile of a heavily used network
> server (or whatever) where timeout handling has been shown to have a
> significant cost, or at least _some_ indication that it has (or in the
> future, with new users) will have significant cost.

You're looking at only the current uses of callouts.  The point is
that they should be used more, and doing this requires them to be
cheaper.

> > The overall time used for any given callout (whether deleted or
> > executed) is thus O(log T), where T is the distance into the future.
> > Since T is (especially when you include things like TCP timers) almost
> > always <= 60 seconds, this means that the constant factor is actually
> > fairly small.
> 
> Don't forget the constant multipliers!

I didn't.  If you consider the hair that either a heap or a balanced
tree would require, it's fairly clear that on all but one or two
platforms (e.g. *maybe* very old SPARC CPUs), the constant multiplier
is going to be about the same, or maybe slightly more than a `log N'
factor under low load, but will definitely be less under heavy load.

> If you allow 'tick' buckets to be collapsed into 'n-tick' buckets, the
> cost is higher.

Since I never suggested that, nor would I given that how inefficient
it would be, it's not particularly relevant.

> 	(2) less wasteful of memory than it should be.

It uses less memory per element than the balanced tree, although it
does have constant overhead.

> 	(3) 'nice' to the system.  It causes regular, potentially
> 	    large bursts of of CPU load completely asynchronous with
> 	    callout insertion/processing.  At the very least that
> 	    makes it hard to charge properly for that CPU usage.
> 	    At worst, it interferes with other system operation.
> 	    Wouldn't resorting have to happen with access to the
> 	    buckets disabled, i.e. at splhigh?

There are *already* `regular, potentially large bursts of CPU load'
when under load due to things like tcp_{fast,slow}timo() and the
scheduler.  This certainly isn't any worse.