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/
This archive was generated by hypermail 2b29 : Sun Apr 15 2001 - 21:00:20 EST