What is the ideal growth rate for a dynamically allocated array?

Question

C++ has std::vector and Java has ArrayList, and many other languages have their own form of dynamically allocated array. When a dynamic array runs out of space, it gets reallocated into a larger area and the old values are copied into the new array. A question central to the performance of such an array is how fast the array grows in size. If you always only grow large enough to fit the current push, you'll end up reallocating every time. So it makes sense to double the array size, or multiply it by say 1.5x.

Is there an ideal growth factor? 2x? 1.5x? By ideal I mean mathematically justified, best balancing performance and wasted memory. I realize that theoretically, given that your application could have any potential distribution of pushes that this is somewhat application dependent. But I'm curious to know if there's a value that's "usually" best, or is considered best within some rigorous constraint.

I've heard there's a paper on this somewhere, but I've been unable to find it.

Answer 1

I remember reading many years ago why 1.5 is preferred over two, at least as applied to C++ (this probably doesn't apply to managed languages, where the runtime system can relocate objects at will).

The reasoning is this:

1. Say you start with a 16-byte allocation.
2. When you need more, you allocate 32 bytes, then free up 16 bytes. This leaves a 16-byte hole in memory.
3. When you need more, you allocate 64 bytes, freeing up the 32 bytes. This leaves a 48-byte hole (if the 16 and 32 were adjacent).
4. When you need more, you allocate 128 bytes, freeing up the 64 bytes. This leaves a 112-byte hole (assuming all previous allocations are adjacent).
5. And so and and so forth.

The idea is that, with a 2x expansion, there is no point in time that the resulting hole is ever going to be large enough to reuse for the next allocation. Using a 1.5x allocation, we have this instead:

1. Start with 16 bytes.
2. When you need more, allocate 24 bytes, then free up the 16, leaving a 16-byte hole.
3. When you need more, allocate 36 bytes, then free up the 24, leaving a 40-byte hole.
4. When you need more, allocate 54 bytes, then free up the 36, leaving a 76-byte hole.
5. When you need more, allocate 81 bytes, then free up the 54, leaving a 130-byte hole.
6. When you need more, use 122 bytes (rounding up) from the 130-byte hole.