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

However, since the bit pattern might really be meant asan integer, the object cannot be moved (which would change the possible integer), and somegarbage objects may not be reclaimed. Wentworth [1990] points out that such an integer may(coincidentally) point to the root of a huge garbage data structure, which therefore will not bereclaimed; so conservative collection will occasionally suffer from a disastrous space leak.Boehm [1993] describes several techniques for making these disasters unlikely: For example,if the collector ever finds an integer pointing to address X that is not a currently allocatedobject, it should blacklist that address so that the allocator will never allocate an object there.Boehm [1996] points out that even a conservative collector needs some amount of compilerassistance: If a derived pointer can point outside the bounds of an object, then its base pointermust be kept live as long as the derived pointer exists.Page 481 discusses some of the literature on improving the cache performance of garbagecollected systems.Cohen [1981] comprehensively surveys the first two decades of garbagecollection research;Wilson [1997] describes and discusses more recent work.

Jones and Lins [1996] offer acomprehensive textbook on garbage collection.EXERCISES•*13.1 Analyze the cost of mark-sweep versus copying collection. Assume that everyrecord is exactly two words long, and every field is a pointer. Some pointers may pointoutside the collectible heap, and these are to be left unchanged.234a. Analyze Algorithm 13.6 to estimate c1, the cost (in instructions per reachableword) of depth-first marking.b. Analyze Algorithm 13.3 to estimate c2, the cost (in instructions per word in theheap) of sweeping.c.

Analyze Algorithm 13.9 to estimate c3, the cost per reachable word of copyingcollection.d. There is some ratio γ so that with H = γR the cost of copying collection equalsthe cost of mark-sweep collection. Find γ.•••e. For H > γR, which is cheaper, mark-sweep or copying collection?13.2 Run Algorithm 13.6 (pointer reversal) on the heap of Figure 13.1. Show the stateof the heap; the done flags; and variables t, x, and y at the time the node containing 59is first marked.*13.3 Assume main calls f with callee-save registers all containing 0.

Then f saves thecallee-save registers it is going to use; puts pointers into some callee-save registers,integers into others, and leaves the rest untouched; and then it calls g. Now g savessome of the callee-save registers, puts some pointers and integers into them, and callsalloc, which starts a garbage collection.a. Write functions f and g matching this description.b. Illustrate the pointer maps of functions f and g.c. Show the steps that the collector takes to recover the exact locations of all thepointers.**13.4 Every object in the Java language supports a hashCode() method that returns a"hash code" for that object.

Hash codes need not be unique ± different objects canreturn the same hash code − but each object must return the same hash code everytime it is called, and two objects selected at random should have only a small chanceof having the same hash code.The Java language specification says that "This is typically implemented byconverting the address of the object to an integer, but this implementation technique isnot required by the Java language."Explain the problem in implementing hashCode() this way in a Java system withcopying garbage collection, and propose a solution.235Chapter 14: Object-Oriented LanguagesOVERVIEWob-ject: to feel distaste for somethingWebster's DictionaryAn important characteristic of object-oriented languages is the notion of extension orinheritance.

If some program context (such as the formal parameter of a function or method)expects an object that supports methods m1, m2, m3, then it will also accept an object thatsupports m1, m2, m3, m4.14.1 CLASS EXTENSIONProgram 14.1 illustrates the use of class extension in Java. Every Vehicle is an Object;everyCar is a Vehicle; thus every Car is also an Object.

Every Vehicle (and thus every Car andTruck) has an integer position field and a move method.PROGRAM 14.1: An object-oriented program.class Vehicle {int position;void move (int x) { position = position + x; }}class Car extends Vehicle{int passengers;void await(Vehicle v) {if (v.position < position)v.move(position - v.position);elsethis.move(10);}}class Truck extends Vehicle{void move(int x) {if (x <= 55) { position = position + x; }}}class Main{public static void main(String args[]) {Truck t = new Truck();Car c = new Car();Vehicle v = c;c.passengers = 2;c.move(60);v.move(70);c.await(t);}}In addition, a Car has an integer passengers field and an await method.

The variables inscope on entry to await arepassengers because it is a field of Car,position because it is (implicitly) a field of Car,236v because it is a formal parameter of await,this because it is (implicitly) a formal parameter of await.At the call to c.await(t), the truck t is bound to the formal parameter v of the awaitmethod. Then when v.move is called, this activates the Truck_move method body, notVehicle_move.We use the notation A_m to indicate a method instance m declared within aclass A.

This is notpart of the Java syntax, it is just for use in discussing the semantics of Java programs. Eachdifferent declaration of a method is a different method instance. Two different methodinstances could have the same method name if, for example, one overrides the other.14.2 SINGLE INHERITANCE OF DATA FIELDSTo evaluate the expression v.position, where v belongs to class Vehicle, the compiler mustgenerate code to fetch the field position from the object (record) that v points to.This seems simple enough: The environment entry for variable v contains (among otherthings) a pointer to the type (class) description of Vehicle; this has a list of fields and theiroffsets. But at run time the variable v could also contain a pointer to a Car or Truck; wherewill the position field be in a Car or Truck object?Single inheritance For single-inheritance languages, in which each class extends just oneparent class, the simple technique of prefixing works well.

Where B extends A, those fields ofB that are inherited from A are laid out in a B record at the beginning, in the same order theyappear in A records. Fields of B not inherited from A are placed afterward, as shown in Figure14.2.Figure 14.2: Single inheritance of data fields.METHODSA method instance is compiled much like a function: It turns into machine code that resides ata particular address in the instruction space. Let us say, for example, that the method instanceTruck_move has an entry point at machine-code label Truck_move. In the semantic analysisphase of the compiler, each variable's environment entry contains a pointer to its classdescriptor; each class descriptor contains a pointer to its parent class, and also a list of methodinstances; and each method instance has a machine-code label.Static methods Some object-oriented languages allow some methods to be declared static.The machine code that executes when c.f() is called depends on the type of the variable c,not the type of the object that c holds.

To compile a method-call of the form c.f(), thecompiler finds the class of c; let us suppose it is class C. Then it searches in class C for amethod f; suppose none is found. Then it searches the parent class of C, class B, for a methodf; then the parent class of B; and so on. Suppose in some ancestor class A it finds a staticmethod f; then it can compile a function call to label A_f.237Dynamic methods This technique will not work for dynamic methods. If method f in A is adynamic method, then it might be overridden in some class D which is a subclass of C (seeFigure 14.3).

But there is no way to tell at compile time if the variable c is pointing to anobject of class D (in which case D_f should be called) or class C (in which case A_f should becalled).Figure 14.3: Class descriptors for dynamic method lookup.To solve this problem, the class descriptor must contain a vector with a method instance foreach (nonstatic) method name. When class B inherits from A, the method table starts withentries for all method names known to A, and then continues with new methods declared by B.This is very much like the arrangement of fields in objects with inheritance.Figure 14.3 shows what happens when class D overrides method f.

Although the entry for f isat the beginning of D's method table, as it is also at the beginning of the ancestor class A'smethod table, it points to a different method-instance label because f has been overridden.To execute c.f(), where f is a dynamic method, the compiled code must execute theseinstructions:1. Fetch the class descriptor d at offset 0 from object c.2.

Fetch the method-instance pointer p from the (constant) f offset of d.3. Jump to address p, saving return address (that is, call p).14.3 MULTIPLE INHERITANCEIn languages that permit a class D to extend several parent classes A, B, C (that is, where A isnot a subclass of B, or vice versa), finding field offsets and method instances is more difficult.It is impossible to put all the A fields at the beginning of D and to put all the B fields at thebeginning of D.Global graph coloring One solution to this problem is to statically analyze all classes atonce, finding some offset for each field name that can be used in every record containing thatfield.

We can model this as a graph-coloring problem: There is a node for each distinct fieldname, and an edge for any two fields which coexist (perhaps by inheritance) in the sameclass.[1] The offsets 0, 1, 2;… are the colors. Figure 14.4 shows an example.Figure 14.4: Multiple inheritance of data fields.238The problem with this approach is that it leaves empty slots in the middle of objects, since itcannot always color the N fields of each class with colors with the first N colors. To eliminatethe empty slots in objects, we pack the fields of each object and have the class descriptor tellwhere each field is.

Figure 14.5 shows an example. We have done graph coloring on all thefield names, as before, but now the "colors" are not the offsets of those fields within theobjects but within the descriptors. To fetch a field a of object x, we fetch the a-word from x'sdescriptor; this word contains a small integer telling the position of the actual a data within x.Figure 14.5: Field offsets in descriptors for multiple inheritance.In this scheme, class descriptors have empty slots, but the objects do not; this is acceptablebecause a system with millions of objects is likely to have only dozens of class descriptors.But each data fetch (or store) requires three instructions instead of one:1.

Fetch the descriptor pointer from the object.2. Fetch the field-offset value from the descriptor.3. Fetch (or store) the data at the appropriate offset in the object.In practice, it is likely that other operations on the object will have fetched the descriptorpointer already, and multiple operations on the same field (e.g., fetch then store) won't need torefetch the offset from the descriptor; commonsubexpression elimination can remove much ofthis redundant overhead.Method lookup Finding method instances in a language with multiple inheritance is just ascomplicated as finding field offsets. The global graph-coloring approach works well: Themethod names can be mixed with the field names to form nodes of a large interference graph.Descriptor entries for fields give locations within the objects; descriptor entries for methodsgive machine-code addresses of method instances.Problems with dynamic linking Any global approach suffers from the problem that thecoloring (and layout of class descriptors) can be done only at link time; the job is certainlywithin the capability of a special-purpose linker.239However, many object-oriented systems have the capability to load new classes into a runningsystem; these classes may be extensions (subclasses) of classes already in use.