Re: kernel/timer.c design

[Tim Bird <tim.bird@am.sony.com>]

Ingo,

Thanks for the excellent description of the timer wheel
implementation.

Ingo Molnar wrote:
> One cost is the burstiness of processing: a single step of cascading can 
> take many timers to be processed (if they happen to be in that same 
> bucket)...

> But there's a hidden win as well from this approach: if a timer is 
> removed before it expires, we've saved the remaining cascading steps!  
> This happens surprisingly often: on a busy networked server, the 
> majority of the timers never expire, and are removed before they have to 
> be cascaded even once.

Unfortunately, this means that the actual costs of the wheel
implementation vary depending on the relationship between HZ,
the average timeout duration, and the bucket mappings (which,
as you say, can be adjusted for size reasons.)  This is one of
the downsides of the wheel implementation.  It's very difficult
to tell in advance whether a particular timer load
will cascade or not, making the costs (although bounded)
unexpectedly variable.

One solution (even suggested by Linus) for high resolution
timers was to increase HZ and skip timer ticks.  Unfortunately,
this has a dramatic affect on the cost of cascading, and on
the maximum duration available for timers.  (By increasing
HZ, you push more timers to higher tiers in the wheel, which
means you potentially end up cascading them more often,
even when they are removed before expiry.) These types
of unexpected consequences are one good reason for avoiding
use of the wheel for high res timers.

=============================
Tim Bird
Architecture Group Chair, CE Linux Forum
Senior Staff Engineer, Sony Electronics
=============================