Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!ames!oliveb!apple!desnoyer
From: desnoyer@Apple.COM (Peter Desnoyers)
Newsgroups: comp.lang.c
Subject: Memory Allocation (was Re: binary data files)
Message-ID: <29978@apple.Apple.COM>
Date: 2 May 89 16:42:03 GMT
References: <10946@bloom-beacon.MIT.EDU> <12546@ut-emx.UUCP> <8758@csli.Stanford.EDU> <11021@bloom-beacon.MIT.EDU>
Organization: Apple Computer Inc, Cupertino, CA
Lines: 32

In article <11021@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes:
>
>Getting back to data files, it's not necessary to know how big
>they are while reading them.  Just use code like the following:
>
>	[ while data
>	    if (not room)
>		allocate another N bytes]
>

No, No. This algorithm takes O(n^^2) copies in the worst case. If you
change your code to:

	while data
	  if not room
	    current_size *= 2
	    ptr = realloc( ptr, curr_size)

(i.e. increase multiplicatively instead of additively) then you will
only need O(n) copies. There is a direct tradeoff between wasted memory
and cycles using this algorithm - if the multiplicative factor is N,
then :
   	copies = 1 + 1/N
	mean wasted memory (fraction) = (N-1)/2N

2 seems to be a good factor to use - you waste about 25% of your
allocated memory and the copy overhead is only equivalent to copying
the data once. If fitting as much data in memory as possible is more
important than having it work right the first time, don't use this
algorithm. Otherwise, it's fine. 

				Peter Desnoyers