Memory Allocation

[Tom Stockfisch]

In article <10206 at smoke.BRL.MIL> gwyn at brl.arpa (Doug Gwyn) writes:
>In article <461 at chem.ucsd.EDU> I (Tom Stockfisch) write:
>>You waste up to a factor of 4 with a power-of-2 implementation,
>>not including fragmentation.

>..., I see a factor of two (not four) here,...

Here is the problem, at least with our BSD malloc():  I am reading in data
that needs to be put in one contiguous array.  I call malloc() with a certain
amount, fill that up, call realloc(), fill that up, etc.  Every time
that I cross a power of two boundary, realloc() puts my old memory on the
free list for the previous power of two and gets a whole new chunk.  Thus,
for a large final array size of n = (2^m) + 1 it has allocated
2^4 + 2^5 + 2^6 + 2^7 + 2^8 + ... + 2^(m+1), which is nearly 2^(m+2), which
is nearly 4*n.

-- 

|| Tom Stockfisch, UCSD Chemistry	tps at chem.ucsd.edu