From: jhallen@world.std.com (Joseph H Allen)
Subject: Re: Memory management models (plus new malloc library described)
Organization: The World Public Access UNIX, Brookline, MA
Date: Tue, 5 Jan 1993 07:21:06 GMT

In article <1ia6tqINNaps@uwm.edu> markh@csd4.csd.uwm.edu (Mark) writes:
>   I'm looking for efficient models for source-level memory management that
>resolve fragmentation and allows contiguous segments of arbitrary size to be
>allocated.  They should be compared to the model which I presently use:
>
>        * Free lists maintained for blocks of size 2^N for each N < 32,
>
>        * Allocated segment are fit into the smallest available block of
>          size 2^N, using the Nth free-list if it's non-empty.
>
>Default malloc is insufficient because it doesn't normally protect against
>external fragmentation,

>   The model above guarantees that fragmentation will always lie under 50%,
>that allocation will usually be a constant-time operation and that deallocation
>will always be constant time.

I've found that fragmentation (I think you mean the tendancy for free blocks
to get more numerous on the small end) is not really that much of a problem
compared to other things.  In your algorithm for example:  although what you
call fragmentation will be less than 50%, the amount of memory you waste is
large since you also have to count what's left in the free list.

In any case, GNU Malloc works the same as your method for blocks smaller
than 4K, except that it will combine free blocks together into other powers
of 2, and works as a simple first-fit singly-linked free-list allocator for
blocks larger than 4K.  It's quite fast, wastes a bit less space than your
method, but sill wastes quite a bit compared with other slower algorithms.

The most space-effecient non-garbage collecting algorithm I've found (for
flat random distributions of mallocs, frees and reallocs) is best-fit.  This
is when you pick the smallest free block which will fit the malloc request
and always return the balance of the block back to the free list.  Also free
blocks always get coalesced when they can.  Usually I try to give back space
to the OS by calling sbrk when the last block is freed.  This helps only a
little, but it does help.

Although I usually use flat random numbers for testing malloc schemes, I've
found that less random tests only amplify the differences between schemes. 
So in the real world, best-fit is much better than GNU malloc.

The problem with best fit is that since you have to do a linear search
through a linked list, it's really slow (like hundreds or thousands of times
slower than GNU malloc).

I found that this can be fixed by using a database.  The best database I
found is the 'skip-list' scheme described in this newsgroup some time ago. 
It's best because the constant time cost is extremely small.

Anyway I made a new memory allocator using this (it's included as part of my
JOE editor.  Get it from anonymous ftp from world.std.com, file
src/editors/joe1.0.7.tar.Z.  The allocator is in heap.c/heap.h and requires
blocks.c/blocks.h, random.c/random.h and config.h).

I compared it with GNU malloc for 100,000 random mallocs, reallocs and
frees.  It ended up wasting 50% less memory.  I don't remember the exact
test results, but I think GNU malloc had 4 MB of core allocated of which 2MB
was actually requested, where mine had 3 MB of core allocated.

It used only 50% more CPU time than GNU malloc.  This is really astounding
considering how fast GNU malloc is.  That a best fit scheme is even in the
same order of magnitude is really amazing.  Skip-lists are really cool.  :-)
one neat thing is that in the paper that described skip-lists, the inventor
suggests that you use 1/2 or 1/4 as easy approximations of 1/e for the
random number distribution.  It turned out that using 1/e instead of 1/2 or
1/4 translated into significant CPU-time differences, so that was used
instead.

>and source-level paging is insufficient because it
>doesn't resolve the need for contiguity.

I started out as a microprocessor assembly langauge programmer.  I have to
remind myself time and time again that using malloc on UNIX is ok and that I
don't have to make up some difficult page allocation scheme.  But I still
have this feeling that I'm cheating :-)
-- 
/*  jhallen@world.std.com (192.74.137.5) */               /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
Newsgroups: comp.programming