Managing Heap Memory

Managing heap memory is important in any programming language that lets the programmer allocate/de-allocate heap memory.

Most modern application-level languages manage the heap using garbage collection. There are many variations on the basic garbage collection algorithms, and here we touch upon a few popular approaches.

First, though, we will look at a couple of approaches that are not commonly used today: tombstones, and locks and keys. They are not common because while they do protect from accessing memory that has been deleted, they still require the programmer to manually delete memory (i.e. explicitly called dispose/delete/free etc). However, they are relatively easy to understand, and are interesting techniques that might have applications in other situations.

Keep this basic example in mind in the notes that follow:

p = new(String)  // p points to a new (empty) string on the heap

other = p        // other and p both point to the same heap object

// ...

deallocate(p)    // dispose of the string p points to
                 // How does other know the object it is
                 // pointing to has been de-allocated?

The techniques below address the problem of what to do when a chunk of heap memory is no longer needed.

Tombstones

Tombstones solve the memory management problem by assigning to each heap object an intermediary object, called a tombstone, that pointers point to instead of the object itself:

p --> |         |
q --> |tombstone| --> |object|
r --> |         |

The tombstone is a special object that contains the address of the true object.

Now suppose the object is de-allocated, e.g. we call something like “deallocate(p)”. The diagram looks like this:

p --> |         |
q --> |tombstone| --> nil   |object|
r --> |         |

The tombstone points to nil, and so all the other pointers are effectively nil. At run-time if you try to access *r, say, then we know that is illegal and can raise an appropriate error.

Tombstones are not commonly used for a couple of reasons. First, the tombstones take some extra memory for every object that is created. Second, accessing the actual object is a little slower because it must go through the tombstone, which requires an extra dereferencing call.

Locks and Keys

In the locks and keys technique, each heap object is given its own unique numeric key that is stored with the object. A pointer is now a (key, address) pair (instead of just an address).

When an object is accessed through a pointer, the key of the pointer is compared to the key of the object, and the access is only permitted if the keys match.

When the object is de-allocated, its key is set to -1 (or some other “no longer exists” value). This way a pointer for a de-allocated object cannot be accessed:

                     key: 7
p: key=7, -------> |        |
                   | object |
q: key=7, -------> |        |

Now suppose the object is de-allocated. We set its key to -1:

                     key: -1
p: key=7, -------> |        |
                   | object |
q: key=7, -------> |        |

Now if you try to access the object, e.g. *q, a run-time error can be raised because the keys no longer match.

As with tombstones, the locks and keys approach has performance and memory overheads that make it uncommon in practice.

Garbage Collection

The most common technique for managing heap memory in modern programming languages is garbage collection. A garbage collector is a program that occasionally runs during the running of a program. The garbage collector automatically de-allocate any memory no longer in use by the program.

A major advantage of garbage collection over manual memory management, and also over the tombstone and locks and keys approaches described above, is that there is no need for the programmer to explicitly de-allocate memory. Instead, the garbage collector determines on its own when tp dispose of objects.

Garbage collection is a big and relatively complex topic, and so we will only mention a couple of the most basic techniques.

We will assume that heap memory is always allocated in fixed-size cells, and that free memory is structured as a linked list of empty cells. Allocating memory from this free list is easy, i.e. you take as many cells as needed.

De-allocation is the tricky part. We will look at two basic garbage collection de-allocation methods: reference counting, and mark and sweep.

Reference Counting

The idea of reference counting garbage collection is to store with each memory cell a counter that is the total number of pointers currently pointing to it. When this counter becomes 0, the object can be safely deleted.

Implementing reference counting requires that every time a pointer is made to refer to an object, that object’s reference count is incremented, and every time a pointer is made to no longer point to an object, it’s reference count is decremented.

It is possible that a single de-allocation could trigger a chain of de- allocations, which might result in a pause in the program. One way to avoid this is to put all de-allocated objects onto a special list of de-allocated objects, and then actually de-allocate them incrementally over time.

In general, though, reference counted garbage collection is interleaved with a program’s actions, and so tends to avoid the pauses associated with other kinds of garbage collection.

A basic problem with reference counting is that it can’t handle cyclic structures, e.g.:

| a: points to b |
| ref count: 1   |

| b: points to a |
| ref count: 1   |

These two objects can be safely de-allocated, because the only pointers in play are internal to the objects. However, their reference counts are not 0, and so a pure reference-counted garbage collector cannot detect that these objects can be deleted.

Referencing counting is used in some programming languages, such as Python. C++ also provides it via its shared_ptr class.

Mark and Sweep

In the basic mark and sweep garbage collection algorithm, garbage collection “stops the world” and does a two-phase scan of memory. We assume that every memory object has an “in use” bit that is always set to 0 except during garbage collection.

The first memory scan done by mark and sweep is the “mark” phase where the “in use” bit of each memory object is set to 1. This can be done following each root pointer through the tree of all objects being pointed to.

After the marking phases is finished, all of memory is then scanned to check which objects have their “in use” bit set, and which don’t. Those objects whose “in use” bits are 0 can then be safely disposed of.

A major problem with this approach is that it can, periodically, cause the program to come to a complete halt while garbage checking is done. This might be unacceptable for interactive applications, e.g. real-time systems.

Many variations on basic mark and sweep algorithms have been proposed. For instance, generational garbage collectors use heuristics based on the idea that the most recently created objects are likely to be deleted sooner than older objects.

In practice, good garbage collectors are often hybrids of different approaches.

Smart Pointers in C++

C++ is not a garbage-collected language, although it does provide some useful techniques for automaticaly managing memory. Here, we will look at one of C++’s standard smart pointer classes: unique_pointer<T>.

// smart.cpp

#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <stdexcept>

using namespace std;

// The Person_leak class has a memory leak. The problem is that a Person_leak
// object creates a new string on the heap when it's constructed, but does not
// delete that object when it, the Person_leak object itself, is deleted.
// Running this with valgrind confirms there's a memory leak.

class Person_leak {
    string* name;

public:
    Person_leak(const string& name)
    : name(new string(name))
    { }

    void print() const {
        cout << "Name: \"" << *name << "\"\n";
    }
}; // Person_leak

void test_Person_leak() {
    Person_leak p{"Jane"};
    p.print();
}

////////////////////////////////////////////////////

// Person_manual_free1 objects fix the memory leak by providing a "free"
// function that, when called, deletes the string allocated in the
// constructor. It's up to the programmer to remember to always call free()
// before the object is deleted.
//
// In practice, this is easier said than done. In large programs, it's easy to
// miss one or two instance of calling free(), thus resulting in a memory
// leak. Also, there's nothing stopping you from call free too early; figuring
// out exactly when an object can be safely freed can be surprisingly tricky
// in some programs. Also, nothing stops free from being called more than once
// (i.e. double deletion); C++ says you should never delete the same object
// more than once.

class Person_manual_free1 {
    string* name;

public:
    Person_manual_free1(const string& name)
    : name(new string(name))
    { }

    void print() const {
        cout << "Name: \"" << *name << "\"\n";
    }

    void free() {
        delete name;
    }
}; // Person_manual_free1

void test_Person_manual_free1() {
    Person_manual_free1 p{"Jane"};
    p.print();
    p.free();
}

////////////////////////////////////////////////////

// Person_manual_free2 is an attempt at fixing the shortcomings of
// Person_manual_free1. The idea is to keep a flag variable that tracks
// whether the object is alive (free not yet called) or dead (free has been
// called). This way we can prevent multiple calls to free causing an error,
// and we can also throw an error if print() is called after calling free().
//
// But this is not a great solution. We still must remember to always call
// free() at the right time. Plus, there is now the problem is that we have
// two kinds of Person_manual_free2 objects --- living ones and dead ones. The
// dead objects still exist and take up memory. You can still point to dead
// objects, or store them in a vector, and so code that uses these objects
// will need to check to see if they are usable or not. This means you'll need
// if-statements everywhere in your program checking if the object is alive or
// not. See the examples function for the kinds of things you must now do to
// make this work.

class Person_manual_free2 {
    string* name;
    bool alive;

public:
    Person_manual_free2(const string& name)
    : name(new string(name)), alive(true)
    { }

    bool is_alive() const { return alive; }

    void print() const {
        if (!alive) throw runtime_error("object is dead");
        cout << "Name: \"" << *name << "\"\n";
    }

    void free() {
        if (alive) {
            delete name;
            alive = false;
        }
    }
}; // Person_manual_free2

void test_Person_manual_free2() {
    Person_manual_free2 p{"Jane"};
    p.print();
    p.free();
}

void test_Person_manual_free2_examples() {
    vector<Person_manual_free2> names;
    names.push_back(Person_manual_free2("Jane"));
    names.push_back(Person_manual_free2("Kelly"));
    names.push_back(Person_manual_free2("Bob"));
    names.push_back(Person_manual_free2("Erin"));

    // calling print() on a dead object throws an error
    for(int i = 0; i < names.size(); i++) {
        if (names[i].is_alive()) {
            names[i].print();
        }
    }

    // the size of the vector is different than the number of alive objects in
    // it
    int size = 0;
    for(int i = 0; i < names.size(); i++) {
        if (names[i].is_alive()) {
            ++size;
        }
    }
    cout << "size = " << size << "\n";

    // de-allocate all Person_manual_free2 objects
    for(int i = 0; i < names.size(); ++i) {
        names[i].free();
    }
}

////////////////////////////////////////////////////

// Person_destructor objects fix the memory leak by implementing a destructor
// that deletes the string allocated in the constructor. C++ guarantees that
// an object's destructor is automatically called when the object is deleted.
//
// Destructor's in C++ cannot be called manually, so there's never a problem
// with double-deletion. Plus, destructors are called when exceptions occur.
//
// Thus, Person_destructor objects clean-up after themselves without any
// special effort on the part of the programmer --- except for writing the
// destructor.

class Person_destructor {
    string* name;

public:
    Person_destructor(const string& name)
    : name(new string(name))
    { }

    void print() const {
        cout << "Name: \"" << *name << "\"\n";
    }

    ~Person_destructor() {
        delete name;
    }
}; // Person_destructor

void test_Person_destructor() {
    Person_destructor p{"Jane"};
    p.print();
    // C++ automatically calls p's destructor
}

////////////////////////////////////////////////////

// C++11 onward provides a number of standard classes for simplifying memory
// management. Here we use the unique_ptr<string> class to manage a pointer to
// a string object. unique_ptr<string> wraps a raw string pointer, and it
// makes sure to de-allocate it when name is deleted. Now the programmer does
// not need to write a destructor --- unique_ptr handles automatically de-
// allocates the object it points to.

class Person_unique_ptr {
    unique_ptr<string> name;

public:
    Person_unique_ptr(const string& name)
    : name(unique_ptr<string>(new string(name)))
    { }

    void print() const {
        cout << "Name: \"" << *name << "\"\n";
    }

}; // Person_unique_ptr

void test_Person_unique_ptr() {
    Person_unique_ptr p{"Jane"};
    p.print();
}

void raw_ptr_examples() {
    string* p = new string("Jane");
    string* q = p;  // both p and q point to "Jane"
    cout << *p << ", length=" << p->size() << "\n";
    cout << *q << ", length=" << q->size() << "\n";
    delete p; // "Jane" is deleted via p

    // But q does not know that the string it points to is no longer valid!

    cout << *q << ", length=" << q->size() << "\n";

    // You can think of the problem as being an "ownership" issue: who owns
    // the string "Jane", p, or q, or both? If we share ownership, then the
    // owners must communicate with each other, e.g. p must somehow tell q
    // that has deleted the string. The problem is that in C++ it can be very
    // difficult, or even impossible, to recognize shared ownership because
    // any could at any time a make pointer referring to an object.
}

void unique_ptr_examples() {
    unique_ptr<string> p{new string("Jane")};

    // unique_ptr use the regular * and -> pointer operators
    cout << *p << ", length=" << p->size() << "\n";

    // This is a compiler error: unique_ptr does not allow more than one
    // unique_ptr for an object.

    // unique_ptr<string> q{p};  // compiler error!
    // cout << *q << ", length=" << q->size() << "\n";

    // A unique_ptr can give up ownership of object to another unique_ptr
    // using the standard move function.
    unique_ptr<string> q{move(p)};
    cout << *q << ", length=" << q->size() << "\n";

    // p no longer points to "Jane", it's null.
    if (!p) {
        cout << "p doesn't point to anything\n";
    } else {
        cout << "p points to something: \"" << *p << "\"\n";
    }


    vector<unique_ptr<string>> names;
    names.push_back(unique_ptr<string>(new string("Bob")));
    // names.push_back(q); // compiler error: this would cause two unique_ptrs to refer
    //                     // to "Jane"
    names.push_back(move(q));
    for (int i = 0; i < names.size(); ++i) {
        cout << *names[i] << "\n";
    }

    cout << "-----\n";

    for (auto p = names.begin(); p < names.end(); ++p) {
        cout << **p << "\n";
    }

    // You can get around the guarantees of unique_ptr if you want to, so some
    // care is still needed to use it correctly. But in many basic cases, it
    // is a practical way to manage heap objects in C++.
}

int main() {
    // test_Person_leak();
    // test_Person_destructor();
    // test_Person_manual_free1();
    // test_Person_manual_free2_examples();
    // test_Person_manual_free2();
    // test_Person_unique_ptr();
    // raw_ptr_examples();
    unique_ptr_examples();
}

Escape Analysis

In C++, objects can be allocated either on the stack or the heap. You need to be careful not to mix them up. For example:

struct Point {
        double x, y;
};

Point* bad_make_origin() {
        Point p;  // point allocated on the stack
        p.x = 0;
        p.y = 0;
        return &p;
}

The problem with bad_make_origin is that it returns the address of the point p, which is declared on the stack. When &p is evaluated, the address is valid, but then when the function ends, p is popped from the stack which means the address &p referred to no longer contains a valid Point.

So you must instead write code like this:

Point* good_make_origin() {
        Point* p = new Point;  // point allocated on the free store (heap)
        p->x = 0;
        p->y = 0;
        return p;
}

When good_make_origin ends, the variable p is popped off the stack, but the Point object it points to stays unchanged on the heap.

In Go, however, things are bit different. Consider this code:

type Point struct {
        x, y float64
}

func make_origin() *Point {
        p := Point{0, 0}
        return &p
}

It might appear that make_origin() is returning a pointer to an invalid memory location, just like bad_make_origin() from above. But it turns out to work perfectly. In fact, this style of programming is enouraged in Go.

Here, the Go compiler uses escape analysis to figure out that p should be declared on the heap instead of the stack. The compiler can determing that a pointer to p “escapes” from make_origin(), and so allocates p on the heap.

Java is another language that is well-known for using escape analysis. In Java, objects can only be allocated on the heap using new, which tends to be inefficient for short-lived local objects in a function. With escape analysis, a Java compiler can sometimes prove that an object could instead be allocated on the stack.