fangchin@portia.Stanford.EDU (Chin Fang) (01/11/91)
First of all I would like to give my thanks to all people who
have kindly responded to me (so far more than ten, still coming).
From the rate of response, it seems that my question was not a too
boring one. Most people even sent me pieces of codes to make their
ideas clear.
I am not ready to make a detail summary so far. So I briefly mention
the most common suggestion to my problem, assuming I still use
balanced red-black tree for data caching.
(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.
(an implication of this is: blindly using the utilities in the
Appendix D of Numerical Receipt to get so called completely
dynamic memory management MAY cost one A LOT! depending the # of calls.
Rewrite them so that the following. See (2) (3))
(2) a private management will speed up process and reduce running costs
significantly most of the time. Using a linked list is the most
common suggestion.
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.
When start building tree, each time get a node from this linked
list instead call malloc() directly.
Two benefits: cheaper. less malloc() calls.
memory-wise more efficient, since malloc() spends
less memory for housekeeping. (=> faster too)
(3) If nodes on the linked list run out, just allocate another chunck,
break them up into nodes, and join them to the existing linked
list again. (see also (1))
(4) If a tree node is deleted, put it back to the linked list for
future use.
(This part is hard to me, because tree node deletion for Red-black
balanced 2-3-4 tree is difficult to write simple and well.
Particularly I had to deal with key cascades, ie. primary key,
2ndary key, 3rd key, not just one int key that one typically reads in
data structures text books.
I would appreciate any sample that you consider good and am
willing to let me take a look. Please email.)
(5) If the tree needs to be take apart completely. Just scan the
linked list, free it all. The tree vaporizes too since it's
nodes are all free-ed. (For black-red tree, if dummy nodes are
used, there are two remaining, head and another ground node,
but these two are easy to deal with).
(6) If data caching becomes involved to implement, building dynamical
data structures may not gain due to the complexity of codes and
the time they require to execute. A simple static (and/or global)
storage may do the job cheap and efficiently too. (Yeah, you are
right.....)
Many people asked me where I got my impression that I had to deallocate
in EXACTLY the reverse order. I would like to answer this here too.
I do programming most of the time on my i386 box running AT&T System V
R.3.2. for which I believe malloc(3C) uses circular list for
maintaining free list.
I don't have access the src. This is the impression that I got from
reading the man page in Prentice-Hall UNIX System V/386 Programmer's
Reference Manual. I did the following testing too:
allocate a chunck of blocks, save their addresses.
deallocate them in different order and after done, reallocate the same
number of blocks, and write out their addresses, compare with the
saved addresses to see which order of allocation/deallocation would
give me the same lists. It turned out only precisely the reverse
order would give me such on my machine (Thanks Steve).
Also see ps .2 below.
Anyone who has access to an i386 box running ATT UNIX should get the
same results as mine. I think Interactive, Micropot, UHC, ESIX, and SCO
are all from the same place basically other than some "enhancement?"
added later on by different vendors. But as long as the C Software
Developement Set is pcc based, libs should be the same and therefore
malloc()/free() would behave the same as mine. (SCO and Interactive
may provide different compilers, eg MS C for SCO).
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?
I haven't try DEC's C libs on VAX/MIPS and IBM C libs on RS/6000 yet.
I will however. (Note, what I used was not the new ANSI C libs from
SUN, it was the old implementation that comes with SUN OS 4.01?).
So whether the order of allocation/deallocation matters is still not
too clear to me. I guess only computational experiments would sort
out a claim then. I will write some test codes and try to monitor
their run time memory usuage to see if any claim is valid in general
accross some popular C implementations.
Regards and Thanks again to all people who responded.
Chin Fang
Mechanical Engineering Department
Stanford University
fangchin@portia.stanford.edu
ps. 1. I normally always return people's mails. But due to my school's
mail server problems, I have been unable to reply to a few people.
I apologize. I saved all your input and I will try later when
the mail server becomes more stable.
2. The following simple codes were used for testing addresses:
*** Code Used (originally from Mr. Steve Clamage, steve@taumet.com, Thanks)***
#include <stdio.h>
#define DATASIZE 123 /* each allocation block */
#define RAYSIZE 10 /* how many blocks */
int main(void)
{
void *save[RAYSIZE];
int i;
for ( i = 0; i < RAYSIZE; ++i)
save[i] = (void *)malloc(DATASIZE); /* recording each block's add */
for (i = RAYSIZE-1; i >= 0; i -= 2)
free(save[i]); /* free odd #-ed blocks */
for ( i = 0; i < RAYSIZE; i +=2)
free(save[i]); /* free even #-ed blocks */
for ( i = 0; i < RAYSIZE; ++i)
printf("old=%u, new=%u\n", save[i], (void *)malloc(DATASIZE));
/* now compare */
return 0;
}
******** The following is for reverse order release ***************
#include <stdio.h>
#define DATASIZE 123 /* each allocation block */
#define RAYSIZE 10 /* how many blocks */
int main(void)
{
void *save[RAYSIZE];
int i;
for ( i = 0; i < RAYSIZE; ++i)
save[i] = (void *)malloc(DATASIZE); /* recording each block's add */
for (i = RAYSIZE-1; i >= 0; i --)
free(save[i]); /* free in reverse order */
for ( i = 0; i < RAYSIZE; ++i)
printf("old=%u, new=%u\n", save[i], (void *)malloc(DATASIZE));
/* now compare */
return 0;
}
*************** The above is for reverse order release **************kpv@ulysses.att.com (Phong Vo[drew]) (01/11/91)
In article <1991Jan10.203552.9752@portia.Stanford.EDU>, fangchin@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);