all this talk about which data structure to use and how to allocate memory is
waaaay premature.
there needs to be a clear definition of the requirements that we wish to meet,
including whether we are going to do ticked, tickless, or both
a func spec, for lack of a better term needs to be developed
then, when we go to design the thing, THEN is when we decide on the particular
flavor of list/tree/heap/array/dbase that we use.
let's engineer this thing instead of hacking it.
On Sun, 15 Apr 2001, Jamie Lokier wrote:
> 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
> -
> 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/
-- /*------------------------------------------------** ** Mark Salisbury | Mercury Computer Systems ** ** mbs@mc.com | System OS - Kernel Team ** **------------------------------------------------** ** I will be riding in the Multiple Sclerosis ** ** Great Mass Getaway, a 150 mile bike ride from ** ** Boston to Provincetown. Last year I raised ** ** over $1200. This year I would like to beat ** ** that. If you would like to contribute, ** ** please contact me. ** **------------------------------------------------*/- 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/
This archive was generated by hypermail 2b29 : Mon Apr 23 2001 - 21:00:19 EST