Re: Variable-block memory managers bad in realtime

[gwinn@res.ray.com (Joe Gwinn)]

In article <ufk9cu7bjl.fsf@synquiry.com>, Jon S Anthony <jsa@synquiry.com>
wrote:

> gwinn@res.ray.com (Joe Gwinn) writes:
> 
> > Waste lots of memory, actually.  Sometimes we don't have the memory
> > to waste, or we would rather waste it on something else.  I don't
> > know that these algorithms have guaranteed absolute upper bounds on
> > response time, and absolute protection against fragmentation,
> > together with the requisite efficiency.
> >
> > Fixed-block allocators waste no space, and have absolutely constant
> > service time.
> 
> What in the world are you talking about?  Fixed block allocators waste
> space up the wazoo unless (of course) you _always_ require the _exact_
> size they provide.

See below.  We get to pick the block sizes to suit the application, so the
wastage isn't a problem, and we really like the constant-time behaviour.


> Second, you should probably take a look at some of the work on
> allocators and collectors in the GC literature.  Including stuff on
> compaction.  Many of these do indeed have guranteed worst case
> behaviors.  In particular, check out Henry Baker's work on this stuff
> (including his realtime GC papers).  These may or may not work for
> you, but unless you are targetting realtime engine control, or some
> such, they will likely be OK.

Will do.  Do you have more specific references?  Thanks.

We are doing the equivalent of engine control in many places.


> > True, but our applications are happy with from three to six different
> > block sizes; the specific spectrum of sizes varies with the specific
> > application.
> 
> OK, fine, then maybe a suite of 3-6 fixed size allocators will work
> for you.  Of course, this may well be memory inefficient as well, but
> if it is good enough, go for it.

It *does* work.  These values are taken from at least a billion dollars
worth of fielded systems.


> > Remember, I don't have to solve as general a problem as does
> > a compiler or runtime writer, and I am more interested in predictability
> > and behaviour under overload and near overload than memory efficiency per
> > se.  Nor do I agree that there is one "best" algorithm, for all
> > applications.
> 
> OK, I can pretty much agree with all of this.

Thanks.


Joe Gwinn