Re: Variable-block memory managers bad in realtime

[Jon S Anthony <jsa@synquiry.com>]

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.

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 partiuclar, 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.

> 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.

> 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.

/Jon

-- 
Jon Anthony
Synquiry Technologies, Ltd., Belmont, MA 02178, 617.484.3383
"Nightmares - Ha!  The way my life's been going lately,
 Who'd notice?"  -- Londo Mollari