Re: No 100 HZ timer!

• Next message: Pete Zaitcev: "sk->state_chage is not called for listening sockets"
• Previous message: Rafael E. Herrera: "Sudden scsi timeouts on main disk."
• In reply to: Bret Indrelee: "Re: No 100 HZ timer!"
• Next in thread: george anzinger: "Re: No 100 HZ timer!"
• Reply: george anzinger: "Re: No 100 HZ timer!"
• Reply: Horst von Brand: "Re: No 100 HZ timer!"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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
-
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/

• Next message: Pete Zaitcev: "sk->state_chage is not called for listening sockets"
• Previous message: Rafael E. Herrera: "Sudden scsi timeouts on main disk."
• In reply to: Bret Indrelee: "Re: No 100 HZ timer!"
• Next in thread: george anzinger: "Re: No 100 HZ timer!"
• Reply: george anzinger: "Re: No 100 HZ timer!"
• Reply: Horst von Brand: "Re: No 100 HZ timer!"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

This archive was generated by hypermail 2b29 : Sun Apr 15 2001 - 21:00:20 EST