[lkml]   [2005]   [Oct]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH] ktimers subsystem 2.6.14-rc2-kt5
Tim Bird wrote:
> Ingo Molnar wrote:
>>My claim is that if you _know_ that a timer will expire most likely, you
>>want it to order at insertion time - i.e. you want to have a tree
>>structure. If you _know_ that a timer will most likely _not_ expire,
>>then you can avoid the tree overhead by 'delaying' the decision of
>>sorting timers, to the point in the future where we really are forced to
>>do so.
>>The result of this mathematical paradox is that we end up with two data
>>structures: one is the timer wheel (kernel/timers.c) for
>>timeout/exception related use; the other one is ktimers
>>(kernel/ktimers.c), for expiry oriented use.
> I'd like to make an observation on another
> difference between the wheel and the rbtree. Note that
> the wheel implementation inherently coalesces timeouts
> that are near each other, due to it's relatively
> low resolution (at tick granularity - which is
> still pretty low resolution on embedded hardware -
> usually 10 milliseconds.)
> One concern I have with the rbtree is that this
> automatic coalescing is lost, and there may be
> unanticipated overhead in the move to support
> high resolution timers.

I think the coalescing is really done by the resolution rounding. There will always be the list
removal overhead, but short of a duplex tree (i.e. one entry per time with dup times linked from the
first (Ug)) you will always have that. What you want to coalesce is the interrupt overhead, not the
list overhead, the former being MUCH larger. The difference here is that we don't see the
resolution reflected in the tree structure, but that, I think, is good.
> Whether some form of coalescing should be
> preserved for timers, even when the system
> supports higher resolution, will be a
> function of the number of timers and their
> intended use. I don't see any support for that
> in the current patch, but maybe I'm missing
> something.
> =============================
George Anzinger
HRT (High-res-timers):
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-10-19 02:07    [W:0.125 / U:32.444 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site