george anzinger wrote:
> > A pointer-based priority queue is really not a very complex thing, and
> > there are ways to optimise them for typical cases like the above.
> >
> Please do enlighten me. The big problem in my mind is that the
> pointers, pointing at points in time, are perishable.
Um, I'm not sure what perishability has to do with anything. Timers at
the moment can be added, deleted and destroyed and it's no big deal.
Look in an algorithms book under "priority queue". They usually don't
say how to use a heap-ordered tree -- usually it's an array -- but you
can use a tree if you want. In such a tree, each timer has a link to
_two_ next timers and one previous timer. (The previous timer link is
only needed if you can delete timers before they expire, which is
required for Linux).
I'm not saying saying a heap-ordered tree is fastest. But it's ok, and
doesn't require any more storage than the `struct timer' objects
themselves.
It's possible to optimise this kind of data structure rather a lot,
depending on how you want to use it. Linux' current timer algorithm is
a pretty good example of a priority queue optimised for timer ticks,
where you don't mind doing a small amount of work per tick.
One notable complication with the kernel is that we don't want every
timer to run at its exactly allocated time, except for some special
timers. For example, if you have 100 TCP streams and their
retransmission times are scheduled for 1.0000s, 1.0001s, 1.0002s, etc.,
you'd much rather just process them all at once as is done at the moment
by the 100Hz timer. This is because cache locality is much more
important for TCP retransmits than transmit timing resolution.
There's literature online about this class of problems: look up "event
set" and "simulation" and "fast priority queue".
enjoy,
-- Jamie
-
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:16 EST