To garbage collect or not to garbage collect

Many computer programs require more memory as the size of the data increases. For example, a spreadsheet uses more RAM if the sheet contains more columns and rows. If you delete a row or column of the spreadsheet, the RAM used by it should be freed, so it can be reused later if new rows or columns get added to it. If you delete parts of a spreadsheet and the RAM does not get freed, the program will keep using more and more RAM as you delete cells and later add new cells, even if the total size of the spreadsheet does not increase. This is called a memory leak. The longer you use the program, the more RAM it will use, until it requires more RAM than is available and the program crashes.

Many programs require the capability to dynamically allocate memory. Support in programming language varies. Most versions of BASIC do not allow you to allocate entirely new objects and arrays cannot be resized. However, strings can be of variable length, so you use way more memory if you have long strings in a string array, compared to the situation where all strings are null strings. In Python on the other hand, you can dynamically resize lists and even store new lists inside lists.

Allocation

Memory is allocated on what we mostly call the “heap”. A memory address range is reserved for the heap. When a program needs more RAM, it calls an operating system function to allocate a large chunk of memory in that address range. When that memory fills up and still more memory is needed, another system call is made to add more memory to the heap. Within that address range, the runtime library manages the blocks that are free and that are allocated. Free blocks are on a free list. When an allocation function is called, a free block is taken from the free list. When the free block was (much) larger than the amount of memory requested, the block is split. The used part is allocated and the unused part is put back on the free list. When an allocated block is freed, it is put on the free list again. If the freed block is next to another free block, these two blocks are usually merged into a single larger free block.

Even if we do everything right and free each block as soon as it is no longer in use, the heap may get fragmented. The total amount of free space may be large enough, but the free space may consist of many small blocks with allocated blocks in between.

Also an allocation may take much longer if a long free list must be traversed before a suitable block is found.

Some languages, like Zig allow you to specify which allocator you want to use in which situation, so you can have an allocator that is more suitable for a specific application.

Garbage Collection.

If you delete an object (for example a list) in Python, the Python interpreter itself takes care to free that memory. Take the following code fragment:

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b = a
a = None
b = None

The first line allocates memory for a list of 10 numbers. The variable a stores a reference to that list. The second line causes variable b to store a reference to the same list. The list is not copied: it’s the same list in the same memory. The third line causes the variable a to no longer refer to the list. But the list is still accessible through variable b, so it cannot be freed. The fourth line causes variable b to no longer refer to that list. Now it becomes unreferenced and it can be freed.

Earlier versions of Python used a reference count in each object. Line 1 would give the list reference count 1 (only one reference from variable a). Line 2 would increase the reference count to 2, line 3 would decrement it to 1 and line 4 would decrement it to 0, in which case it was time to free the memory. This is comparatively simple, but it would not work in case cyclic references exists. Lists can store references to other list (or even to the same list). Take for example the following Python fragment:

a = [1, 2, 3, 4, 5]
b = [10, a]
a[4] = b
a = None
b = None

The first three lines create a pair of lists that contain references to each other. List b has two elements: the number 10 and (a reference to) list a. List a has five elements: the numbers 1 through 4 and a reference to list b. Even when the variables are reassigned, the references inside the two lists remain valid and the reference counts will not decrease to 0. Both lists will be inaccessible though, as there are no other references from outside. Therefore, modern versions have a true garbage collector (in addition to the reference counting), to free up memory in situations like this.

A garbage collector performs the following job:

• It starts from all variables that contain references to objects. Those objects are marked.
• For all marked objects, check which other objects are referenced from them. If they are not already marked, mark them and repeat the operation for the newly marked objects.
• Free all allocated objects that are not marked.
• Remove the marking from the marked objects.

The job of a garbage collector is very complex. It uses much CPU power and while it is marking all dynamic objects that are still reachable, all operations of the program must be paused. This is unacceptable for hard real-time systems. If the program is supposed to react within 5 ms, we cannot accept that the program is frozen for 500 ms during garbage collection. In general you have no control when the garbage collector will kick in and when a large chunk of memory will actually be freed.

Languages like Python, Lisp, Java and Go have a garbage collector. Of all these, Go is a truly compiled language and its garbage collector is state of the art and aims to reduce the duration of any pauses in the program.

Manual Free

C is on the other extreme. See the following code snippet:

int *a = malloc(10 * sizeof(int));
int *b = a;
if (a == NULL) return -1;
...
free(a);

In the first line, we call the malloc function to allocate a chunk of memory for an array of 10 integers. We have to calculate the size manually: multiply 10 (the number of integers we want) by the size of one integer. Of course we have to check that the returned pointer is non-null.

The variable b points to the exact same array.

At the end of the program, we free the memory again. If we forget to free, we create a memory leak, if we free too soon, some pointers may still point to it, while the data in that memory range is no longer valid; the runtime system may have reused it for completely different purposes. If we call free(a), we may set a to the NULL pointer to prevent it from being used to access the array, but we may have forgotten about pointer b, which still points to the same memory.

Manual free leaves room for a lot of bugs that would be prevented by using garbage collection.

C,Pascal and Zig use manual free. C++ has this too, but it also has managed data types that take care of allocation and freeing internally.

Rust

And then of course we have Rust. Rust has no garbage collector, but it severely restricts how pointers (references) may be passed around. A dynamically allocated object always has one “owner”, which will be responsible for freeing it. References to objects can be “borrowed” by other functions, in which case they are temporarily unavailable to the owner. This is all checked by the compiler. The compiler knows when an object can be freed and it takes care to call free when appropriate, so you don’t have to do this explicitly.

Due to the restrictions that Rust puts on copying of pointers, it is not really possible to have data structures with cyclic references either.

The advantages of Rust:

• You don’t have a garbage collector with the runtime overhead and nondeterministic timing.
• You get memory safety with respect to freed dynamic memory. No use after free or double free and no memory leaks.
• Rust also makes sure that in a multithreaded environment, only one thread gets access to any given object at the same time (multiple readers are okay, but a writer needs truly exclusive access)..

Disadvantages of Rust:

• Some data structures, consisting of nodes linked by pointers, are impossible to create.
• Semantics of ownership and of the borrow checker are extremely complex. Getting a program compiled at all, can be a frustrating experience for beginners.