Arrays in Memory

When we last left our intrepid heroes, they were writing loops to add data to an array. But they still had one question:

Where does the data go?

Let’s take a closer look at how data is stored in an array.

Blocks of Memory

Let’s simplify our earlier pseudo-code a bit with a new example:

numbers = array(10)
index = 1

loop
     # Loop Body
     numbers[index] = input("Enter a new number: ")
     index = index +1
until index > 10

The first line sets aside some space for an array which can hold up to ten different numbers. In memory, this memory looks like:

Loc 1	Loc 2	Loc 3	Loc 4	Loc 5	Loc 6	Loc 7	Loc 8	Loc 9	Loc 10
????	????	????	????	????	????	????	????	????	????

Each of the ten memory locations will store a single number. The first memory location corresponds to numbers[1], the second to numbers[2] and so on.

This should look somewhat familiar, if you recall the article where strings were introduced:

Loc 1	Loc 2	Loc 3	Loc 4	Loc 5	Loc 6
0x68	0x65	0x6c	0x6c	0x6f	????

Recall that a string consists of a sequence of individual characters, treated as a single unit. You can think of the sequence of individual characters as an array of characters. In fact, many programming languages don’t even have a specific data type for strings, forcing coders to create arrays of characters explicitly.

What does this have to do with where data is stored in an array? Let’s keep going…

Adding Up

So with this in mind, let’s take a look at the loop from the example in more detail:

• The value of index starts as 1, so the first number input by the user will be stored in numbers[1].
• After that, index is incremented, and the loop continues.
• The loop ends when index > 10.

We know that each variable points to a specific memory location when it is created. So numbers points to some address in memory, which is the location of a block of memory big enough to hold every element in that array. This implies that every element of numbers has an individual memory location assigned to it as well.

So in the middle of the loop when index = 5, the computer knows the memory location of numbers[5]. It has to, in order to store a value there. The problem is, while the computer set aside a block of memory big enough for the entire numbers array, it only stored one memory location for it.

So the question is how does the computer know where numbers[5] should be stored?

The answer is it does some basic math.

First, let’s introduce one new definition. We define the term &numbers to be the memory address of the numbers array.

Next, recall that each element of an array takes up the same amount of memory space. The numbers array stores integers, so this is four bytes.

Assuming &numbers is 0x4000, this looks like:

Generalizing a bit, we can state:

• the first element of the array numbers[1] is stored at &numbers
• the second element numbers[2] is stored at &numbers + 4
• the third element numbers[3] is stored at &numbers + 8

And so on.

Looking closely, there is a pattern emerging here which lends itself to some basic math. The address of any element of numbers is based on the value of index and the size of the of the data being stored. In fact, the address of any element can be found with the following formula:

&numbers + (index - 1) * size(data)

To find the address of numbers[index], you subtract 1 from the value of index, multiply that by the size of the data being stored, and add that to the address of the numbers array.

Let’s see that at work by calculating the address of numbers[6]:

• Subtracting one from index gives us 5.
• Multiplying that by the size of the data (4 bytes) gives us 20, which is 0x14 in hexadecimal.
• Adding that to &numbers gives us 0x4014.

In fact, these steps are exactly what the computer does each time you reference an element in an array.

Zero My Hero

Everything you do on a computer takes some amount of time. Even basic math like adding and subtracting integers takes some small amount of time. It may only be a fractions of a microsecond, but it’s still a positive amount of time.

When working with arrays, you also often find yourself working with loops. The code within the loop takes some amount of time, which repeats as long as the loop repeats. Any small increase or decrease in the amount of time spent doing work in the loop can magnify into a human measurable amounts of time.

Think of a computer game, where a microsecond spent or not spent in a loop might impact the frame rate of a game. Every calculation done decreases the number of loops you can do each second, which may impact the visual aspects of the game. If you can shave a microsecond off a loop which spins half a million times, you can save half a second over the entire loop. While that’s an exaggerated example, it still makes sense to do as few calculations in each loop as possible.

One way programming languages do this is by simplifying the calculations needed to locate each array element. But how? Well, what if we didn’t need to subtract one every time?

This can work, but only if we think about our array indices differently. Rather than counting starting with one, we can start counting at zero:

• The first element of the array is now numbers[0].
• The second element is numbers[1].
• The 27th element is numbers[26].

And so on.

So how does this simplify things? Let’s look at the new address calculation:

&numbers + index * size(data)

Removing that single subtraction from within a loop could save dozens of microseconds during processing. Over the life of the program, this could be significant. In fact, languages like C, C++, and Java use this technique, called zero indexing or zero-based indexing, to both simplify and speed up array access.

Homogeniety is Boring

An array is a data structure which holds many different pieces of data, but all that data is the same data type. What if you want to store many different types of data in a single place? Next time, we’ll examine a way to do just that in a single data structure.