Re: 2.6.13-rt6, ktimer subsystem

[George Anzinger]

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   george@xxxxxxxxxx
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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/