Anyone know this paper?

[gregory.menke at gsfc.nasa.gov]

"Joel Sherrill <joel at OARcorp.com>" <joel.sherrill at OARcorp.com> writes:
 > gregory.menke at gsfc.nasa.gov wrote:
 > > "Joel Sherrill <joel at OARcorp.com>" <joel.sherrill at OARcorp.com> writes:
 > >  > gregory.menke at gsfc.nasa.gov wrote:
 > > 
 > > No, they seemed to spend their time vaporing away about network
 > > traffic simulations and bitmap twiddling without presenting content-
 > > or any examples of just how their algorithms help wireless and
 > > multimedia applications- or any examples of said applications as
 > > depoyed on embedded systems.  I got the vague impression that they
 > > implemented a C++ layer on top of the OS heap functions to expose
 > > their own memory allocation routines.  Then they claimed those big
 > > percentage "gains" without defintions or data.
 > 
 > Yes.  It is amazing what managing your own free list of
 > inactive structures of a known type can do for performance. :)

Yep.. actually the slab allocator does that for each size grade its
configured for, with the wrinkle that the OS can ask each pool of free
objects to free unused objects if there is memory pressure.  The
Solaris implementation (closed source, unfortunately) allows user
software to register constructor and destructor callbacks per object
type so the minimum of reinitialization is required at allocation-time
and zero-fill can be skipped.  I don't know if Linux's implementation
goes as far as that.  Maybe its time for me to check around for
reference implementations...

 
 > >  No doubt all will
 > > become clear after they get funding for another round of
 > > research.. lol ;)
 > 
 > We're not being cynical are we? ;)

Who, me?  :)


 > >  > 
 > >  > I believe that there is no perfect algorithm for all real-time
 > >  > embedded systems.  It would be great to be able to choose from
 > >  > a variety of heap, CPU scheduling, disk scheduling and disk
 > >  > caching algorithms based upon your application requirements.
 > >  > 
 > >  > It seems that no algorithm is perfect for every situation.
 > > 
 > > I agree.  That said, I'm a big fan of the slab concepts, I suppose
 > > their downside is complexity & subtlety- its great for the user but
 > > you have to put your software weenie hat on to understand what its
 > > doing inside.
 > 
 > I am not opposed to replacing the supercore heap or making the
 > malloc family use a different algorithm.

In my copious spare time, (yeah sure), I was thinking of setting one
up.  Last time we talked, you mentioned some profiling you did on heap
performance- do you have any stats for that?  If so, it might help
establish a means to compare a different algorithm.

In the slab docs referenced above, the allocator was tested in Solaris
2.6 (iirc), by replacing the conventional OS allocator with it.  They
measured a substantial performance benefit- even on uniprocessor
systems.  The theory there was the free-list per size grade of
allocation kept allocs/frees fast, and the persistence of freed
objects tended to be cache-friendly.

Its of particular benefit on SMP systems, the critical sections move
out of the allocation code and essentially into the heap extender
routines, so contention per allocation drops nearly to zero.  The
algorithm appears to be highly scalable as well- I think it was tested
up into machines with 16 or more cpu's.

Gregm