memory management of array

ZHOU Zhenyu rinick at
Sun Dec 21 04:03:57 PST 2008

mastrost Wrote:
> If you reallocate the memory using (requiredSize*k1), you will do about 'n' reallocations, wich means 'n' copies of the buffer, which cost you 'n' each time you do so. So your algo costs about n^2 operations.
> If you reallocate the memory using (oldSize * K2) you will do about 'log(n)' reallocations. That is why the stl is using (oldSize * 2). When using (oldSize*k2), the memory used is the same order of magnitude than with (requiredSize * k1), but the execution time becomes n*log(n) instead of n^2.
> This is just an asymptotic behaviour (this becomes more and more true if n is big), so in real life, it is not necessary true that oldSize*2 is really better. But if you cannot be sure that (requiredSize * K1) is better than (oldSize * K2), I think you should use (oldSize * k2).
> I have been tought this stuffs a couple of years ago, so I might be mistaken. Moreover I did not make the experience myself.

I found that (oldSize*k) will be about 20% slower than (requiredSize*k)
I thought they should be same, be the test result told me that (requiredSize*k) is always faster.
I don't know why that happened, maybe the reason is something related to the mechanism of GC.

More information about the Digitalmars-d mailing list