From: george anzinger <george@mvista.com>
To: Bret Indrelee <bret@io.com>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
high-res-timers-discourse@lists.sourceforge.net
Subject: Re: No 100 HZ timer!
Date: Thu, 12 Apr 2001 15:20:08 -0700 [thread overview]
Message-ID: <3AD62A18.8AC75605@mvista.com> (raw)
In-Reply-To: <Pine.LNX.4.21.0104121606360.10006-100000@fnord.io.com>
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).
>
> 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
next prev parent reply other threads:[~2001-04-12 22:21 UTC|newest]
Thread overview: 118+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-04-11 17:56 No 100 HZ timer! Bret Indrelee
2001-04-12 17:39 ` george anzinger
2001-04-12 21:19 ` Bret Indrelee
2001-04-12 22:20 ` george anzinger [this message]
2001-04-13 4:00 ` Bret Indrelee
2001-04-13 6:32 ` Ben Greear
2001-04-13 8:42 ` george anzinger
2001-04-13 10:36 ` Jamie Lokier
2001-04-13 16:07 ` george anzinger
2001-04-13 23:00 ` Jamie Lokier
2001-04-13 12:05 ` Horst von Brand
2001-04-13 21:53 ` george anzinger
2001-04-13 23:10 ` Jamie Lokier
2001-04-16 3:02 ` Ben Greear
2001-04-16 2:46 ` Jamie Lokier
2001-04-16 12:36 ` Mark Salisbury
2001-04-16 19:19 ` george anzinger
2001-04-16 20:45 ` Albert D. Cahalan
2001-04-16 21:29 ` Chris Wedgwood
2001-04-16 22:25 ` george anzinger
2001-04-16 23:57 ` Mark Salisbury
2001-04-17 0:45 ` george anzinger
2001-04-17 12:12 ` Mark Salisbury
2001-04-17 12:51 ` Mark Salisbury
2001-04-17 18:53 ` george anzinger
2001-04-17 19:41 ` Jamie Lokier
2001-04-23 8:05 ` Ulrich Windl
2001-04-23 13:22 ` Mark Salisbury
2001-04-16 2:41 ` Ben Greear
-- strict thread matches above, loose matches on Subject: below --
2001-08-01 17:22 No 100 HZ timer ! george anzinger
2001-08-01 19:34 ` Chris Friesen
2001-08-01 19:49 ` Richard B. Johnson
2001-08-01 20:08 ` Mark Salisbury
2001-08-01 20:33 ` george anzinger
2001-08-01 21:20 ` george anzinger
2001-08-02 4:28 ` Rik van Riel
2001-08-02 6:03 ` george anzinger
2001-08-02 14:39 ` Oliver Xymoron
2001-08-02 16:36 ` george anzinger
2001-08-02 17:05 ` Oliver Xymoron
2001-08-02 17:46 ` george anzinger
2001-08-02 18:41 ` Oliver Xymoron
2001-08-02 21:18 ` george anzinger
2001-08-02 22:09 ` Oliver Xymoron
2001-08-02 17:26 ` John Alvord
2001-04-12 13:14 No 100 HZ timer! Bret Indrelee
2001-04-12 12:58 No 100 HZ timer ! Mark Salisbury
2001-04-11 9:06 schwidefsky
2001-04-10 14:42 schwidefsky
2001-04-10 12:54 schwidefsky
2001-04-10 11:38 schwidefsky
2001-04-10 11:54 ` Alan Cox
2001-04-10 7:29 schwidefsky
2001-04-10 7:27 schwidefsky
2001-04-09 15:54 schwidefsky
2001-04-09 18:30 ` Jeff Dike
2001-04-09 18:19 ` Mark Salisbury
2001-04-09 20:12 ` Alan Cox
2001-04-09 20:32 ` Mark Salisbury
2001-04-09 22:31 ` Mikulas Patocka
2001-04-09 22:35 ` Alan Cox
2001-04-10 11:43 ` David Schleef
2001-04-10 12:04 ` Mikulas Patocka
2001-04-10 12:31 ` David Schleef
2001-04-10 12:34 ` Mark Salisbury
2001-04-10 14:10 ` Mikulas Patocka
2001-04-10 13:35 ` root
2001-04-10 14:22 ` Andi Kleen
2001-04-10 15:43 ` Alan Cox
2001-04-12 5:25 ` watermodem
2001-04-12 8:45 ` Jamie Lokier
2001-04-10 17:15 ` Jamie Lokier
2001-04-10 17:27 ` Alan Cox
2001-04-10 17:35 ` Jamie Lokier
2001-04-10 18:17 ` Alan Cox
2001-04-10 18:24 ` Jamie Lokier
2001-04-10 19:28 ` george anzinger
2001-04-10 20:02 ` mark salisbury
2001-04-10 22:08 ` george anzinger
2001-04-11 0:48 ` Mark Salisbury
2001-04-11 2:35 ` george anzinger
2001-04-12 0:24 ` Mark Salisbury
2001-04-11 16:11 ` Jamie Lokier
2001-04-11 16:59 ` george anzinger
2001-04-11 18:57 ` Jamie Lokier
2001-04-11 19:21 ` John Alvord
2001-04-12 8:41 ` Jamie Lokier
2001-08-01 1:08 ` george anzinger
2001-08-11 11:57 ` Pavel Machek
2001-08-14 15:59 ` Jamie Lokier
2001-08-14 16:57 ` george anzinger
2001-04-10 19:50 ` Zdenek Kabelac
2001-04-11 11:42 ` Maciej W. Rozycki
2001-04-11 16:13 ` Jamie Lokier
2001-04-12 9:51 ` Maciej W. Rozycki
2001-04-10 19:42 ` Zdenek Kabelac
2001-04-10 12:19 ` Mark Salisbury
2001-04-10 17:51 ` yodaiken
2001-04-11 18:43 ` Oliver Xymoron
2001-04-10 12:11 ` Mark Salisbury
2001-04-10 5:51 ` Andi Kleen
2001-04-10 9:33 ` Martin Mares
2001-04-10 10:00 ` Albert D. Cahalan
2001-04-10 12:14 ` Mark Salisbury
2001-04-11 5:55 ` Karim Yaghmour
2001-04-10 11:18 ` Alan Cox
2001-04-10 12:02 ` Andi Kleen
2001-04-10 12:12 ` Alan Cox
2001-04-10 12:27 ` Mark Salisbury
2001-04-10 12:32 ` Andi Kleen
2001-04-10 12:36 ` Alan Cox
2001-04-10 12:37 ` Andi Kleen
2001-04-10 18:45 ` Stephen D. Williams
2001-04-10 19:59 ` Andi Kleen
2001-04-10 12:07 ` Mark Salisbury
2001-04-10 12:45 ` Andi Kleen
2001-04-10 12:42 ` Mark Salisbury
2001-04-10 12:54 ` Andi Kleen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3AD62A18.8AC75605@mvista.com \
--to=george@mvista.com \
--cc=bret@io.com \
--cc=high-res-timers-discourse@lists.sourceforge.net \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).