Mark-Sweep Garbage Collector for WACC Compiler

Mark-Sweep Garbage Collector

The reason we have chosen a Mark-Sweep algorithm is its power of removing cyclic dependencies between memory blocks. We have come to the conclusion that this implementation would provide a practical asymptotic computational complexity for a single collection of O(M * (M + R)) where M represents the number of heap-allocated memory blocks and R the number of nested references of a block. We have chosen to do an object-oriented cross implementation using C++ function calls from the ARM assembly generated file.

In order to interfere, the garbage collector needed to construct its cache of memory blocks and to periodically crawl through and check which ones should be kept further. Therefore, we took the decision to modify our code generator to call caching functions for newly allocated memory blocks. Moreover, we dealt with the high level processes that cause changes to occur in the state of the heap:

Scoping
- When entering a new scope we get hold of the stack pointer and the number of variables which are on the stack. This way, we have set the bounds of this scope beyond which any memory block belonging to it should be marked as not alive and all root blocks should be cached as non-root. Any root block is reachable from the stack in the current scope.
Declaration
- Fresh heap allocation On each memory allocation, an external function call to a cached_malloc creates a new memory block and adds it to the vector of blocks contained in the garbage collector.
- Stack variable declaration The new stack variable’s address will be added in the set of stack addresses of the referenced memory block, which will be marked as root.
Assignment
- The address, references and block size of the right hand side member are transferred to the one on the left hand side.

Heap Internal Representation

We have chosen to represent heap blocks by a C++ class containing household data members that indicate its size in bytes, whether it is root or it should be collected. All stack addresses that reference the block are stored in an ordered set providing logarithmic complexity for retrieval and ease on chopping stack addresses when exiting a scope and all outwards references of that block are stored in an unordered set, providing constant time complexity for reference retrieval. The graph of memory blocks is stored as an adjacency list in the garbage collector class.

Collection Phase

Split in two phases: Mark and Sweep. During the first phase we perform depth-first search from each node, marking each dead block as ready for collection. A block is dead when it cannot be reached from the stack via any path. The second step is to remove all the cached blocks from the vector and to perform the actual free of the heap address. This process does not allow multiple deallocations to occur.

Profiling

The product is a stop-the-world garbage collector with a modifiable invocation rate. For testing, at every two allocations, the garbage mark-sweep algorithm is run over the heap blocks, checking whether any of the remaining blocks are unreachable and therefore eligible for removal. One of the analyzed WACC programs consists of two nested while loops, the outer one allocating a uni-dimensional array int[] a = [1, 2, 3]and the inner one a bi-dimensional array int[][] b = [a] (See Figure 1). Running the valgrind memory check tool on a Raspberry Pi, we obtained 854 allocs, 854 frees, 14,636 bytes allocated. The result proves that not only the root blocks have been freed, but also their inner references. Using the massif memory profiling tool, under the assumption that the number of cached memory blocks and the number of actual heap blocks have the same lifetime, we obtained the graph in Figure 2. The time-irregular snapshots show the memory consumption against the number of instructions executed.

One of the main difficulties in profiling and memory leak detection on cross-compiled code is lack of reliable tools. To make a general idea of how much memory our garbage collector consumes, we made a Python script that would lunch a sub-process of an infinite loop WACC program in qemu and measure the amount of memory it takes. To do that we embedded bash command inside the Python script and plotted the final results. This plots helped us detecting memory leaks and approximate the efficiency of our program (see Figure 3 and Figure 4).

Further Development

The garbage collector can be improved firstly in terms of efficiency. As we have not used any caches (for example scope caches for memory blocks), all operations on blocks involve a linear time complexity look-up. A rather more intuitive approach would be to use a tree data structure for a better, logarithmic complexity, of the mark-sweep algorithm. Modifying the work-flow could also yield an improvement by using more advanced data structures such as disjoint data sets and randomized treaps (average complexity of O(N * log_star N) where log_star refers to the inverse of the Ackermann function). Moreover, the aforementioned caches can build a whole new functional paradigm of our garbage collector and transform it into a generational one. This way, only some newer generations can face the collection process, thus improving time overhead.

Running the garbage collector periodically in a stop-the-world manner causes a non-uniform use of computer resources (CPU cores), therefore we consider an improvement on the side of making a multi-threaded collector.