GENERATIONAL COLLECTION

In many programs, newly created objects are likely to die soon; but an object that is still reachable after many collections will probably survive for many collections more. Therefore the collector should concentrate its effort on the "young" data, where there is a higher proportion of garbage. We divide the heap into generations, with the youngest objects in generation G₀; every object in generation G₁ is older than any object in G₀; everything in G₂ is older than anything in G₁, and so on. To collect (by mark-and-sweep or by copying) just G₀, just start from the roots and do either depth-first marking or breadth-first copying (or semidepth-first copying). But now the roots are not just program variables: They include any pointer within G₁, G₂,… that points into G₀. If there are too many of these, then processing the roots will take longer than the traversal of reachable objects within G₀! Fortunately, it is rare for an older object to point to a much younger object. In many common coding styles, when an object a is created its fields are immediately initialized; for example, they might be made to point to b and c. But b and c already exist; they are older than a. So we have a newer object pointing to an older object. The only way that an older object b could point to a newer object a is if some field of b is updated long after b is created; this turns out to be rare. To avoid searching all of G₁, G₂,… for roots of G₀, we make the compiled program remember where there are pointers from old objects to new ones. There are several ways of remembering:

• Remembered list: The compiler generates code, after each update store of the form b. f_i ← a, to put b into a vector of updated objects. Then, at each garbage collection, the collector scans the remembered list looking for old objects b that point into G₀.

• Remembered set: Like the remembered list, but uses a bit within object b to record that b is already in the vector. Then the code generated by the compiler can check this bit to avoid duplicate references to b in the vector.
• Card marking: Divide memory into logical "cards" of size 2^k bytes. An object can occupy part of a card or can start in the middle of one card and continue onto the next. Whenever address b is updated, the card containing that address is marked. There is an array of bytes that serve as marks; the byte index can be found by shifting address b right by k bits.
• Page marking: This is like card marking, but if 2^k is the page size, then the computer's virtual memory system can be used instead of extra instructions generated by the compiler. Updating an old generation sets a dirty bit for that page. If the operating system does not make dirty bits available to user programs, then the user program can implement this by write-protecting the page and asking the operating system to refer protection violations to a usermode fault handler that records the dirtiness and unprotects the page.

When a garbage collection begins, the remembered set tells which objects (or cards, or pages) of the old generation can possibly contain pointers into G₀; these are scanned for roots. Algorithm 13.3 or 13.9 can be used to collect G₀: "heap" or "from-space" means G₀, "to-space" means a new area big enough to hold the reachable objects in G₀, and "roots" include program variables and the remembered set. Pointers to older generations are left unchanged: The marking algorithm does not mark old-generation records, and the copying algorithm copies them verbatim without forwarding them. After several collections of G₀, generation G₁ may have accumulated a significant amount of garbage that should be collected. Since G₀ may contain many pointers into G₁, it is best to collect G₀ and G₁ together. As before, the remembered set must be scanned for roots contained in G₂, G₃;…. Even more rarely, G₂ will be collected, and so on. Each older generation should be exponentially bigger than the previous one. If G₀ is half a megabyte, then G₁ should be two megabytes, G₂ should be eight megabytes, and so on. An object should be promoted from G_i to G_i+1 when it survives two or three collections of G_i. Cost of generational collection Without detailed empirical information about the distribution of object lifetimes, we cannot analyze the behavior of generational collection. In practice, however, it is common for the youngest generation to be less than 10% live data. With a copying collector, this means that H / R is 10 in this generation, so that the amortized cost per word reclaimed is c₃ R / (10R − R), or about 1 instruction. If the amount of reachable data in G₀ is about 50 to 100 kilobytes, then the amount of space "wasted" by having H = 10R in the youngest generation is about a megabyte. In a 50-megabyte multigeneration system, this is a small space cost. Collecting the older generations can be more expensive. To avoid using too much space, a smaller H / R ratio can be used for older generations. This increases the time cost of an older-generation collection, but these are sufficiently rare that the overall amortized time cost is still good.

Maintaining the remembered set also takes time, approximately 10 instructions per pointer update to enter an object into the remembered set and then process that entry in the remembered set. If the program does many more updates than fresh allocations, then generational collection may be more expensive than nongenerational collection.

JaVa	Previous    Next