memory allocation/deallocation for tree (a prelimary summary)

[Phong Vo[drew]]

In article <1991Jan10.203552.9752 at portia.Stanford.EDU>, fangchin at portia.Stanford.EDU (Chin Fang) writes:
> 
> (1) use malloc as less often as possible, it is expansive. Always allocate in  
>     large chunks. enlarge space allocated using realloc(3C)(3X) if
>     necessary.
For every malloc implementation that I know of, every malloc request is
rounded up to a multiple of sizeof(double) and every allocated block
entails a hidden overhead of at least one word. So, yes, if you know
that you are allocating many objects of the same size, get large chunks
and use them as you need.
> 
>     One idea, putting an extra field in the node decl in addition to
>     the left and right pointers.  Allocate a bunch of them, link them.
Just a trivial observation but when a node is not used, either the left
or right pointer can be used for the link in the free list. There is no
need for another field.
> 
> Since many people asked me such.  So in the past few days, I tried Sun
> C libs as well.  The outcome?  No any order would produce the same 
> address lists.  All bats are off!  Can someone explain this?
Sun malloc coalesces adjacent free blocks immediately. So any order of
free will ultimately result in one big free block. The older SysV malloc does
not merge adjacent free blocks until it is necessary to do so. In addition,
after a block is free, the search for the next malloc request is started
at that address. Therefore, only a reverse order free sequence will put the
search for the next round of malloc at the right place (as you want it).
> 
> So whether the order of allocation/deallocation matters is still not 
> too clear to me.  I guess only computational experiments would sort
As far as efficiency is concerned, it shouldn't make any difference,
especially if you are using a more modern malloc like Sun's or SysVr4's.
For correctness, when deleting tree and list structures, it may be vital
that some form of the reverse order is used. For example, the following
piece of code to free a list is fatally wrong but it'll work with some
mallocs such as SysVr3's or BSD's:
	for(e = list; e; e = e->next)
		free(e);