rtm@grenada.UUCP (Richard Minner) (10/21/89)
In article <1175@svx.SV.DG.COM> gary@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 ||
gwyn@smoke.BRL.MIL (Doug Gwyn) (10/23/89)
In article <427@grenada.UUCP> rtm@grenada.UUCP (Richard Minner) writes: >One last quick invitation to flame: Am I abusing the term "heap" here? There are two fairly standard technical meanings for "heap". One of them denotes a partially ordered array meeting certain constraints, and is encountered primarily is discussions about sorting algorithms. The other denotes a pool of dynamically allocated memory. The use of heap in its colloquial "pile" meaning is discouraged.