Daniel Walker wrote:
On Thu, 2005-09-15 at 15:35 -0700, George Anzinger wrote:
In the early HRT patches the whole timer list was replaced with a hashed
list. It was O(N/M) on insertion where we could easily choose M (for a
while it was even a config option). Removal was just an unlink, same as
the cascade list.
To be clear on my take on this, as I understand it the rblist is
something like O(N*somelog 2). What is left out here is the fixed
overhead of F which is there even if N = 1. So we have something like
(F+O(f(N)) for a list. For the most part we don't look at F, but as
list complexity grows, it gets larger thus pushing out the cross over
point to a higher "N" when comparing two lists. I considered the rbtree
when doing the secondary list for HRT and concluded that "N" was small
enough that a simple O(N/2) list would do just fine as it would only
contain timers set to expire in the next jiffie.
The fact that we know in advance that a system is only going to a very
small number of these timers should be noted. You could just use a
regular list , and limit the total number of timers . I would hesitate
to stick a big data structure in when your only dealing with one or two
timers on average..
George, what's largest number of highres timers that someone might
need/want?
Well, the interesting thing is that, unless you change something, the
system has a current limit of 1000 posix timers. This can be changed,
but, I suspect it is not changed very often. And this handles all posix
timers, low and high res. Sleep is another thing, with a max of one
sleep timer per task. The ktimer list is also doing itimers, which are
also limited to the number of tasks.
As for data structures, a hashed list requires a "list head" for each
bucket while, I think the rblist only has one list head, but requires an
additional list head (or is it two) in the entry data structure so this
is a pay as you go list.
--
George Anzinger [email protected]
HRT (High-res-timers): http://sourceforge.net/projects/high-res-timers/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
| |
 |