Lab 11: Garbage Collection

This is the archived website of SI 413 from the Fall 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

This lab is due at 2359 on Thursday, 21 November. It should be submitted as "413 lab 11", with the files named properly according to the submit script. See the submit page for details. You are highly encouraged to submit whatever you have done by the end of this lab. Remember that duplicate submissions are fine; I will just grade the latest one when the time comes.

# Starter Code

The starter code for this week's lab is... the solution to last week's lab. You can stick with your own solution or use mine (or some combination thereof). But in either case you should download the updated Makefile and the new file builtin.hpp to keep things running smoothly.

# Background

Today's lab is all about garbage collection. In it, we will be using a few C++ features that we haven't seen yet: static methods, static fields, constructors, and deconstructors. Here's a brief overview on each.

## Static methods

Also sometimes called class methods, these are methods in a class that are not called on any particular object of that class. They have access to any static fields in the class (see below), but not any of the other fields, and they also have no this pointer.

You declare a static method by using the word static:

class SomeClass {
private:
...

public:
static int foo() { /* body of the method goes here. */ }
};

## Static fields

Static fields are data members that exist only once for the entire class, not for each individual object. Really, they are just dressed-up global variables.

The tricky thing with static fields is that they are declared in the class declaration in the header file, as usual, but they must also be declared, and possibly initialized, in some cpp file. So for example we might have

class SomeClass {
private:
static bool x;

public:
...
};

This would go in the header file. Then, in the cpp file, we have to initialize the static member as follows:

bool SomeClass::x = true;

## Constructors

Okay, we've been using constructors for a while now, so you should know what they look like. They're just like any other (non-static) class method, except that (1) there is no return type, and (2) the name is the same as the name of the class. For instance:

class SomeClass {
public:
SomeClass (int arg) { /* This is a constructor. */ }
};

## Destructors

We haven't yet seen destructors. These are called whenever an object is de-allocated at run time. Remember this can happen either when a local variable goes out of scope (i.e., the function or block it was declared in comes to an end), or when an object allocated using new is explicitly deallocated with a call to delete.

A destructor is again like any other class method, except that it has no return type, no arguments, and the name is a tilde (~) followed by the class name. For example:

class SomeClass {
public:
~SomeClass() { /* This is a destructor. */ }
};

(You won't necessarily have to write any destructors for this lab, I just wanted to make sure you know what they are.)

# Counting Frames

To help see why we really need automatic garbage collection in our SPL interpreter, let's see just how many frames are being created in our program. You'll do this by storing a big list of all the Frames that get created, as well as a way to access the size of this list from within an SPL program.

First thing to do is modify the Frame class to keep track of all Frames that get created in a list. This requires a few additions to the class:

• A static field of type list<Frame*> that will contain a pointer to every Frame object that is currently allocated by the interpreter. You will have to
#include <list>
at the beginning of frame.hpp to be able to use this built-in data structure. Then you'll need a declaration like
static list<Frame*> allFrames;
inside the Frame class, to declare the static member. Finally, you have to initialize this member somewhere outside the class. That means adding a line like
list<Frame*> Frame::allFrames;
at the beginning of the spl.ypp parser file, in the same place the other global variables are initialized.
• A (public) static method to get the number of Frames in memory. Of course this will just return the size of the list you just set up.
• A new line in the Frame constructor that adds a pointer to the newly-created frame to the list. (Remember the special keyword that is used to get a pointer to the current object?)
You might want use the push_back method of the list class; see here or here for more complete reference.

After these modifications, your SPL interpreter should work just fine, but you have no way of telling that it's doing anything differently. We want a function that can be called from within a SPL program to determine the number of Frames currently allocated in memory. Sounds like a perfect candidate for a built-in! Go back and review Lab 10 if you need help making another built-in function, or look at the starter code for this week's lab.

After you get this working, you should try some examples to see how many frames are created. You can of course run whatever examples you like, but here's a fun one that I made: a rather inefficient function to compute the prime factorization of any positive integer:

# Takes an integer and prints out all its prime factors
new factors := lambda n {

# Produces the remainder when the first argument is divided by the second
# (curried function)
new remainder := lambda a {
ret := lambda b {
ret := a - a/b*b;
};
};

# Returns the smallest (prime) factor of n, where n >= 2.
new smallest_factor := lambda n {
new helper := lambda i {
ifelse remainder@n@i = 0
{ ret := i; }
{ ret := helper@(i+1); }
};
ret := helper@2;
};

if n > 1 {
new p := smallest_factor@n;
write p;
factors@(n/p);
}
};

## Exercises

1. Modify the Frame class as described above to keep track of allocated frames in a list. There are no tests for this, but to help yourself debug, you might want to add, say, a debugging statement to the Frame constructor that prints out the current size of the list to cerr.
2. Create a built-in function frames that ignores its argument and returns the number of Frames in the list at that moment. (To emphasize, your built-in must take one argument, since that's how SPL works. It just shouldn't do anything with the argument.)
After this, you should be able to do something like:
spl> write frames@0;
3
spl> new sum := lambda n { 
ifelse n=1
{ret := 1;}
{ret := n + sum@(n-1);}
};
spl> sum@5;
spl> write frames@0;
20
spl> sum@100;
spl> write frames@0;
322

You definitely could write tests for this part, but don't. The reason is that we're about to implement garbage collection, so all the counts are going to change (for the better)! So no tests to submit for this exercise either.

# Mark and Sweep

Now we want to actually implement automatic garbage collection for our SPL interpreter. The basic idea is to add the following to the Frame class:

• A regular, non-static boolean field to indicate whether this Frame has been "marked".
• A non-static method mark to mark this Frame and anything this Frame points to.
• A static method sweep to delete and remove from the list any un-marked Frames.
• The ultimate goal (the exercise is listed below) is to have automatic mark-and-sweep garbage collection happen after every statement is executed by our interpreter. Once this is working, the number of Frames in memory after every step should shrink down to some very small number every time. You can proceed however you like; however, I recommend the following steps:

1. Add a field (NOT static) of type bool to the Frame class to indicate whether this frame has been marked. Add a line to the constructor to initialize this field to false.
2. Add a class method (also NOT static) called mark that performs the marking part of mark-and-sweep, starting with this Frame. If the this frame is already marked, then just return without doing anymore work. Otherwise, you want to set the boolean field to true, and make a recursive call on the parent frame (if it isn't NULL) and on the environment Frame of any Closure that is in the bindings of this Frame. To do this, you will need to loop through all the key-value pairs in bindings like this:
map<string,Value>::iterator iter = bindings.begin();
while (iter != bindings.end()) {
/* in here, "iter->second" is the Value.
* You see, *itr is a pair<string,Value>, i.e., a
* string-Value pair from the map. ".second" gives the second
* element of the pair --- the Value.
*/
++iter; // Increments the iterator to go to the next pair.
}
3. Finally, add a static class method sweep. This is going to go through all the Frame pointers in the list from step (i) and do one of two things:
• If the Frame is marked, then just unmark it (set the bool from step (i) to false).
• If the Frame is not marked, then call delete on it to de-allocate its memory, and remove its entry from the list.
For this part you will have to iterate through the list. This will be a loop similar to the one for iterating though bindings, except that now *iter will be of type Frame* rather than some kind of pair. Then you want to use the erase method in the list class (again, see references here or here) to remove list items as necessary. Careful: Your iterator will point to nonsense after you erase the corresponding entry. Luckily, the erase method returns an iterator to the next element in the list. But then you don't want to increment the iterator in this case!

## Exercises

1. Add automatic mark-and-sweep garbage collection in the while loop of your main in spl.ypp, to occur after every statement is executed. This means calling mark on the global frame, and then sweep.
IMPORTANT: There are actually two loops in the main method, for "interactive" and "non-interactive" usage. When I test your code, it runs the "non-interactive" version. So you will actually have to add the mark and sweep calls in two different places. It should be just after the call to tree->exec in both loops. Ask your instructor if you need help finding this!
2. Now test this! You need to submit at least 4 tests for this exercise. And make sure they're actually testing frame and garbage collection stuff. Simple modifications of my public tests will not suffice.

# Automatically-triggered GC

Great! Now that you have garbage collection, you can run a series of fairly computationally-intensive operations like (using my example SPL function above) factors@65432 over and over again without ever running out of memory.

But if you try to do it a few times in a block, or in a function, or loop, etc., the garbage collector never gets called and your program will run out of memory. Why? The problem is that garbage collection is currently only triggered from the top-level in spl.ypp. So now we want to improve on this by triggering garbage collection from within function calls, blocks, loops, and the like, whenever it is needed.

The tricky part is what we called the "root set" in class. See, it's no longer sufficient just to mark all the Frames that are reachable from the global frame, because the frame that we're currently executing in also needs to be considered. So we have to keep track of all the currently active frames in some sort of stack, and mark everything reachable from any of these frames before sweeping.

This is an optional exercise. Make sure you have completed AND SUBMITTED a working version of everything else before continuing. This will break your solution to exercise 3, so no skipping allowed!

Here are a few hints on how you might proceed:

• You should make a global variable for the "root set", the Frames that are currently in the function call stack and should definitely not be deleted yet. You should of course add the global frame to this set, but you also need to add Frames as they are created in Block::exec and Funcall::eval. These frames also NEED TO BE REMOVED when those methods return! (I used an STL vector to hold my root set, but you may do as you wish.)
• You will need to make a new static method (or something like it) that calls mark for every Frame in the root set, before sweeping. But where should this method be called from? You need to be really careful here that everything important gets marked. I would recommend just calling it in the Block::eval method, which should be good enough.
• Performing garbage collection too often is very wasteful, and creates a phenomenon known as "thrashing". Avoid this problem. (You will probably want some kind of counter to keep track of what has happened since the last time garbage was collected. You will have to set the threshold experimentally.)

## Exercises

1. (OPTIONAL) Implement automatically-triggered garbage collection as described above.