The Array: What It Really Is in Memory

Get access to whole semester resourcesSemester Pass

Chapter Eleven

Syllabus topic Computer Science Practical 3, Module 2, "Compare static (array) vs dynamic (linked) approaches"

Pages 32 to 34 of 411

In one line

An array is a run of equal-sized cells side by side in memory, which is why the machine can compute the address of the nth item instead of looking for it.

The arrangement

Ask for an array of ten integers and the machine gives you one unbroken block of memory, divided into ten equal cells. Nothing separates them; nothing links them. They are simply next to each other.

That one property, equal cells, side by side, is the whole of the array, and everything it is good and bad at follows from it.

Why indexing is instant

Suppose the block starts at address 1000 and each cell is 4 bytes.

address of item 0 = 1000 + (0 x 4) = 1000

address of item 1 = 1000 + (1 x 4) = 1004

address of item 2 = 1000 + (2 x 4) = 1008

address of item i = 1000 + (i x 4)

So, in general:

address of item i = base + (i x size of one cell)

That is one multiplication and one addition. It does not depend on i, and it does not depend on how many items the array holds. Reaching item 9,999 of ten thousand costs exactly what reaching item 0 costs.

This is what O(1) access means, and it is the array's one great gift. It is also why array indices start at 0 in most languages: item 0 is at base + 0, so the arithmetic has no correction in it.

Seen in a real run:

BASE = 1000
CELL = 4

print("index | address")
for i in (0, 1, 2, 9, 9999):
    print("%5d | %d" % (i, BASE + i * CELL))

print()
print("the cost of the arithmetic does not depend on i:")
print("  item     0 needs 1 multiply and 1 add")
print("  item 9,999 needs 1 multiply and 1 add")

index | address
    0 | 1000
    1 | 1004
    2 | 1008
    9 | 1036
 9999 | 40996

the cost of the arithmetic does not depend on i:
  item     0 needs 1 multiply and 1 add
  item 9,999 needs 1 multiply and 1 add

The three consequences

Everything about arrays follows from equal cells side by side.

1. Access is constant. Shown above.

2. The cells must be the same size. Otherwise the multiplication is meaningless. This is why a C array holds one type only. Python's list appears to hold anything, because what it really stores is a row of equal-sized addresses, each pointing at the actual value elsewhere. The row is still uniform; the values are not in it.

3. The block must be contiguous, so the size is fixed at creation. You cannot extend a block if something else is sitting immediately after it in memory. That single fact is the whole of the next chapter.

The Array: What It Really Is in Memory

Row major order, and why a 2D array is really 1D

A two dimensional array is stored as one row of cells too, one row of the table after another. This is row major order, and it is examinable because the address formula follows from it.

For an array with C columns, starting at base, with cells of size w:

address of A[i][j] = base + ((i x C) + j) x w

BASE, COLS, CELL = 2000, 5, 4

print("A is 3 rows x 5 columns, base 2000, 4 bytes a cell")
print()
print("element | offset in cells | address")
for i, j in [(0, 0), (0, 4), (1, 0), (2, 3)]:
    cells = i * COLS + j
    print("A[%d][%d]  | %14d | %d" % (i, j, cells, BASE + cells * CELL))

A is 3 rows x 5 columns, base 2000, 4 bytes a cell

element | offset in cells | address
A[0][0]  |              0 | 2000
A[0][4]  |              4 | 2016
A[1][0]  |              5 | 2020
A[2][3]  |             13 | 2052

Notice A[0][4] and A[1][0] are next to each other in memory, four bytes apart. The row boundary exists only in your head; the machine sees one long run of cells.

Some languages, notably Fortran, store column major instead, down the columns first. The formula then becomes base + ((j x R) + i) x w. An examination question naming a language is asking which of the two you use.

What an array promises, as an ADT

Operation	Cost
`get(i)`	constant
`set(i, value)`	constant
`length()`	constant
insert in the middle	linear
delete from the middle	linear
grow	not possible; a new array must be made

The top three are why arrays are everywhere. The bottom three are why this paper has ten more structures in it.

Quick revision

An array is a contiguous block of equal-sized cells.
Address of item i is base + (i x cell size): one multiply, one add, independent of i and of the

array's length. That is O(1) access.

Indices start at 0 so the arithmetic needs no correction.
Cells must be equal in size, so a C array holds one type; a Python list stores equal-sized addresses

pointing elsewhere.

The block is contiguous, so the size is fixed when it is created.
2D arrays are stored row major: base + ((i x C) + j) x w. Fortran uses column major.
A row boundary is not in memory; the cells of one row run straight into the next.

The Array: What It Really Is in Memory

Test yourself

1. Write the address formula for the ith item of a one dimensional array and say why it is O(1). base + (i x w), where w is the cell size. It is one multiplication and one addition whatever i is and however long the array is, so the cost does not grow with the data.

2. Why must all cells be the same size? Because the address is computed by multiplying the index by the cell size. Unequal cells make that multiplication meaningless.

3. A Python list can hold an integer and a string at once. How is that consistent with equal cells? The list stores equal-sized addresses, not the values. The values live elsewhere; the row itself is uniform.

4. Give the row major address of A[2][3] where A has 5 columns, base 2000 and 4 byte cells. Offset in cells is (2 x 5) + 3 = 13, so the address is 2000 + 13 x 4 = 2052.

5. Why can an array not grow? Because its cells must be contiguous, and the memory immediately after the block may already be in use. Growing means allocating a new block and copying.

6. Which single property of the array causes both its greatest strength and its greatest weakness? Contiguity. It makes the address computable, which gives O(1) access, and it fixes the size at creation, which makes growth and middle insertion expensive.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue