A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 46

Therefore, we can compute the amortized cost of collection by dividing the timespent collecting by the amount of garbage reclaimed. That is, for every word that thecompiled program allocates, there is an eventual garbage-collection cost of217If R is close to H, this cost becomes very large: Each garbage collection reclaims only a fewwords of garbage. If H is much larger than R, then the cost per allocated word isapproximately c2, or about 3 instructions of garbage-collection cost per word allocated.The garbage collector can measure H (the heap size) and H − R (the freelist size) directly.After a collection, if R/H is larger than 0.5 (or some other criterion), the collector shouldincrease H by asking the operating system for more memory. Then the cost per allocated wordwill be approximately c1 + 2c2, or perhaps 16 instructions per word.Using an explicit stack The DFS algorithm is recursive, and the maximum depth of itsrecursion is as long as the longest path in the graph of reachable data.

There could be a path oflength H in the worst case, meaning that the stack of activation records would be larger thanthe entire heap!Figure 13.4: Mark-and-sweep collection.To attack this problem, we use an explicit stack (instead of recursion), as in Algorithm 13.5.Now the stack could still grow to size H, but at least this is H words and not H activationrecords. Still, it is unacceptable to require auxiliary stack memory as large as the heap beingcollected.ALGORITHM 13.5: Depth-first search using an explicit stack.function DFS(x)if x is a pointer and record x is not markedmark xt 1stack[t] ← xwhile t > 0x ← stack[t]; t ← t - 1for each field fi of record x218if x.

fi is a pointer and record x. fi is not markedmark x. fit ← t + 1; stack[t] ← x. fiPointer reversal After the contents of field x. fi have been pushed on the stack, Algorithm13.5 will never again look the original location x. fi. This means we can use x. fi to store oneelement of the stack itself! This all-too-clever idea is called pointer reversal, because x. fi willbe made to point back to the record from which x was reached.

Then, as the stack is popped,the field x. fi will be restored to its original value.Algorithm 13.6 requires a field in each record called done, which indicates how many fieldsin that record have been processed. This takes only a few bits per record (and it can also serveas the mark field).ALGORITHM 13.6: Depth-first search using pointer reversal.function DFS(x)if x is a pointer and record x is not markedt ← nilmark x; done[x] 0while truei done[x]if i < # of fields in record xy ← x. fiif y is a pointer and record y is not markedx. fi ← t; t ← x; x ← ymark x; done[x] 0elsedone[x] ← i + 1elsey ← x; x ← tif x = nil then returni ← done[x]t ← x. fi; x.

fi ← ydone[x] ← i + 1The variable t serves as the top of the stack; every record x on the stack is already marked,and if i = done[x], then x. fi is the "stack link" to the next node down. When popping the stack,x. fi is restored to its original value.An array of freelists The sweep phase is the same no matter which marking algorithm isused: It just puts the unmarked records on the freelist, and unmarks the marked records. But ifrecords are of many different sizes, a simple linked list will not be very efficient for theallocator. When allocating a record of size n, it may have to search a long way down the listfor a free block of that size.A good solution is to have an array of several freelists, so that freelist[i] is a linked list of allrecords of size i.

The program can allocate a node of size i just by taking the head offreelist[i]; the sweep phase of the collector can put each node of size j at the head of freelist[j].219If the program attempts to allocate from an empty freelist[i], it can try to grab a larger recordfrom freelist[j] (for j > i) and split it (putting the unused portion back on freelist[j − i]).

If thisfails, it is time to call the garbage collector to replenish the freelists.Fragmentation It can happen that the program wants to allocate a record of size n, and thereare many free records smaller than n but none of the right size. This is called externalfragmentation. On the other hand, internal fragmentation occurs when the program uses atoo-large record without splitting it, so that the unused memory is inside the record instead ofoutside.13.2 REFERENCE COUNTSOne day a student came to Moon and said: "I understand how to make a better garbagecollector.

We must keep a reference count of the pointers to each cons."Moon patiently told the student the following story:"One day a student came to Moon and said: ‘I understand how to make a better garbagecollector …'"(MIT-AI koan by Danny Hillis)Mark-sweep collection identifies the garbage by first finding out what is reachable. Instead, itcan be done directly by keeping track of how many pointers point to each record: This is thereference count of the record, and it is stored with each record.The compiler emits extra instructions so that whenever p is stored into x.

fi, the referencecount of p is incremented, and the reference count of what x. fi previously pointed to isdecremented. If the decremented reference count of some record r reaches zero, then r is puton the freelist and all the other records that r points to have their reference countsdecremented.Instead of decrementing the counts of r. fi when r is put on the freelist, it is better to do this"recursive" decrementing when r is removed from the freelist, for two reasons:1. It breaks up the "recursive decrementing" work into shorter pieces, so that the programcan run more smoothly (this is important only for interactive or real-time programs).2.

The compiler must emit code (at each decrement) to check whether the count hasreached zero and put the record on the freelist, but the recursive decrementing will bedone only in one place, in the allocator.Reference counting seems simple and attractive. But there are two major problems:1. Cycles of garbage cannot be reclaimed. In Figure 13.1, for example, there is a loop oflist cells (whose keys are 7 and 9) that are not reachable from program variables; buteach has a reference count of 1.2. Incrementing the reference counts is very expensive indeed.

In place of the singlemachine instruction x. fi ← p, the program must execute220A naive reference counter will increment and decrement the counts on every assignment to aprogram variable. Because this would be extremely expensive, many of the increments anddecrements are eliminated using dataflow analysis: As a pointer value is fetched and thenpropagated through local variables, the compiler can aggregate the many changes in the countto a single increment, or (if the net change is zero) no extra instructions at all. However, evenwith this technique there are many ref-count increments and decrements that remain, and theircost is very high.There are two possible solutions to the "cycles" problem. The first is simply to require theprogrammer to explicitly break all cycles when she is done with a data structure.

This is lessannoying than putting explicit free calls (as would be necessary without any garbagecollection at all), but it is hardly elegant. The other solution is to combine reference counting(for eager and nondisruptive reclamation of garbage) with an occasional mark-sweepcollection (to reclaim the cycles).On the whole, the problems with reference counting outweigh its advantages, and it is rarelyused for automatic storage management in programming language environments.13.3 COPYING COLLECTIONThe reachable part of the heap is a directed graph, with records as nodes, and pointers asedges, and program variables as roots.

Copying garbage collection traverses this graph (in apart of the heap called from-space), building an isomorphic copy in a fresh area of the heap(called to-space). The to-space copy is compact, occupying contiguous memory withoutfragmentation (that is, without free records interspersed with the reachable data). The rootsare made to point at the to-space copy; then the entire from-space (garbage, plus thepreviously reachable graph) is unreachable.Figure 13.7 illustrates the situation before and after a copying collection. Before thecollection, the from-space is full of reachable nodes and garbage; there is no place left toallocate, since next has reached limit.

After the collection, the area of to-space betweennext and limit is available for the compiled program to allocate new records. Because thenew-allocation area is contiguous, allocating a new record of size n into pointer p is very easy:Just copy next to p, and increment next by n. Copying collection does not have afragmentation problem.221Figure 13.7: Copying collection.Eventually, the program will allocate enough that next reaches limit; then another garbagecollection is needed.

The roles of from-space and to-space are swapped, and the reachabledata are again copied.Initiating a collection To start a new collection, the pointer next is initialized to point at thebeginning of to-space; as each reachable record in from-space is found, it is copied to to-spaceat position next, and next incremented by the size of the record.Forwarding The basic operation of copying collection is forwarding a pointer; that is, given apointer p that points to from-space, make p point to to-space (Algorithm 13.8).ALGORITHM 13.8: Forwarding a pointer.function Forward(p)if p points to from-spacethen if p. f1 points to to-spacethen return p.

f1else for each field fi of pnext. fi ← p. fip. f1 ← nextnext ← next+ size of record preturn p. f1else return pThere are three cases:1. If p points to a from-space record that has already been copied, then p. f1 is a specialforwarding pointer that indicates where the copy is. The forwarding pointer can beidentified just by the fact that it points within the to-space, as no ordinary from-spacefield could point there.2. If p points to a from-space record that has not yet been copied, then it is copied tolocation next; and the forwarding pointer is installed into p. f1. It's all right tooverwrite the f1 field of the old record, because all the data have already been copiedto the to-space at next.3. If p is not a pointer at all, or if it points outside from-space (to a record outside thegarbage-collected arena, or to to-space), then forwarding p does nothing.222Cheney's algorithm The simplest algorithm for copying collection uses breadth-first searchto traverse the reachable data (Algorithm 13.9, illustrated in Figure 13.10).