Re: No 100 HZ timer!

[Ben Greear <greearb@candelatech.com>]

Bret Indrelee wrote:
> 
> On Thu, 12 Apr 2001, george anzinger wrote:
> > 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).
> 
> I don't like the cost of the cascades every (as I recall) 256
> interrupts. This is more work than is done in the rest of the interrupt
> processing, happens during the tick interrupt, and results in a rebuild of
> much of the table.
> 
> -Bret

Wouldn't a heap be a good data structure for a list of timers?  Insertion
is log(n) and finding the one with the least time is O(1), ie pop off the
front....  It can be implemented in an array which should help cache
coherency and all those other things they talked about in school :)

Ben
> 
> ------------------------------------------------------------------------------
> Bret Indrelee |  Sometimes, to be deep, we must act shallow!
> bret@io.com   |  -Riff in The Quatrix
> 
> -
> 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/

-- 
Ben Greear (greearb@candelatech.com)  http://www.candelatech.com
Author of ScryMUD:  scry.wanfear.com 4444        (Released under GPL)
http://scry.wanfear.com               http://scry.wanfear.com/~greear