memory allocation

[Richard Harter]

In article <778 at proxftl.UUCP> bill at proxftl.UUCP (T. William Wells) writes:
>In article <33184 at cca.CCA.COM> g-rh at CCA.CCA.COM (Richard Harter) writes:

>: Writing a fast "best-fit" allocator is an interesting exercise in
>: programing.

>Yes.  A exact- + worst-fit (a close relative of best-fit)
>allocator that I wrote as part of a real time kernel turned out
>to be one of the largest sections of the kernel; it was easily
>the most complicated.

It shouldn't be all that bad -- the best fit allocator I am using
currently runs about 200 lines of C, excluding comments.    That includes
both the allocate and the free routine.  However it doesn't have any
tuning code or any special code for handling small blocks.

>Two disadvantages come to mind for best-fit.  The first is the
>memory overhead.  If you keep track of the block size and make
>your minimum block size be two pointers, you can keep the
>overhead per allocated block to a single bit.  Of course, there
>is also the overhead of allocated but unused space; this is often
>small compared to a word per block, especially if the typical
>allocation amount is small.

I don't understand this comment.  If you mean to say that you can get
by with a single bit to mark whether a block is allocated or not, sure.
But the block size word will (on a ptr per word machine) take the same
space as a ptr.  

In any case, yes, there is more memory overhead for a best-fit allocator.
Personally I think this is a moot point.  The losses for fragmentation
and oversize allocation are much more signifigant unless you have a heavy
load of short requests.  However small block requests are best handled by
having dedicated blocks for the small blocks.

One point which I feel strongly about is that most allocators use the
blocks (free and allocated) to hold control information.  I think that
this is a mistake.  I put all control information in structures in a 
separate node space.  This adds overhead, but it makes life a lot safer.
Array indexing errors do not damage the allocator.  Free's can be checked
for validity.

>The second disadvantage is fragmentation: exact-fit + worst fit
>is supposed to create less fragmentation than best-fit.  I have
>not done the experiment, though.

I have -- I ran an extensive series of tests on allocator strategies a
number of years ago.  What it comes down to is that you can get the results
you want by picking your assumptions.  Exact fit (whether EF+WF) is important;
it defeats the 2/3 rule.  Given that, different size distributions and 
different allocate/free patterns give different results.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.