Lab 11: Garbage Collection

This lab is due at the beginning of your next regular lab, which will be TWO WEEKS from today, after Thanksgiving.

This lab contains only electronic parts, to be submitted using the submit program. Be sure to add entries to features.txt as indicated for each exercise. See the Lab 3 page for details on the format.

You can (and should) work with a partner for this lab, and if so, only one of you should submit.

Your electronic submission should come from a folder called lab11. The following files must be included:

features.txt: Specification for testing.
Makefile: If I type make spl, this program should be compiled from source.
ex3.txt, transcript from Exercise 3

Most of your work for this lab will be in frame.hpp frame.cpp, and spl.ypp.

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).

Background

Today's lab is all about garbage collection. In it, we will be using a few C++ features related to classes 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. */ }
};

You can either define the method within the class (as above, best for short methods), or in the cpp file, with something like

int SomeClass::foo() { /* or the body could be here. */ }

Observe that we do not have to put the static keyword here; it is already in the class declaration.

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. (I think I'm supposed to shush you here?)

The tricky thing with static fields is that they are declared in the class declaration in the header file, as usual, but they must be initialized in the 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. */ }
};

Counting Frame births and deaths

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.

What we want to do is count how many instances of the Frame class are in memory at any given point. This will require:

A static field of type int that holds the number of Frames currently in memory. This field should be initialized to 0, of course.
A (public) static method to get the number of Frames in memory.
A new line in the constructor that increments the static counter by one. So every time a new frame is created, we will keep the count correct.
A new destructor for the class that does nothing except decrement the static counter.

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 {
      if (remainder(n)(i) = 0) { ret := i; }
      else { ret := helper(i+1); }
    };
    ret := helper(2);
  };

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

Exercises:

(no features.txt entry necessary) Modify the Frame class as described above to count Frame births and deaths.
(ADD ENTRY TO features.txt) Add a line to the while loop in your main function from spl.ypp that prints out the number of Frames in memory after each statement is read and executed, in some nice way like "The number of frames in memory is ...".
(no features.txt entry necessary) Show me that you played around with this by recording a transcript of some tests in a file called ex3.txt. You can run whatever examples you like, but do enough so that (1) we see at least 10000 frames are in memory at some point, and then (2) the program runs out of memory and probably segfaults in disgrace. By "transcript" I just mean to copy the text from the terminal window where you run your interpreter on some example functions.

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 static field for a list of pointers, containing a pointer to every Frame that has been allocated so far.
A 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:

Add a static field of type list<Frame*> to the Frame class. Remember that you will essentially have to declare it twice: in the class declaration in frame.hpp, and then outside of it in frame.cpp. You will also have to include the standard header file with a line like #include <list>
Add a line to the constructor to add the current frame (using the this pointer) to the list. (You can use the push_back method; see here or here for more complete reference on the list class.) Note that you do NOT have to add anything to the destructor (we'll handle removing Frames from this list elsewhere). You can check that this much is working by comparing the count from part 1 to the size of the list.
Add a class field (NOT static) of type bool to indicate whether this frame has been marked. Add a line to the constructor to initialize this field to false.
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.
}
```
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 (iii) 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:

(ADD ENTRY TO features.txt) 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. Print out the Frame counts before and after each time the garbage collection occurs.

Automatically-triggered GC

Great! Now that you have garbage collection, you can run a series of fairly computationally-intensive operation 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 a bonus exercise, so I'm not going to step you through how to do it. But I'll allow a couple hints:

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.)

BONUS Exercise:

(no features.txt entry necessary, but UPDATE THE ENTRY from #4 so that the tester knows what's going on.) Implement automatically-triggered garbage collection as described above.