Path: utzoo!attcan!uunet!husc6!cca!g-rh
From: g-rh@cca.CCA.COM (Richard Harter)
Newsgroups: comp.lang.c
Subject: Re: memory allocation
Message-ID: <33184@cca.CCA.COM>
Date: 12 Sep 88 05:59:20 GMT
References: <1262@micomvax.UUCP> <733@proxftl.UUCP>
Reply-To: g-rh@CCA.CCA.COM (Richard Harter)
Distribution: comp.lang.c,comp.os.misc
Organization: Xerox Corporation, Cambridge, Massachusetts
Lines: 29

In article <733@proxftl.UUCP> bill@proxftl.UUCP (T. William Wells) writes:
>In article <1262@micomvax.UUCP> belanger@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.