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/