This is based on a neat little post that I saw on Simon Frankau‘s blog that I thought I’d provide a few more details on, as well as bringing it to a wider audience. Some higher-level data structures in object-oriented programming languages have dynamic memory allocation. This is used to create objects (usually things that behave like lists) that can grow and shrink as the program executes. When initializing a regular array in C or Java, you have to specify the size of the array on creation, for example with
int myArray[] = new int[10];
in Java (actually Java has a wide variety of syntaxes for array creation, which I won’t go into). Importantly, your array has the size you initially specify for the rest of time. When it’s created, you are allocated a sequential block of memory that’s exactly big enough to hold the elements of the array (it’s sequential so that looping through the elements of the array is fast). If you find that you need more storage space at any point in time, you’re out of luck. Fortunately most high-level languages like provide a data structure which is able to grow, for example C++’s std::vector or Java’s ArrayList and Vector. When these are created they are allocated a block of memory. If it ever turns out that you need more space, then they allocate a new block of memory to allow you to extend the array: for example, if you have an array of size 10 and then try to allocate something to the 11th position:
ArrayList myArray = new ArrayList(10);
myArray.set(10, "foo");
But how much new memory should they allocate? A little bit of investigation reveals that this varies across languages and across data structures. Commonly, a multiplicative growth factor is applied. For example, with a growth factor of two, you would double the size of the allocated block each time. To ensure that the array elements remain sequential in memory (so that it’s still fast) you probably want to allocate a new block and copy across the elements in the old block – so your strategy works like this:
- Allocate a new block of memory that is bigger than the current block by some factor
- Copy the old data into the new memory block
- Start writing the new elements here
As Simon points out, a natural strategy is to double the size of the array each time, but this is probably a bad choice. This is because at each stage you assign a new memory block of size 2^n, but the total size of the memory locations used so far (assuming your initial array size is rescaled to be 1) is 1 + 2 + \cdots + 2^{n-1} = 2^n - 1, so you can’t reuse any of the old memory. Since you’re now only dealing with the newly allocated memory, all this old memory goes to waste.
What would be a better factor? Let’s say we used x. Then initially we’d have a block of (rescaled) length 1. We allocate a new block of length x. When we extend again we allocate a block of length x^2. We need to keep the old block of length x around to copy over the old data, and we can’t fit our block of size x^2 in the space of size 1, so we allocate this as a new block too. But when we allocate the next block of size x^3, we might be able to fit it in the two old blocks, of size 1 and x. This works if
1 + x = x^3
which you can solve numerically and find that there is a solution x~1.32. What if you were willing to wait for
one more allocation before reusing the memory? Then we’d try and fit a block of size x^4 into a block of size
1 + x + x^2, so we solve
1 + x + x^2 = x^4
for a solution of x~1.47. How about if we were willing to wait for n allocations? Then we’d be trying to solve
1 + x + ... + x^{n-2} = x^n
which is more tricky. However, if we notice that the left-hand side is a geometric series, then we can sum it up and multiply through to get
x^{n-1} - 1 = x^{n+1} - x^n
This still looks a but hopeless, but when n is large the three terms involving x will dominate the ‘-1′ and we can neglect it. This corresponds to an allocation strategy where we know that we will be able to reuse a block of memory at some point in the future. We get:
x^{n-1} = x^{n+1} - x^n
This is looking more hopeful. Now we can divide by x^{n-1} and rearrange, giving a familiar-looking equation:
x^2 - x - 1 = 0
Why does this look so familiar? It’s positive solution is exactly the well-known golden ratio!
Now, you wouldn’t want to use exactly this value to do your memory reallocation, because you’d end up waiting forever to be able to reuse your old memory. But Simon suggests that a strategy of using a number a bit less than this, say 1.5, might work out.
And guess what? Java’s ArrayList uses exactly this factor to allocate new memory. I don’t know if it reuses its previously allocated memory in the style described here – that’s something to find out for the future.