Memory Allocation (was Re: binary data files)

[Chris Torek]

In article <29978 at apple.Apple.COM> desnoyer at 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 at mimsy.umd.edu	Path:	uunet!mimsy!chris