Xref: utzoo comp.unix.questions:27892 comp.lang.c:35070
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!ucsd!ucbvax!agate!eos!shelby!portia.stanford.edu!fangchin
From: fangchin@portia.Stanford.EDU (Chin Fang)
Newsgroups: comp.unix.questions,comp.lang.c
Subject: Memory allocation/deallocation for tree? Any good way?
Summary: How to keep the memory leak of a tree routine zero?
Keywords: tree, cache, malloc, free, tree-deletion, memory consumption
Message-ID: <1991Jan7.034619.4449@portia.Stanford.EDU>
Date: 7 Jan 91 03:46:19 GMT
Distribution: comp
Organization: AIR, Stanford University
Lines: 82

Hi everyone,
 
Not long ago I had to write a code to handle certain iterative floating
point intensive computations.  However, I discovered that the
algorithm allowed me to skip many repeated time-consuming fp
operations if I could somehow cache computed data in memory.  I was
in a situation that I had enough memory at my disposal, so reducing 
disk access would be my priority to speed up the process.

After some deliberation, I decided to use balanced tree as the way
to implement the data cache.  The algorithm for the balanced tree is
Drs. Guibas and Sedgewick's RB tree [1].  

The data that I had to cache were small float matrices (3x3 typical),
and I used Numerical Recipes [2] utility fuctions for creating and 
distorying these small matrices. The small matrices required some
quite heavy transendental function computations to generate and I 
deemed it unacceptable to have bad worst case performance.  So I
decided to implemented an in-memory cache using RB tree, this strategy
should result somewhat cheaper operation (I hope).

The problem I had (and still having) was how to keep the program's
memory consumption almost constant.  From what I understand, if my
malloc(3C) and free3(C) work correctly, as long as I make sure that
a sequence of malloced memory blocks are freed in EXACTLY the reverse 
order, my program's memory consumption would stay constant no matter
how many iterations it goes thru.  This has been my guideline in my
coding.  By the way, I always do C programming on UNIX machines.  

To achieve this for simple linear opertions is trival.  But for trees,
as far as I could (and can) see, I had to maintain a list for keeping
track of the order of creation of each node in the tree in order to
call free() in the right order.  To do so necessitated a mess in my code
that I was really unhappy.

Summerize, below is an outline of what I was doing

enter program

while (some conditions are true){

    get raw data from somewhere;

    form certain matrices and put them into nodes of a RB tree;

    perform some FP ops, go to the tree first to see if required matrices
    are available.  (They should, my algorithm guarantee this);

    distory the tree and release all memory (in the right order);

}

exit program

As obvious from above pseudo code, I was trying to trade expansive
memory operations for disgusting and far more expansive disk
accesses.  Note, each while loop may require a different tree, so it
is impossible to move the expansive memory allocation/deallocation to
outside the while (I wish it could be done).

Given this situation, could someone give me some suggestions for 
a better way of handling tree structure memory management? I don't
think the order tracking list that I am using is a good enough one.
and I believe there is still some memory leak somewhere as I can see
from the output of ps(1) (SZ term was growing).

Thanks in advance to anyone who responds.  Emails are most welcome,
if this question is of general interest, I will summerize.

Regards

Chin Fang
Mechanical Engineering Department
Stanford University
fangchin@portia.stanford.edu

[1] L. J. Guibas and R. Sedgewick. "A dichromatic framework for
    balanced trees." In Proc. 19th Ann. Symp. on Theory of Computing
    (1978): 8-21
[2] W. H. Press, B.P.Flannery, S.A. Teukolsky, W.T.Vetterling.
    Numerical Recipes in C, the art of scientific computing. 
    Cambridge University Press. 1988, Appendix D.