memory allocation

[Richard Harter]

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".  This is *extremely* fast.  The drawback is
>that you must allocate in blocks of certain sizes.  For example,
>the standard method uses blocks of size k*2**n, where k is a
>constant and n is a parameter...

Best fit is also very fast, albeit not as fast a carefully implemented
buddy system.  The trick is round sizes up modulo a small convenient 
power of two to reduce the range of requests to a reasonable range,
and then maintain a separate list for each size.  To access the lists
quickly maintain a table of list head pointers.  [There are some tricks
for searching the table more efficiently than a linear search.]  For
example the round factor might be 8 and the table size 128, which
takes care of requests up to 1024.  For blocks beyond that size you can
maintain a single "large block" list.  If you have numerous large requests
you can have an additional table for large blocks going up by powers of
two.  There is a fixed overhead price in space for each allocated block.
Writing a fast "best-fit" allocator is an interesting exercise in
programing.
-- 

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