Path: utzoo!attcan!uunet!samsung!usc!chaph.usc.edu!alcor.usc.edu!jeenglis
From: jeenglis@alcor.usc.edu (Joe English Muffin)
Newsgroups: comp.os.msdos.programmer
Subject: Re: malloc() and free() is order important
Message-ID: <12290@chaph.usc.edu>
Date: 2 Oct 90 03:01:19 GMT
References: <20681@orstcs.CS.ORST.EDU>
Sender: news@chaph.usc.edu
Distribution: na
Organization: Joe's Homeopathic Hangover Remedies
Lines: 97
Nntp-Posting-Host: alcor.usc.edu

duvalj@bionette.cgrb.orst.edu (Joe Duval) writes:

>Hi,

>  I am using Turbo C on a 386-20 with 1 Meg of RAM.

Which memory model?  If it's small, tiny, or medium,
that could be part of the problem.

>My question is does the order of mallocing and freeing data matter?  Should
>whatever I malloc first be free'd last or the opposite?  My program is showing
>inconsistency that seems to relate to the malloc'ing and free'ing I am doing.

No; you can free() mallocked areas in any order,
as long as you don't free() the same thing twice.


>Here is how my program "works":

[ ... Much deleted ]

>#define LINEDELTA 100
>#define STRLEN     80

>typedef char element[STRLEN] /* will be a line of a data file, lines can be up
>								to 80 characters long */

>main ()
>{	element	*data1, *data2;
>
>	data1 = (element *) malloc (LINEDELTA*sizeof(element *));
>	data2 = (element *) malloc (LINEDELTA*sizeof(element *));

First, you really should check malloc's return
value.  It just might fail and return NULL.

>  /* One of the files is usually about 20 times the size of the other.  If I
>	 read in the smaller one first, the data in the smaller one gets trashed
>	 when I read in the data to the second one.  What can I do to avoid that.
>	 things are fine if I read in the data for the larger one first (I may
>	 not know which of the two is the larger at run time)
>   */

>	lines1 = fillarray ("test1", data1);
>	lines2 = fillarray ("test2", data2);

I would guess, that since fillarray() [description
deleted] calls realloc() several times, the heap
is probably getting too fragmented to allocate
any more big chunks, and one of the realloc()s
eventually fails.

You could try using an exponentially increasing
realloc() size instead of asking for
(current_size + LINEDELTA) elements each time.
That will decrease the number of realloc()s from
O(n) to O(log n), which will probably help.
Some good choices would be: current_size * 2
(O(2^n)) or current_size + last_size (O(Fib(n))).

As for malloc() in general, here are the rule-of-thumb
guidelines that I use:

+ Never malloc() lots of little items; malloc() off a
  big chunk and hand it out a piece at a time.  If you
  need to free() the items individually, write your
  own free-list manager for each size item.  (Or write
  a general-purpose one; that's what I did.)

  This saves malloc() overhead on each item allocated,
  and reduces fragmentation on many implementations of
  the allocator.

+ If you must malloc() small structures, malloc()
  the big stuff first.

  This helps fragmentation on most implementations of
  the allocator.

+ Don't use realloc() to dynamically resize things;
  use linked-lists or other dynamic structures.

+ If you must realloc(), then realloc() exponentially
  increasing sizes.

  This helps fragmentation on most implementations of
  the allocator.


(Why "on most implementations of the allocator?"
Malloc()/free() can be implemented in several
ways; I have no idea which one Turbo C uses.)


--Joe English

  jeenglis@alcor.usc.edu