DS&A

Memory and Pointers

Computer programs use variables and data structures to store data in memory.(1) A data structure is a scheme for representing values of some type in memory; before we can understand, analyse and design data structures, we need to understand memory.

In this post we’ll develop a simplified model of how memory works. In our model, there are some number of memory locations, and each memory location has a certain number of bits(2) which can be used to store a value at that location. Each location stores one value at a time, because the bits can only be in one state at once. Each location also has an address — a number which says “where” in memory it is.

We’re interested in data structures (which concretely represent types) and algorithms (which implement operations). Data structures are composed of simpler types, and algorithms are composed of simpler operations; ultimately, everything boils down to primitive data types and primitive operations.

There are only two primitive memory operations: read and write (also called load and store). Only very low-level languages like C and Assembly let the programmer use these operations directly; normally, the programmer uses variables and objects, and the computer handles the memory accesses.

When you declare a variable, the computer chooses a memory address for it. As a programmer, you refer to the variable by its name, but the computer keeps track of its memory address too. When you use the value of a variable, the computer reads it from that address; when you change its value, the computer writes the new value to that address.(3)

The idea for objects is similar; when you create an object, the computer chooses a memory address for it. Objects generally have more than one field; the simplest way to represent the object in memory is to store its fields as a sequence, in adjacent memory locations. This means the computer also needs to keep track of what fields exist and which order they’re stored in. For example, if a Vector class has fields for x and y coordinates, then Vector objects can be stored using two adjacent memory locations, one for each field; the memory address of the x field is the same as for the object itself, and the y field is at the next address.(4)

Consider the following Python class for a 2D vector, with a method to rotate it:

class Vector:
    def __init__(self, x, y):
        self.x, self.y = x, y
    
    def rotate(self):
        # Rotate by 90 degrees.
        self.x, self.y = self.y, -self.x

Consider the following Java class for a 2D vector, with a method to rotate it:

class Vector {
    int x, y;
    
    Vector(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    void rotate() {
        // Rotate by 90 degrees.
        int tmp = -x;
        x = y;
        y = tmp;
    }
}

See what happens in memory when you create a Vector object and rotate it:

Actually, this is not quite correct. When we call rotate, the computer needs to know which Vector object to rotate. The rotate method changes the object’s state, which requires writing to the memory locations where the object is stored; so object’s memory address is required as an input to this procedure. (In most languages this is handled implicitly, but in Python, methods like rotate explicitly take self as a parameter.) This means the memory address is itself a value which can be operated on or stored in memory.

Consider also what happens when we declare a variable for our Vector object. The variable doesn’t actually hold the object itself; the variable and the object are different things, with different memory addresses. The value stored in the variable is the address of the object; instead of saying the variable holds the object, we say it holds a pointer or a reference to the object.(5)

This means we can have more than one reference to the same object. Whichever reference we use to access the object, any changes we make are to the object, not the variables which refer to it; it is important to know whether you are changing the value of a variable, or the state of an object it refers to.

Try the following in Python:

>>> class Vector:
...     def __init__(self, x, y):
...         self.x, self.y = x, y
...
>>> a = Vector(1,2)
>>> b = a
>>> b.x
1
>>> a.x = 5
>>> b.x
5
>>> a.y
2
>>> b.y = 6
>>> a.y
6

Try the following in Java, using the Vector class:

>>> Vector a = new Vector(1,2);
>>> Vector b = a;
>>> b.x
1
>>> a.x = 5;
>>> b.x
5
>>> a.y
2
>>> b.y = 6;
>>> a.y
6

class Vector:
    __slots__ = ['x', 'y']
    
    def __init__(self, x, y):
        self.x, self.y = x, y

Footnotes

1. We usually just say “memory”, but there are many kinds of it: CPUs have registers and caches which are faster than RAM, and hard disks can be used as virtual memory. It’s up to the CPU, compiler and operating system to use the right kinds of memory for the right purposes, so the distinctions are usually irrelevant to programmers, though some awareness is required to write very efficient programs.
2. This number is called the word size. It’s 64 on most modern computers, but 32 is still common; older computers had 16 or 8 bits per word.
3. This is a simplification; some types of data may require more than one word. For example, if each memory location has 32 bits, then a double-precision floating point number would occupy two memory locations.
   Alternatively, some types (e.g. characters) might only take up part of a memory location, so one location could store multiple values.
4. This is another simplification; depending on the programming language, real objects usually contain more than just their fields’ values. They might also have type information and/or a method table reference.
5. A reference is anything that lets us locate other data, and this is normally achieved by following a pointer to a memory address.

• Tags: 
• memory, types, binary, pointers, objects