Please do grow your buffers exponentially: multiplying the size of your array by c at each reallocation yields amortized O(1) operations for any c > 1.
But please don't use c=2: c=1.5 is a much better constant.
The reason is that that when you grow the array one element at a time, after i reallocations your memory is like this:
<previous allocations>|c^i| |c^(i+1)|
old new
Since the previous allocations are freed already, you would like to place the new allocation in the freed space. How much is that? Well that's 1 + c + c^2 + ... + c^(i-1), that is (c^i - 1)/(c - 1). For c=2 that's 2^i - 1, so the new allocation can never fit.
It turns out that if c is smaller than the golden ratio (1.618...) then eventually new allocations will fit in the freed area. It is a nice exercise to see how the golden ratio shows up.
c=1.5 is a generally used constant also because it's easy to compute as n + n/2.
I don't understand; why hang on to previously freed array space to reuse for new iterations of the array? Isn't the whole point of freeing array space to allow arbitrary other data to use it as needed?
No one is really hanging on to previously freed space (except for the allocator, or if you're using a custom object pool allocation scheme) specifically for new versions of the array.
But if you're allocations look like this:
array = malloc(<capacity>);
// do stuff with array
free(array);
...
array = malloc(<new capacity>);
// do stuff with array
free(array);
with no other allocations in between then it is possible that the allocator might reuse previously freed array space.
I guess let me put my question another way: what's the advantage of being able to reuse previously freed array space for new iterations of the array, vs. having that space used for something else and using some other space for new iterations of the array?
It seems to me that, when reallocating, one ought to be able to say to the memory allocator "I want you to reallocate this array to a new size of [whatever]; go find a contiguous block of size [whatever], possibly overlapping the current array but not overlapping any other allocated memory, and copy/move the contents over there appropriately". (I believe that's what the "realloc" function does, no?). And, in that context, I can't see why any of the golden ratio stuff matters (though, of course, exponential resizing is still useful as noted).
In embedded apps I use a 'bucket heap' where freed memory goes on a list by size e.g. 64, 128, 256 etc. So allocations come from their bucket only; freed to their bucket. Never re-used.
Why use it? Because each bucket is separately managed; no unexpected garbage collection; hardly any collisions. And at runtime you quickly reach your working-set and fill buckets with enough pieces. Its amazingly fast, simple and has very predictable latency. Which matter in embedded environments.
O(1), or O(log N)? Small difference but I was just having this argument yesterday. Each reallocation takes O(1) time (we assume), and you need O(log N) reallocations to grow by a cumulative factor of N.
By "amortized O(1)", what's meant is essentially O(1) _per array element_; in other words, O(N) overall to reach a size of N. Note that this is when considering each reallocation to take time O(current length of array) [as one has to copy over all the current elements to the new space].
Ah yeah, I was double wrong. I see now that N insertions require a maximum of 2N-3 copy operations (with a growth factor of 2), so O(1) amortized. Thanks!
But please don't use c=2: c=1.5 is a much better constant.
The reason is that that when you grow the array one element at a time, after i reallocations your memory is like this:
Since the previous allocations are freed already, you would like to place the new allocation in the freed space. How much is that? Well that's 1 + c + c^2 + ... + c^(i-1), that is (c^i - 1)/(c - 1). For c=2 that's 2^i - 1, so the new allocation can never fit. It turns out that if c is smaller than the golden ratio (1.618...) then eventually new allocations will fit in the freed area. It is a nice exercise to see how the golden ratio shows up.c=1.5 is a generally used constant also because it's easy to compute as n + n/2.