-
Andrew Appel has another scheme for reducing the run-time type information
requirement of accurate (non-conservative) collection. He does
two things (i) has the compiler generate tables that tell you types of
global and stack allocated variables, and (ii) has the compiler generate
a compact representation of all the types in the form of a type graph.
At heap. For instance, let the program have one type and one stack
allocated variable:
TYPE t = RECORD
val: INTEGER;
next: REF t;
END;
VAR v: REF t; (* v is a stack allocated variable
of type REF t *)
At garbage collection time, the collector looks at all the globals
and stack allocated variables (in this case only v). Since
it knows the types of stack allocated variables it knows that v points
to an object of type t. Since v is a garbage collection root,
it knows that what v points to is reachable; moreover, it also knows that
it is of type t. Now it uses that heap allocated object to continue
the collection: it knows that it is of type t AND its "next" field
is of type REF t. So it can follow the next field and mark that object
as reachable. So, it is able to find the types of all heap allocated
objects by TRAVERSING THE TYPE GRAPH WHILE DOING THE REACHABILITY ANALYSIS.
Note that the heap allocated objects do NOT need type descriptors.
Does this scheme work for weakly-typed languages? Does it work for
polymorphic languages? Give examples in each case to support your
argument.
-
One of the biggest complaints that (uninformed) people have about garbage
collection is that it is slower than explicit deallocation. However
in reality garbage collection isn't necessarily slower than explicit deallocation--as
a matter of fact, it may be faster in some instances. Argue when Scheme
I may be faster than Scheme II and vice versa. Consider the
following criteria: (i) time spent doing allocation; (ii) time spent doing
deallocation; (iii) paging behavior.
Scheme I: Explicit Deallocation: The memory management
system maintains a linked list of free memory locations (called a
"free list"). When a program makes an allocation request, it
searches the list for a memory block the right size.
If the block is larger than what the program requested, it breaks
up the block, returns one part to the program and puts the other
part on the free list. When a program deallocates a variable, it
puts the space for that variable on the free list. This is very similar
to how UNIX does it.
Scheme II: Copying Collection: All objects are compacted
together in memory. All free space is contiguous. When
a program makes an allocation request, the memory manager breaks
off a part of the free space and returns it to the user program.
If there is not enough free space available, the system does a garbage
collection (which presumably frees up some space) and then does the
allocation.
-
Let's suppose you want to use a garbage collector with a quicksort routine:
List *quicksort(List *l) {
if (l == NULL) return NULL;
else {
List *lt, *gt;
Value
pivot = l->head();
Pair p
= partition(l->tail(), pivot, lt, gt);
List *l1
= quicksort(lt);
List *l2
= quicksort(gt);
return
append(l1, pivot, l2);
}
}
In the above routine, partition takes a list and a pivot (the second
argument) and constructs two NEW lists which it puts in the two pass by
reference arguments to partition (in the above code these arguments are
lt and gt). After the call to partition, lt contains all the entries
in l that were smaller than the pivot and gt all the entries in l that
were greater than the pivot.
Assume that you have two accurate copying garbage collectors, one that
uses liveness information and one that doesn't use liveness information.
Would these two garbage collectors differ in their ability to reclaim garbage
for quicksort? Explain. Assume that the list being sorted does
not have any duplicates.
-
For each of the three principles of orthogonal persistence, explain the
problems that would occur if you compromised the principles.