Memory Management

Why memory management matters

Every value a program works with — a number, a string, a list of a million orders — occupies memory while the program runs. Memory is finite and shared with every other program on the machine, so a program must obtain memory when it needs it and give it back when it is done. Memory management is how that happens.

Getting it wrong has real consequences. A program that never gives memory back grows until the system slows down or kills it. A program that uses memory after giving it back can crash, silently corrupt its data, or open a security hole: Microsoft and Google's Chromium team have both reported that roughly 70 percent of their serious security bugs were memory-safety errors. That is why most modern languages take the job away from the programmer, and why it still pays to understand what they do for you.

The memory of a running program

When the operating system starts a program, it gives the new process its own address space, divided into regions with different purposes:

• Code (also called text): the program's machine instructions, usually read-only.
• Static data: global variables and constants that exist for the whole run.
• Stack: the local variables of the functions that are running right now.
• Heap: memory requested while the program runs, for data whose size or lifetime is not fixed in advance.

The code and static data have a fixed size, known when the program is built. The stack and the heap change size while the program runs, which is why they are placed at opposite ends of the free space. Modern systems add more detail — shared libraries, memory maps, one stack per thread — but these four regions are the model every language builds on.

The stack

Each time a function is called, a stack frame is pushed onto the call stack: a block of memory holding that call's parameters, its local variables and the address to return to. When the function returns, its frame is popped and the memory is immediately available for the next call. The stack works exactly like the stack data structure: last in, first out.

This design has three consequences:

• Automatic lifetime. Local variables exist only while their function runs. Nobody has to free them.
• Speed. Allocating a frame means moving one pointer (the stack pointer) by a fixed amount, which costs almost nothing.
• Limited size. The stack is small — typically 8 MB per thread on Linux and 1 MB on Windows. Very deep recursion or a huge local array exhausts it: a stack overflow.

The C example below contrasts a local variable, which lives in the stack frame and starts fresh on every call, with a static one, which lives in the static data region for the whole run:

#include <stdio.h>

void visit(void)
{
    int local = 0;          /* in the stack frame: a new one on every call */
    static int total = 0;   /* in static data: one copy for the whole run */

    local++;
    total++;
    printf("local = %d, total = %d\n", local, total);
}

int main(void)
{
    visit();
    visit();
    visit();
    return 0;
}

local = 1, total = 1
local = 1, total = 2
local = 1, total = 3

int *make_counter(void)
{
    int counter = 0;
    return &counter;   /* BUG: counter no longer exists after the return */
}

The heap

The heap is the region for memory that a program requests explicitly while it runs, and that lives until it is explicitly or automatically released — independent of which function is running. You need it when:

• data must outlive the function that created it, such as a list built inside a function and returned to the caller;
• the size is only known at run time, such as a file's contents or a list that grows as users sign up;
• the data is too large for the stack.

The price is speed and bookkeeping. A heap allocator must search for a free block of the right size, track which blocks are in use, and cope with fragmentation: free memory split into many small gaps. And someone has to decide when a block is no longer needed — the question the rest of this page is about.

Values, references and pointers

A variable can hold a value directly, or it can hold a reference: something that identifies an object stored elsewhere, usually on the heap. Copying a value gives you an independent copy; copying a reference gives you a second way to reach the same object.

In Python, every name is a reference. The objects themselves live on the heap; a function's frame holds only the names that refer to them. Assignment never copies an object — it makes a name refer to it. That explains the classic surprise below:

def add_bonus(score, bonus):
    score = score + bonus       # makes the local name refer to a new int


def add_item(cart, item):
    cart.append(item)           # changes the one list both names refer to


score = 70
add_bonus(score, 10)
print(score)

cart = ["bread"]
add_item(cart, "milk")
print(cart)

same_cart = cart                # a second reference, not a copy
print(same_cart is cart)

70
['bread', 'milk']
True

The operator is tests whether two references point to the same object. The built-in id() returns a number that identifies an object during its lifetime (in CPython, its memory address); it is useful for debugging but differs on every run, so never rely on its value. See Lists and Tuples for how to make real copies.

Other languages mix both models. In Java and C#, numbers and booleans are stored as values, while objects are always accessed through references (C# also has structs, which are values). In C, everything is a value — including addresses, which brings us to pointers.

Pointers in C

A pointer is a variable whose value is a memory address. It is a reference you can see and manipulate directly. C has two operators for it:

• &x (address-of) gives the address of x;
• *p (dereference) gives the value stored at the address in p — and can also change it.

#include <stdio.h>

void add_bonus(int *score, int bonus)
{
    *score += bonus;           /* change the caller's variable through the pointer */
}

int main(void)
{
    int score = 70;
    int *p = &score;            /* p holds the address of score */

    printf("score = %d\n", score);
    printf("*p = %d\n", *p);   /* dereference: the value at that address */

    *p = 75;                   /* writing through p changes score */
    printf("score = %d\n", score);

    add_bonus(&score, 10);
    printf("score = %d\n", score);
    return 0;
}

score = 70
*p = 70
score = 75
score = 85

Compare this with the Python example: there, add_bonus could not change the caller's score. In C, passing a pointer lets a function change a variable that lives in another function's stack frame. Pointers are powerful and fast, but the compiler cannot check that the address still holds what you think it does — that is your job.

Manual memory management in C

C gives you the heap directly. malloc(n) ("memory allocate") reserves n bytes and returns a pointer to them, or NULL if there is no memory left. free(p) gives the block back. Between those two calls, the memory is yours; after free, it is not.

#include <stdio.h>
#include <stdlib.h>

/* Returns a new array on the heap. The caller must free it. */
int *make_squares(int count)
{
    int *squares = malloc(count * sizeof *squares);
    if (squares == NULL) {
        return NULL;                 /* allocation can fail */
    }
    for (int i = 0; i < count; i++) {
        squares[i] = i * i;
    }
    return squares;                  /* still valid after this function returns */
}

int main(void)
{
    int count = 5;
    int *squares = make_squares(count);
    if (squares == NULL) {
        fprintf(stderr, "Out of memory\n");
        return 1;
    }

    for (int i = 0; i < count; i++) {
        printf("%d squared = %d\n", i, squares[i]);
    }

    free(squares);                   /* give the memory back ... */
    squares = NULL;                  /* ... and forget its address */
    return 0;
}

0 squared = 0
1 squared = 1
2 squared = 4
3 squared = 9
4 squared = 16

Notice the division of work: make_squares allocates, but main frees. Every heap block needs an owner — the part of the program responsible for freeing it exactly once — and in C that responsibility exists only in comments and in the programmer's head. C++ improves on this with destructors and smart pointers, which free memory automatically when the owning object goes out of scope.

Common memory bugs

Three mistakes account for most trouble with manual memory management. The snippets below are deliberately wrong.

A memory leak is memory that a program no longer needs but never releases. Here each pass through the loop allocates a buffer and loses its address, so the memory can never be freed until the process ends. In a long-running server, leaks add up until the machine runs out of memory.

for (int i = 0; i < 1000; i++) {
    char *line = malloc(256);
    /* ... use line ... */
}                              /* BUG: 256 000 bytes allocated, none freed */

A use after free reads or writes memory after it was released. The pointer still holds the old address — it has become a dangling pointer — but the allocator may already have handed that memory to something else. The result is undefined behavior: the program may seem to work, print garbage, crash, or be exploited by an attacker.

int *price = malloc(sizeof *price);
*price = 42;
free(price);
printf("%d\n", *price);        /* BUG: use after free */

A double free releases the same block twice. It corrupts the allocator's own bookkeeping and is undefined behavior as well. Setting a pointer to NULL right after freeing it prevents a double free through that pointer, because free(NULL) does nothing; other copies of the address still dangle.

free(price);
free(price);                   /* BUG: double free */

Automatic memory management

Garbage collection is automatic memory management: the language runtime finds heap objects that the program can no longer reach and frees them. You allocate by creating objects; you never call free. This rules out use after free and double free entirely, at the cost of some extra memory and processor time. Nearly every modern language works this way, using one or both of the techniques below.

Reference counting

With reference counting, every object keeps a count of how many references point to it. Assigning it to a name, putting it in a list or passing it to a function increases the count; when a reference disappears, the count goes down. When it reaches zero, nothing can reach the object any more, and it is freed immediately. CPython uses reference counting as its main mechanism, as do Swift and the smart pointer std::shared_ptr in C++.

class Buffer:
    def __init__(self, name):
        self.name = name
        print("allocated", name)

    def __del__(self):                 # called when the object is freed
        print("freed", self.name)


a = Buffer("A")
b = a            # two references to the same object
del a            # one reference left: nothing is freed
print("after del a")
del b            # count drops to zero: freed right away
print("after del b")

allocated A
after del a
freed A
after del b

You can ask CPython for an object's count with sys.getrefcount(obj), but the number is always higher than you expect — the call itself adds a temporary reference, and the interpreter holds references of its own — so it is rarely useful outside debugging. The timing shown above is specific to CPython; other Python implementations free objects later.

Reference counting has one blind spot: cycles. If two objects refer to each other, each keeps the other's count above zero even when the rest of the program can no longer reach either of them.

Tracing garbage collection

A tracing garbage collector does not count; it searches. The classic algorithm is mark and sweep:

1. Mark: start from the roots — global variables and the references in every stack frame — and follow every reference, marking each object reached.
2. Sweep: go through the heap and free every object that was not marked.

Because it asks "can the program still reach this?" rather than "does anything point to this?", a tracing collector frees cycles without trouble. Java, C#, Go and JavaScript engines use tracing collectors; Java, C# and JavaScript use generational ones: most objects die young, so new objects are checked often and old ones rarely. The trade-off is that memory is freed later than with reference counting, and the collector needs processor time of its own — sometimes as short pauses.

CPython combines both: reference counting frees most objects immediately, and a generational cycle detector (the gc module) periodically finds and frees cycles.

import gc

gc.disable()                 # only for this demonstration: collect by hand below


class Node:
    def __init__(self, name):
        self.name = name
        self.partner = None

    def __del__(self):
        print("freed", self.name)


x = Node("x")
y = Node("y")
x.partner = y                # x and y now refer to each other
y.partner = x

del x, y
print("names deleted; the cycle keeps both alive")
gc.collect()
print("after gc.collect()")

names deleted; the cycle keeps both alive
freed x
freed y
after gc.collect()

A third way: ownership in Rust

Rust avoids both manual free calls and a garbage collector. Every value has exactly one owner, a variable; when the owner goes out of scope, the value is freed automatically. Other code can borrow a value through a reference, and the compiler's borrow checker proves, before the program ever runs, that no reference outlives the value it points to and that no value is changed while someone else is reading it. The result is the speed and predictability of manual management without use after free or double free — paid for with stricter rules at compile time.

Memory leaks with a garbage collector

A garbage collector frees only what the program can no longer reach. If your code keeps a reference to data it will never use again, the collector must assume it is still needed, and memory grows just as it does with a forgotten free. Typical causes:

• Unbounded caches — a dictionary that remembers every result and never forgets any;
• Global lists that collect records, log lines or sessions and are never emptied;
• Event handlers that are registered but never removed, keeping their objects alive (common in JavaScript user interfaces).

from functools import lru_cache

_cache = {}


def thumbnail(photo_id):
    if photo_id not in _cache:                   # remembers every photo forever
        _cache[photo_id] = f"thumbnail of photo {photo_id}"
    return _cache[photo_id]


for photo_id in range(10_000):
    thumbnail(photo_id)
print(len(_cache))


@lru_cache(maxsize=100)                          # keeps only the 100 most recent
def bounded_thumbnail(photo_id):
    return f"thumbnail of photo {photo_id}"


for photo_id in range(10_000):
    bounded_thumbnail(photo_id)
print(bounded_thumbnail.cache_info().currsize)

10000
100

The first cache grows with every new photo for as long as the program runs; the second evicts the least recently used entry once it holds 100. When memory use of a long-running program only ever goes up, look for collections that grow without a limit.