Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Memory Allocation (was Re: binary data files)
Message-ID: <17252@mimsy.UUCP>
Date: 3 May 89 06:10:21 GMT
References: <10946@bloom-beacon.MIT.EDU> <12546@ut-emx.UUCP> <29978@apple.Apple.COM>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 26

In article <29978@apple.Apple.COM> desnoyer@Apple.COM (Peter Desnoyers)
writes:
-... This [additive] 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)
-
-... 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

This analysis is correct, if you assume no interaction with the memory
allocator itself.  But in fact the current BSD (modified Caltech buddy
system) allocator will waste much more memory than this.  (If you can
reuse the smaller pieces later, they will not be `wasted', just tieing
up resources for a while.  Or is that `waste'? :-) )

I get the feeling that some future BSD will have six different malloc
library routines. . . .
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris