Messages in this thread | ![/](/images/icornerl.gif) | | Date | Thu, 12 Apr 2001 15:20:08 -0700 | From | george anzinger <> | Subject | Re: 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/
| ![\](/images/icornerr.gif) |