Linked list node heap manager

[Richard Minner]

In article <1175 at svx.SV.DG.COM> gary at svx.SV.DG.COM () writes:
|a large number of linked lists, malloc'ing and free'ing space for nodes as
|needed.  There is a LOT of malloc'ing and free'ing going on, and nodes
|come in only a few sizes. ...

If there really are just a few different node *types*, and lots
of each type allocated, you'd probably be a lot better off with
some kind of "node heap manager" on top of malloc/free.  I
recently wrote one for a "generic" linked list library and it works
quite nicely.  (The "generic" linked lists are any for which the node
type is of the form:
    struct node { struct node *link; <other stuff, which may include
	       other links, e.g. for doubly linked lists or trees> };
and the library has various simple support functions.)

The idea is for the heap manager to never allocates *less* than
some minimum number of nodes at a time, in simple contiguous
blocks.  It then links the nodes together onto a freelist, from
which the application may allocate and free individual nodes.
This can save a lot of memory and be much faster. (It depends
on how wasteful and slow your malloc is, and also on your node
size.  Note that the node alloc/free can be simple macros
operating directly on the freelist, and only calling for a
block allocation when necessary.)

In the simplest implementation you have to free the entire heap
of nodes all at once, but this is still useful if your
application only uses more and more total nodes as it runs, or
if you already only throw out complete lists.  If you need to
be able to reclaim portions of the heap (i.e. single allocated
blocks) you'd probably have to add a "free flag" to the generic
node structure and some other yucky garbage collection stuff. (I
haven't had any need yet, so I'm not sure of the details.)

I'd be happy to provide some more details for anyone interested,
but I don't work for the Free Software Foundation and probably
can't give source, although it sure is nice stuff.  (Well, maybe
through email... oops)

One last quick invitation to flame: Am I abusing the term "heap" here?
Everyone I work with seems to think not, but I'd welcome a precise
"industry definition."  (Yeah, I should probably find a copy of
ANSI/IEEE standard 729 or whatever one of these days...)

P.S. In general, if you have a lot of small allocating/freeing to do
     it's a good idea to add a more efficient managing layer over
     malloc/free, if possible.  I think malloc is much happier dealing
     with a low "thrash quotient".

-- 
Richard Minner  || {uunet,sun,well}!island!rtm     (916) 447-7081 ||
                || Island Graphics Corporation     Sacramento, CA ||