lkml.org 
[lkml]   [2005]   [Oct]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] ktimers subsystem 2.6.14-rc2-kt5
    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.

    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.

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

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-10-19 01:55    [W:0.023 / U:35.012 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site