Compiler Design

Lecture 22: Garbage Collection

Christophe Dubach
Winter 2024

Original slides by Prof. Laurie Hendren,

updated by Alex Krolik, 2016 – 2020,
updated by Christophe Dubach, 2021 – 2023.

Timestamp: 2024/04/05 15:20:00

1
Garbage Collection

Memory Management

Manual Deallocation Mechanisms

Runtime Automatic Deallocation Mechanisms

Reference Counting
Mark-and-sweep
Stop-and-Copy
Pratical Considerations

Weak references

2
Memory Allocation

Stack Memory Allocation

• Space allocated in the call stack; call stack

caller

• Used for call information, local arguments stack

frame
return value
variables, and return values; FP frame pointer
return address

• Usually contains fixed size data; and local variables

callee
stack

• Is allocated and deallocated at the

frame
saved registers
SP
beginning and end of a function.

Information stored in the stack is therefore specific to a particular

function invocation (i.e. call).

3
Heap Memory Allocation
• Space allocated in the program heap;
• Very dynamic in nature:
• Unknown size; and
• Unknown time;
• Requires additional runtime support for managing heap space.
Information stored in the heap is therefore not necessarily tied to
any particular function invocation.

Example Heap

Heap variables may be referred to by other

2
objects in the heap, or from the stack.

4
Heap Memory Allocation

Data stored in the heap is controlled by a heap allocator: malloc.

• Manages the memory in the heap space;

• Takes as input the size (in byte) needed for the allocation;
• Finds unallocated space in the heap large enough to
accommodate the request; and
• Returns a pointer to the newly allocated space.

You will find more details in an operating systems course.

5
Heap Memory Deallocations

Memory allocated on the heap is freed when it is no longer needed.

This can be:

• Manual:
• User code makes the necessary decisions on what is live and when
to deallocate (e.g. using free).
• Automatic:
• Continuous: Runtime code determines on the spot which objects
are live; or
• Periodic: Runtime code determines at specific times which objects
are live.

Without runtime support the program must explicitly return the

memory when it is no longer needed.

6
Heap Memory Deallocations

12 
r
p r
q 37 - 15
r r
For this class, we will assume that the r
r
freed heap blocks are stored on a
7
freelist (a linked list of heap blocks). - 37 
r
Freeing an object prepends the heap r
block onto the list. 59 
r
r
r - r
freelist 9
- 20
r
r

7
Garbage Collection

Memory Management

Manual Deallocation Mechanisms

Runtime Automatic Deallocation Mechanisms

Reference Counting
Mark-and-sweep
Stop-and-Copy
Pratical Considerations

Weak references

8
Manual Deallocation Mechanisms

Heap memory can be freed manually at any point in the program.

• Programmers determine when an object is no longer live; and

• Requires calls to a deallocator (i.e. free).

Consider the following code

int *a = malloc ( s i z e o f ( i n t ) ) ;

// . . . use o f a

free ( a ) ;

// . . .

*a = 5 ; // what happens ?

9
Manual Deallocation Mechanisms

Advantages

• Reduces runtime complexity;

• Gives the programmer full control on what is live; and
• Can be more efficient in some circumstances.

Disadvantages

• Requires extensive effort from the programmer;

• Gives the programmer full control on what is live;
• Error-prone; and
• Can be less efficient in some circumstances.

10
Manual Deallocation Mechanisms

Sometimes manual deallocation is slower than automatic methods.

Consider the following example code, which allocates 100 integers
and then deallocates them one-by-one.
f o r ( i n t i = 0 ; i < 1 0 0 ; ++ i ) {
a [ i ] = malloc ( s i z e o f ( i n t ) ) ;
}

...

f o r ( i n t i = 0 ; i < 1 0 0 ; ++ i ) {
free ( a [ i ] ) ;
}

This is potentially inefficient. Why?

The allocations are potentially contiguous, and could therefore be
reclaimed as a block instead of one-by-one.

11
Manual Deallocation Mechanisms

Life Without Garbage Collection

• Dead records must be Memory leaks in real life (ical v.2.1)

explicitly deallocated; 31
MB
30
29
• “Superior” if done 28
27
26
correctly; but 25
24
23
22
• It is easy to miss some 21
20
19
18
records; 17
16
15
14
• It is “dangerous” to 13
12
11
10
handle pointers; and 9
8
7
6
• May be less efficient in 5
4
3
some cases. 2
1
0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

hours

12
Garbage Collection

Memory Management

Manual Deallocation Mechanisms

Runtime Automatic Deallocation Mechanisms

Reference Counting
Mark-and-sweep
Stop-and-Copy
Pratical Considerations

Weak references

13
Runtime Deallocation Mechanisms

A runtime deallocation mechanism must answer the question:

Which records are dead, i.e. no longer in use?

The more precise the answer, the better the deallocation mechanism.
Ideally: Records that will never be accessed in the future.
→ But this is undecidable, e.g.:
int * foo ( i n t a ) {
i n t * p1 = ( i n t * ) malloc ( 1 6 ) ;
i n t * p2 = ( i n t * ) malloc ( 1 6 ) ;
i f ( a < 3 ) r e t u r n p1 e l s e r e t u r n p2 ; }

Basic conservative assumption

• A record is live if it is reachable from a stack-based variable or

global variable, otherwise dead.

14
Example Heap

12 
r
p r r
q 37 - 15
r r r
r
r
Consider the following example heap, with stack 7
variables: p, q and r. - 37 
r
• Which records are live? r
• Which records are dead? 59
r
r
r
-9
- 20
r
r

15
Runtime Deallocation Mechanisms

A garbage collector

• Is part of the runtime system; and

• Automatically reclaims heap-allocated records that are no
longer used.

A garbage collector should

• Reclaim all unused records;

• Spend very little time per record;
• Not cause significant delays; and
• Allow all of memory to be used.

These are difficult and often conflicting requirements.

16
Garbage Collection

In this class we will study three types of garbage collection:

• Reference counting;
• Mark-and-sweep; and
• Stop-and-copy.

For each algorithm we will discuss the implementation, an example,

and the associated advantages/disadvantages.

17
Runtime Automatic Deallocation
Mechanisms

Reference Counting
Reference Counting

• Is a type of continuous (or incremental) garbage collection;

• Uses a field on each object (the reference count) to track
incoming pointers; and
• Determines an object is dead when its reference count reaches
zero.

The reference count is updated

• Whenever a reference is changed:
• Created
e.g. int *a = b; // b refcount++
• Destroyed
e.g. a = c; // b refcount--
• Whenever a local variable goes out of scope;
• Whenever an object is deallocated: all objects it points to have
their reference counts decremented.
18
Reference Counting

Reference counting inserts calls to increment and decrement in

the source program as needed.
When the object is no longer needed, a call to free is made.

Pseudo code for reference counting

function increment(x) function free(x)

x.count = x.count+1 ∀ field fi with a ref do
decrement(fi )
function decrement(x) x.f1 = freelist
x.count = x.count−1 freelist = x
if x.count == 0 then
free(x)

19
Example
c l a s s A { i n t count ; // r e f counting
int y ; }
c l a s s B { i n t count ; // r e f counting
int x ;
A a;}
B foo ( i n t c ) {
A a1 = new A ( ) ;
A a2 = new A ( ) ;
B b = new B ( ) ;

b . a = a1 ;

i f ( c >4) {
b . a = a2 ;

return b ;
}

20
Example with increment/decrement calls
c l a s s A { i n t count ; // r e f counting
int y ; }
c l a s s B { i n t count ; // r e f counting
int x ;
A a;}
B foo ( i n t c ) {
A a1 = new A ( ) ; // a1 . count = 1 ;
A a2 = new A ( ) ; // a2 . count = 1 ;
B b = new B ( ) ; // b . count = 1 ;

decrement ( b . a ) ; // i f b . a i s n u l l , no e f f e c t
b . a = a1 ;
increment ( a1 ) ; // a1 . count = 2 ;

i f ( c >4) {
decrement ( b . a ) ; // a1 . count = 1 ;
b . a = a2 ;
increment ( a2 ) ; // a2 . count = 2 ;
}

decrement ( a1 ) ; // a1 . count = ?
decrement ( a2 ) ; // a2 . count = ?
return b ;
}

21
Reference Counting

12 
r
p r r
q 37 - 15
r r r
r
r
Reference counting has one big problem: 7
• What about the objects with number 7 & 9? - 37 
r
r
How can we even have this situation? 59
r
r
r
-9
- 20
r
r

22
Reference Counting

Advantages

• Is incremental, distributing the cost over a long period;

• Does not require long pauses to handle deallocations;
• Catches dead objects immediately; and
• Requires no effort from the user.

Disadvantages

• Is incremental, slowing down the program continuously; and

• Cannot handle circular data structures.

23
Automatic Reference Counting (ARC)

Initially for Objective-C (now also for Swift), automatic reference

counting (ARC) is a reference counting implementation designed by
Apple and integrated into Clang.

• Inserts calls to retain (increment) and release (decrement)

at compile time;

Previously, developers inserted manual calls to the memory

management methods.

24
Smart pointers

Alternative to ARC is to use smart pointers, such as ones found in the

C++ Standard Library:

• unique_ptr, shared_ptr, weak_ptr

• automatically decremented when out of scope
(using C++ destructor mechanism)
• if you want to learn more (you should!):
https://en.cppreference.com/book/intro/smart_pointers

25
Runtime Automatic Deallocation
Mechanisms

Mark-and-sweep
Mark-and-Sweep

The mark-and-sweep algorithm is a periodic approach to garbage

collection that has 3 main steps:

1. Explore pointers starting from the program (stack & global)

variables, and mark all records encountered;
2. Sweep through all records in the heap and reclaim the
unmarked ones; and
3. Finish by unmarking all marked records.

Assumptions

• We know which fields are pointers;

• We know the size of each record; and
• Reclaimed records are kept in a freelist.

26
Mark-and-Sweep

The 3 steps of the mark-and-sweep algorithm are shown below

(steps 2 and 3 are merged).
Pseudo code for mark-and-sweep

function mark()
for each program variable v do function sweep()
dfs(v) p = first address in heap
while p < last address in heap do
function dfs(x) if record p is marked then
if x is pointer into heap then unmark record p
if record x not marked then else
mark record x p.f1 = freelist
for i=1 to |x| do freelist = p
dfs(x.fi ) p = p+sizeof(record p)

27
Mark-and-Sweep

Mark Sweep
12  12 
r r
p r r p r
q 37 q 37
r r - 15
r r
- 15
r
r r
r r
7 7
- 37  - 37 
r r
r r
59  59 
r r
r r
r r - r
freelist -9 freelist 9
- 20 - 20
r r
r r
28
Analysis of Mark-and-Sweep

• Assume the heap has size H words; and

• Assume that R words are reachable.

The cost of garbage collection: O(R + C)

29
Mark-and-Sweep

Advantages

• Is periodic, so does not slow down each operation in your

program;
• Can be run in parallel to your program;
• Mark and sweep steps can be parallelized too;
• Requires no effort from the user.

Disadvantages

• Scanning the heap can be expensive;

• The heap may become fragmented: containing many small free
records but none that are large enough for the next allocation.

30
Heap Fragmentation

To deal with fragmented heaps we can use compaction.

• Once mark-and-sweep has finished, collect all live objects at the

beginning of the heap;
• Adjust pointers pointing to all moved objects;
• The adjustment depends on the amount of space freed before
the object;
• This removes fragmentation and improves locality.

31
Runtime Automatic Deallocation
Mechanisms

Stop-and-Copy
Stop-and-Copy

Stop-and-copy is a periodic approach to garbage collection that:

• Divides the heap into two parts;

• Only uses one part at a time;

Conceptually this results in a simple high-level algorithm:

1. Use the active half of the heap for all allocations;

2. When it runs full, copy live records to the other part; and
3. Switch the roles of the two parts.

A Nonrecursive List Compacting Algorithm, C. J. Cheney, Commun. ACM, 1970.

32
Stop-and-Copy

Consider the following snapshots of stop-and-copy before/after

execution.

• next and limit indicate the available heap space; and

• Copied records are contiguous in memory.
q q -q
q q q
q q q q
q -q
q q
q
q
-q q
q q 
next
q
q
q
q
  limit
from-space to-space from-space to-space
next
limit

33
Stop-and-Copy

Objects on the stack are processed one at a time as follows:

• If the object has not yet been moved to to-space, copy the object
fields to to-space and update the first field of the from-space
version with a forwarding reference to the to-space copy.
Then update the objet reference from the stack to refer to the
copy in the to-space.
• If the object has already been moved to to-space, update the
object reference from the stack to refer to the copy in the
to-space (using first field of the object which points to the copy).

Then, we simply process all the objects in the to-space, performing

one of the actions above for each field of the object (which holds a
reference).

34
Pseudo code for stop-and-copy
function forward(obj)
if obj ∈ from-space then
if obj.f1 ∈ to-space then
function copy()
// copy already made
scan = next = start of to-space
return obj.f1
for each object obj on stack do
else // copy obj to new space
obj = forward(obj)
for i=1 to |obj| do
while scan < next do
next.fi = obj.fi
for i=1 to |scan| do
obj.f1 = next
scan.fi = forward(scan.fi )
next = next+sizeof(obj)
scan = scan+sizeof(record scan)
return obj.f1
else return obj

35
Stop-and-Copy

The follow are snapshots of stop-and-copy before executing and

after forwarding the top-level and scanning 1 record.
12  -q - 15
-
q q q
q q p q p q q
15 
37 q
q q q 37
q
- 37 

q r q r q scan
-
q q q
q q - 12 
7 7 q
- 37  -q q
q q  next
q q
59  59 

q q
q q
q q
-9 -9
- 20 - 20 
q q
q q
before after forwarding p, q, and r and scanning 1 record

36
Analysis of Stop-and-Copy

• Assume the heap has size H words; and

• Assume that R words are reachable.

The cost of garbage collection is now: O(R)

37
Stop-and-Copy

Advantages

• Allows fast allocation (no freelist);

• Avoids fragmentation;
• Collects in time proportional to R.

Disadvantage

• Wastes half your memory; and

• Stops the program to execute.

38
Runtime Automatic Deallocation
Mechanisms

Pratical Considerations
Practical Considerations

In practice, we use either mark-and-sweep or stop-and-copy (and in

some systems ref. counting).
This can lead to better memory management, at the cost of ∼ 100
instructions for a small object.
Each algorithm can be further extended by

• Generational collection (to make it run faster); and

• Incremental (or concurrent) collection (to make it run smoother).

39
Generational Collection

Observation: the young die quickly

Given this assumption, the garbage collector should:

• Focus on young records;

• Divide the heap into generations: G0 , G1 , G2 , . . .;
• All records in Gi are younger than records in Gi+1 ;
• Collect G0 often, G1 less often, and so on; and
• Promote a record from Gi to Gi+1 when it survives several
collections.

40
Other Optimizations

Exploit locality

• Keep youngest generation small enough to fit in the CPU cache

Incremental collection

• Garbage collection may cause long pauses;

• This is undesirable for interactive or real-time programs; so
• Try to interleave the garbage collection with the program
execution (e.g. Train algorithm).

41
Earlier Assumptions

The presented garbage collection algorithms assumed that:

• We know the size of each record; and

• We know which fields are pointers.

For object-oriented languages, each record already contains a

pointer to a class descriptor, so garbage collection is straightforward
to implement.
For general languages, we must sacrifice a few bytes per record to
indicate its size, and its organization.

42
Garbage Collection

Memory Management

Manual Deallocation Mechanisms

Runtime Automatic Deallocation Mechanisms

Reference Counting
Mark-and-sweep
Stop-and-Copy
Pratical Considerations

Weak references

43
Weak references

Many programming languages/libraries provide weak references:

• C++ Standard Library: weak_ptr

• Java: class java.lang.ref.WeakReference
• Scala: class scala.ref.WeakReference
• Python: module weakref
• ...

In the context of garbage collection, a weak reference to an object is

not enough to keep the object alive. It is as if that reference does not
exist from the point of view of the garbage collection mechanism.

When garbage collection happens, all objects whose only references

are WeakReferences will be garbage collected.

44
Example
s t a t i c WeakReference < Object > foo ( ) {
O b j e c t r e f e r e n t = new O b j e c t ( ) ;
r e t u r n new WeakReference ( r e f e r e n t ) ;
}

p u b l i c s t a t i c void main ( S t r i n g [ ] a r g s ) {
WeakReference wr = foo ( ) ;
// System . gc ( ) ;
O b j e c t r e f e r e n t = wr . g e t ( ) ;
i f ( referent != null )
System . out . p r i n t l n ( ” hasn ’ t been garbaged c o l l e c t e d y e t ” ) ;
else
System . out . p r i n t l n ( ” has been garbaged c o l l e c t e d ” ) ;
}

System.gc() can be used as a hint to trigger garbage collection.

45
WeakHashMap

Weak references are a very useful feature to implement higher-level

data structures such as a WeakHashMap<Key,Value>.
Any value stored in a WeakHashMap will only be weakly referenced
in the Map. These values can be removed from the Map
automatically when they are garbage collected.

In the case of a compiler, could use a WeakHashMap to store

information about the IR. If an IR node later disappear, the
information attached to it will be automatically garbage collected.

46
Example :use WeakHashMap to store type information:
Map< Expr , Type > typeMap = new WeakHashMap ( ) ;

Populate type information during type-checking

class TypeAnalyzer {

Type v i s i t ( ASTNode node ) {

...
case I n t L i t t e r a l i t −> {
typeMap . put ( i t , BaseType . INT ) ;
r e t u r n BaseType . INT ;
}
...

If an AST node is deleted later on (e.g. as a result of an optimization),

the associated type information is automatically removed from the
weakMap when garbage collection occurs.

47
Final word on references

Programming languages usually have more kind of references. For

instance in Java:

• Hard references: the one you usually use

• Weak references: objects only referred by such references are
always garbage collected
• Soft references: objects only referred by such references are
only garbage collected if running out of memory
⇒ used to implement efficient software caches
• PhantomReference: have to do with finalizers

48
Next lecture

Concluding remarks:

• Big compiler research questions;

• What’s next for you?

49