On Tue, Oct 23, 2007 at 02:10:46PM +0200, Joerg Sonnenberger wrote:
> > 
> > Apart from the requirement to scan empty slots - which should be quite
> > fast if there aren't too many of them - it should be ok provided you
> > restrict the granularity a bit.
> > Remember that the large majority of timers (esp in network code) are
> > 'guard' timers that don't expire.
> 
> Keep in mind that it also means that you push them around in the call
> wheel a lot, which is not free either.

I think you need to look at the call wheel code more closely.
Each callout can be processed a maximum of 3 times (5 if you include
adding/removing it).
With a 1ms resolution [1], most callouts will probably need to be moved
once only - in the last quarter second before expiry (the 2nd move
happens when there are ~65 seconds to expiry).
Redistributing callouts into the next level is also cheap.

I'm not suggesting it isn't a good idea to avoid taking an interrupt
every tick, just that you want to keep callouts set to fixed timed
points, and that the call wheel code is a very good scheme.

You might want to consider something else for the last row, but again
scanning an array of pointers (looking for a non-empty queue) is
actually probably quicker that any fancy search - given the likely
number of empty slots to skip.

	David

[1] and the existing 4 layer, 8 bits each system.

-- 
David Laight: david@l8s.co.uk