Mnemonic nibbles

Memory management: Automatic or manual

So far we have discussed how memory registers are manipulated by assembly programs, constituting the immediately accessible memory of the processor. But since these memory registers are limited in number (about thirty generally), what happens if we require more memory? Or if you need to store a large object thus using multiple memory locations at the same time? Beyond these concerns, it is interesting to see how different programming languages conceptualise memory and memory management. It is to be notes that we pay a heavy price for abstraction by suffering losses in performance.

Physical Memory

In addition to the registers accessible by the processor, there are two types of memory. Non-volatile storage (hard disks, USB sticks) is persistent, that is it survives even when the computer is not powered but imposes slow speeds for reading or writing memory. Volatile memory (or RAM) does not survive power failure (a dynamic memory slot is a capacitor that discharges fairly quickly), but is much faster. These characteristics make it crucial for the program and its data to be loaded into RAM at runtime, otherwise there will be very high latency. This is why the amount of RAM has a strong influence on the ability of a computer to support heavy programs like video games.

Let’s now focus on RAM since that’s where the data from our program lives. Remember that in a computer the memory consists of bits that can take the value 0 or 1. They are frequently grouped into packets of 8 called bytes. The assembler’s instructions essentially allow us to manipulate memory as follows:

  • volatile memory can be thought as an array where each entry of the table refers to a memory location. The memory locations have addresses between 0 and \(2^{64}\) (if the address is noted using 64 bits) ;
  • basic assembly instructions allow us to read 1, 2, 4 or 8 bytes at a time stored at a given memory location and transfer them to a register, or write some data from a register to a memory location;
  • a memory address is just like a real number: we can perform basic arithmetic with a memory address. For instances, to compute the address of an element in an array, we perform a simple operation: \(\mathrm{base} + (\mathrm{size}\times\mathrm{index}) \).
image
Memory as an array of bytes.

Thus, when a program has more variables than registers, some are transferred to the RAM. This memory is also used to store everything that does not fit in a memory register: arrays, complex objects (such as classes), etc. Nevertheless, these complex objects are not conceptually represented in assembler: the abstraction as an array stems from our choice to place elements having the same size side by side in memory. But this abstraction is very convenient for the developer, and that is why all high-level programming languages have an implementation for it. So we see here that it is interesting for a language to offer the developer some abstractions for managing memory.

Manual memory management: beware of leaks

As the program progresses, more and more objects of different sizes will be written to the RAM. But how does one decide at which address to write a new object? We are thus confronted with the task of allocating memory when writing an object in memory. The simplest manner is to start allocating at the beginning of the array, and then following the last allocated memory area each time. Thus, objects are never erased and can be accessed whenever we want. But what happens when an object is never accessed again? With our solution, it stays there indefinitely and occupies space in memory; in this way we quickly saturate the RAM of our computer is quickly saturated. This is referred to as a memory leak

image
Memory blocks are allocated one after another.

To avoid this scenario, the programming language will offer the developer the option to free memory, in addition to the ability of allocating it. Thus, when she knows that she no longer needs to access the object in memory, the developer frees the memory block. But if the allocation of memory is translated into assembler by writing the object to a given address, how does one translate the freeing of this memory block? The answer is: by nothing. Indeed, the program will leave this area of memory as is; on the other hand, it will note that the memory located at this address is free, which means that it can be allocated again.

Thus, as the program progresses, we will continuously allocate and free memory. In turn, the memory array will look like the mouth of a child as she loses her milk teeth, replaced by permanent ones: that is there will be memory blocks of different sizes (allocated and freed) mixed randomly. Therefore, we are now presented with the option of compacting the memory, that is to allocate the memory by plugging the holes due to freed memory locations whenever possible. This is done in order to keep large blocks free in anticipation of a hypothetical allocation of a large amount of memory, which can, in principle, occur anytime.

image
After multiple allocations and releases, there is no single contiguous chunk of free space remaining.

With this management, the physical memory has been abstracted away and its linear character is hidden from the developer: the objects seem to live like marbles in a big bag, from which one can withdraw or add as one pleases. Such manual memory management is however demanding for the developer who must not forget to free memory each time it has been allocated. Manual management exposes the developer to the concept of the lifespan of an object, which forces her to constantly worry about memory. Live objects must be separated from dead objects in order to reuse memory. In order to free themselves from this burden, other languages have adopted a different approach.

Garbage Collection

We must now face the following constraint: the developer no longer declares the release of declared objects. How then can we avoid memory leaks? We lost the information that allowed us to distinguish a living object from a dead one; we must find it.

For this, at regular intervals, we stop the execution of the program and look at the memory. What are the living objects? First, all the objects contained in the memory registers, the immediate memory, can be considered as living (with few exceptions). Next, all objects in memory that correspond to local variables of active functions are alive as well. Is that all? In a sense, yes, because the program can not directly access variables other than these (we assume that the program can’t just pick any memory address). However, these variables and living objects may contain addresses of other objects, which in turn become alive as well. Moreover, the objects referred to these newly alive objects become alive as well. Thus we collect these objects together with their web of connections in a suitable representation i.e. a graph. Once done, what remains? A few scattered crumbs of memory, memories of dead objects that can be released without fear because these are inaccessible by the program.

This algorithm called “mark and sweep” is one of the few classic algorithms for what is called garbage collection i.e. releasing memory used for storing dead objects. There are other algorithms that serve the same purpose, each with its advantages and disadvantages. The garbage collector is abbreviated to GC and is a distinguishing feature of a programming language.

image
Graph of objects in memory. Here d is no longer accessible and hence can be freed.

Indeed, if the GC allows the developer to no longer worry about memory management, it is only at the expense of performance, both in terms of execution time and the compactness of the memory. Recall that the GC tries to reconstruct information not given by the developer; the analysis that it carries out is therefore conservative, thus, out of precaution, it will consider some objects as alive even though they will never be accessed by the program in the future. This impacts the compactness of the memory compared to manual management, or when the developer knows exactly when the objects were used the last time. Finally, the execution of the program must stop each time the GC does its magic, and the time for graph traversal increases as we use more and more memory.

The cost of abstraction

A language with garbage collection thus completely does away with the concept of memory, and the developer has the impression of manipulating objects without any constraint. Nevertheless, this abstraction leads to a loss in performance, typically about an order of magnitude at runtime. Intermediately, manual memory management provides a less convenient abstraction but at a very low cost compared to the performance of a program written directly in assembler. Hence we see a very strong compromise between ergonomics of a language and its performance. As far as memory is concerned, it is not possible to have your cake and eat it too, and the decision to endow a language with a GC or not directly determines its applications; a successful program is always harder to write!

Further reading

  • This post and others in the series by Lin Clark illustrate how memory is managed in a web browser. This article is directly inspired from these posts.
  • Visualisation of how different garbage collection (GC) algorithms function.
  • Explaining how GC works in Python. Simpler than the graph traversal mentioned here.
  • This reddit post and answers provide a complete tour of the various memory management strategies.