lkml.org 
[lkml]   [2001]   [Apr]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: No 100 HZ timer!
    Bret Indrelee wrote:
    >
    > On Thu, 12 Apr 2001, george anzinger wrote:
    > > Bret Indrelee wrote:
    > > > Keep all timers in a sorted double-linked list. Do the insert
    > > > intelligently, adding it from the back or front of the list depending on
    > > > where it is in relation to existing entries.
    > >
    > > I think this is too slow, especially for a busy system, but there are
    > > solutions...
    >
    > It is better than the current solution.

    Uh, where are we talking about. The current time list insert is real
    close to O(1) and never more than O(5).
    >
    > The insert takes the most time, having to scan through the list. If you
    > had to scan the whole list it would be O(n) with a simple linked list. If
    > you insert it from the end, it is almost always going to be less than
    > that.

    Right, but compared to the current O(5) max, this is just too long.
    >
    > The time to remove is O(1).
    >
    > Fetching the first element from the list is also O(1), but you may have to
    > fetch several items that have all expired. Here you could do something
    > clever. Just make sure it is O(1) to determine if the list is empty.
    >
    I would hope to move expired timers to another list or just process
    them. In any case they should not be a problem here.

    One of the posts that started all this mentioned a tick less system (on
    a 360 I think) that used the current time list. They had to scan
    forward in time to find the next event and easy 10 ms was a new list to
    look at. Conclusion: The current list structure is NOT organized for
    tick less time keeping.

    George
    -
    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-03-22 13:25    [W:0.035 / U:0.004 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site