Messages in this thread | | | Date | Tue, 18 Oct 2005 16:52:56 -0700 | From | Tim Bird <> | Subject | Re: [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/
| |