memory allocation

[T. William Wells]

In article <33184 at cca.CCA.COM> g-rh at CCA.CCA.COM (Richard Harter) writes:
: In article <733 at proxftl.UUCP> bill at proxftl.UUCP (T. William Wells) writes:
: >In article <1262 at micomvax.UUCP> belanger at micomvax.UUCP (Robert Belanger) writes:
: >:       We are in the process of speeding up memory allocation. Because we
: >: have a CPU with a linear address space, but no (easy) access to disk...
:
: >One scheme comes to mind for fast memory allocation: the "buddy
: >system allocator". ...
:
: Best fit is also very fast, albeit not as fast a carefully implemented
: buddy system. ...
:       There is a fixed overhead price in space for each allocated block.
: 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.

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.

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.

---
Bill
novavax!proxftl!bill