 # DS&A

Data Structures and Algorithms ## Memory and Pointers

Feb 052018

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.

#### Python-specific detail

Almost nothing in Python has a simple memory representation; the memory representations described in this post are simplified, and more similar to how lower-level languages like C++, C or Java work.

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.

(This interactive feature requires Javascript to be enabled in your browser.)

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.

(This interactive feature requires Javascript to be enabled in your browser.)

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:

(This interactive feature requires Javascript to be enabled in your browser.)

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 interactive feature requires Javascript to be enabled in your browser.)

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``````

#### Python-specific detail

Python internally represents objects as dictionaries rather than sequences of fields. This means you can add fields to objects dynamically, and objects of the same class can have different fields; it is possible to create a `Vector` object `a = Vector(1,2)` and then add a field `a.z = 3`. This is generally a bad idea, because it violates the principle that code inside the class should be solely responsible for how its objects work; but for better or worse, this is how objects in Python behave.

You can make Python store fields in a sequence instead of a dictionary, using the `__slots__` feature:

``````class Vector:
__slots__ = ['x', 'y']

def __init__(self, x, y):
self.x, self.y = x, y``````

This has some performance advantages, but is often unnecessary.

#### 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.

## New comment

Your comment will not appear until a moderator approves it.

Atom

hosted on werp.site