3.16 Garbage Collection

Complete this assignment with Team Two.

You must submit this in an archive named "wgc.zip". This archive must contain a folder named "wgc". This folder must contain all the files specified below. You must attach "wgc.zip" to an email whose subject is "BYU - Fall 2010 - CS 330 - wgc" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 11/16. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.

You must submit this in a file named "wgc.pdf".

3.16.1 Mark & Sweep and Large Objects

We have discussed why, at least on paper, mark-and-sweep is an inferior garbage collection strategy for languages (such as ones that do not expose pointer operations) that permit implementations to move data in memory. Yet even for such languages, most memory managers use a mark-and-sweep strategy for their large-object space. Give one reason why mark-and-sweep might be preferable on such objects.

State two standard objections to mark-and-sweep, and explain why they don’t apply in this context. For each reason, first state the objection, then explain why it doesn’t apply.

3.16.2 Type Tag Placement

Suppose we have multiple kinds of data of different sizes. In typical heap representations, the type tag is always at the first address (i.e., at offset 0) that represents a value. Should it matter where the tag resides? For instance, why not put the tag at the last address rather than the first? (The more concrete you are, the more brief you can be.)

3.16.3 Intergenerational Pointers

A generational garbage collector naturally handles references from newer objects (those allocated more recently) to older ones. A major challenge is keeping track of references that go the other way: from old objects to new. What in the design of a copying generational collector makes it straightforward for the collector to handle references from new to old, rather than vice versa?

Distinguish between variable mutation and value mutation. In variable mutation, we change the value held by a variable itself. In value mutation, the variable still refers to the same object; it’s the content of the object that changes. (For example, set! in Racket implements variable mutation, while vector-set! implements value mutation.) Which of these does a generational collector need to track specially? For each one, state whether it is or isn’t tracked, with a brief justification for why or why not.

3.16.4 Application

In 850 words or less, describe if and how your knowledge of garbage collection algorithms will help you in your future programming practice. Good answers might discuss how this concept can be applied in interesting programming environments or how knowledge of its subtleties clarifies or improves existing practices, techniques, tools, etc.