Re: [PATCH] ktimers subsystem 2.6.14-rc2-kt5

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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   [email protected]
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[Index of Archives]     [Kernel Newbies]     [Netfilter]     [Bugtraq]     [Photo]     [Stuff]     [Gimp]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Video 4 Linux]     [Linux for the blind]     [Linux Resources]
  Powered by Linux