Re: No 100 HZ timer!

[Jamie Lokier <lk@tantalophile.demon.co.uk>]

Ben Greear wrote:
> > Note that jumping around the array thrashes no more cache than
> > traversing a tree (it touches the same number of elements).  I prefer
> > heap-ordered trees though because fixed size is always a bad idea.
> 
> With a tree, you will be allocating and de-allocating for every
> insert/delete right?

No, there is no memory allocation.

> On cache-coherency issues, wouldn't it be more likely to have a cache
> hit when you are accessing one contigious (ie the array) piece of
> memory?  A 4-k page will hold a lot of indexes!!

No, because when traversing an array-heap, you don't access contiguous
entries.  You might get one or two more cache hits near the root of the
heap.

> To get around the fixed size thing..could have
> the array grow itself when needed (and probably never shrink again).

You could to that, but then you'd have to deal with memory allocation
failures and memory deadlocks, making add_timer rather complicated.
It's not acceptable for add_timer to fail or require kmalloc().

-- Jamie