lkml.org 
[lkml]   [2001]   [Apr]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: No 100 HZ timer!
Date
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/

\
 
 \ /
  Last update: 2005-03-22 13:25    [W:0.194 / U:1.504 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site