You are currently browsing the tag archive for the ‘java’ tag.

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\approx 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 \approx 1.47. How about if we were willing to wait for n allocations? Then we’d be trying to solve

1 + x + \cdots + 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 x = \tfrac{1}{2}(1 + \sqrt{5}) \approx 1.618\dots, 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.

I was linked to a collection of Edsger Dijkstra’s writings today, and spent an interested half hour reading some of them. Djikstra was known for composing his manuscripts in longhand, using a fountain pen. He would then make a dozen or so photocopies, and mail them out to people he knew to be interested in his work. They would then be further disseminated by those people, and so on, until his work had reached a wide audience. Each article was coded with his initials EWD, followed by a three or four digit number — they thus became known as EWDs in the computer science world.

The most interesting article I read today was EWD831, whose full title is Why numbering should start as zero. Djikstra argues persuasively that counting should start from zero, and thus that all arrays should be indexed beginning from zero. This runs counter to the natural intuition (and to what we are taught at school) that counting begins at 1.

In brief, Dijkstra’s argument runs like this. There are four possibilities for notating the range of numbers 1, …, 10 without using ellipsis notation, which can be ambiguous:

  1. 1 ≤ i < 11
  2. 0 < i ≤ 10
  3. 0 < i < 11
  4. 1 ≤ i ≤ 10

There are several desirable properties that we might want our system of notation to have. For example:

  • (a) the difference between the bounds is equal to the number of terms in the sequence
  • (b) two ranges are adjacent if the upper bound of one is equal to the lower bound of the other.

Both 1 and 2 satisfy these properties, but 3 and 4 don’t. If we want to use our notation to specify a range of natural numbers, then it seems sensible to ask for the following two properties:

  • (c) the lower bound is a natural number
  • (d) the upper bound is a natural number, even when defining the empty sequence

Property (c) is only satisfied by 1 and 4 and property (d) is only satisfied by 1 and 3 So we see that it is only notation 1 that satisfied all of the properties we desire.

Now we move on to the question of whether we should start indexing at 0 or at 1. This is simply an issue of aesthetics. If we want to describe the range of an array with N entries, then by starting at 0 we would write the range as 0 ≤ i < N, whereas if we start indexing at 1 then it is written as 1 ≤ i < N+1, which is significantly more ugly. So we see that we should start indexing at 0. Note that programming languages such as C, Java and Python all follow this convention, as do most widely adopted languages. The only commonly used languages I can think of that don’t use it are Fortran and R.