Lessons Learned From a Generational GC in Racket

I recently wrote a second garbage collector in racket, using the plai gc2 module, and I would recommend it over the older gc module. It allows for use of more racket functions, provides for creation of randomized test programs which use the subset of racket the plai gc module supports, and makes it possible to unit test your program.

I found that it was fairly easy to implement the overarching points of collection, but this project definitely drilled home the insanely stateful nature of a collection system. There tended to be a need for information to be shared promiscuously. Testing was difficult and generally took the form of using automated tests to detect a problem, and then time-consumingly adding in print-debugging and hooks to trace it down to the broken system. The closure environments and interesting pointers were the most painful to debug.

Chapters 13-19

Chapter 13: Concurrency Preliminaries

13.1 Hardwarse

Chapters 9-12

9-12

Chapter 9: Generational Garbage Collection

Prologue

Tracing collectors have best case when heap is mostly garbage, but long-lived objects tend to exhibit pathologically bad behavior for copying and mark-sweep

• Ex: Mark-sweep has dense prefix near bottom of heap, copying moves data unnecessarily
  

Solution: Segment the heap into generations and collect the youngest generation(nursery) most frequently. Tenure into older generations after surviving a number of sweeps.

• Most of the time use copying
  

• Has good mark/cons ratio, so should be faster for young generation
  

• Can tune pause times / frequency of pauses by altering nursery size
  

Only improves average-case time. Worst case still needs to sweep whole heap.

Racket GC Tests.

To anyone doing the racket garbage collector exercises, this is the assignment page for a class doing the exact exercise. It specifies tests that must pass as well; I found this link while trying to think up tests in the face of a lack of working libraries(equals?, map, filter, fold) and a suspicion of a lack of tail call recursion.

http://www.eecs.northwestern.edu/~robby/courses/321-2014-winter/hw7.html

I recommend the assignment as it imposes upon the student how elementary mark-sweep really is.

Notes on Chapters 5-8 of Garbage Collection Handbook

Chapter 5: Reference Counting
- Invariant: An object is alive iff the number of references to it are greater than 0
- Each object has a reference count
- When references mutated, we increment or decrement the reference count. When it reaches 0, it is freed.
- Required write barrier. 
- Mutator uses barriers to keep state of object graph consistent when changes can be non-atomic to the GC

1.1 Advantages + Disadvantages:
Advantages:
- Costs are spread throughout computation time
- Operates well without much headroom
- Potentially free memory immediately
- Locality may be not worse than actual program since only actively used or modified objects referenced
- Does not need runtime assistance, doesn’t need to know roots
- Heavily used today
- Available in C++ through “smart pointers” or pointers with special logic

Readings of chapters 1-4

Chapter 1: Intro
- First GC demo was a mistake. Had exhausted all memory on IBM machine, and GC printed out statistics of memory slowly and used up rest of demo’s time.

- Runtimes allow allocation on heap rather than stack or static allocation.
-- Needed for factories, closures/returned functions

1.1 Explicit deallocation
- Heap memory can be explicitly deallocated like in C.
- Runs risk of programmer error. 
- Two kinds of errors:
— Pointer to deallocated region = dangling pointer
—- Can be fixed with fat pointers, but not performant so only used for debugging
—  Region with no pointers but is never deallocated = memory leak
— Incorrect deallocation can cause both problems
- Difficult for concurrent access
- Solutions: Allocation from a pool which is freed as a whole, “ownership” semantics that prevent sharing and passing by reference ex: smart pointers, unique_ptr and shared_ptr
— Do all libraries used by the programmer use the same approach? Does the API require mixing styles?
- “Liveness is a global property but freeing is a local choice”

First Post

I figured that I would introduce myself and this blog before filling it with content.

I am a CS student at RIT in my third year here. I've got a light background in backend web development, with a fair amount of experience in building distributed/concurrent systems. My focuses tend to be on functional programming, and on compiler implementation strategies. I've worked here as a student lab instructor for a semester and I've spent 7 months on co-op at EnerNOC, the place where I am now working part-time. 

This blog is my journal of my independent study in garbage collection. I'll be working under Professor Fluet; we hope to cover the classic garbage collection handbook and to create a number of small implementations of collectors around the racket dialect of scheme. I hope to culminate the class with useful contributions to Mlton's garbage collector, which Professor Fluet maintains.

I will be using this blog to describe the readings and to document the experience of the class. Our custom syllabus for the course is below: