Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 74

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 74)

It uses draw’s offset,which is 0 relative to the method vector pointer, to obtain a pointer to thedesired implementation of draw. It uses that code pointer in a standard procedure call, with one twist—it passes RightCorner’s or pointer as the implicitfirst parameter to draw. Because it located draw from RightCorner’s or,292 CHAPTER 6 The Procedure Abstractionwhich contains a pointer to ColorPoint’s class methods vector, the codesequence locates the proper implementation of draw. If the invocation hadbeen SimplePoint.draw, the same process would have found Point’smethod vector pointer and called Point.draw.The example assumes that each class has a complete method vector.

Thus,the slot for move in ColorPoint’s method vector points to Point.movewhile the slot for draw points to ColorPoint.draw. This scheme produces the desired result—an object of class x invokes the implementationof a method that is visible inside the definition for class x. The alternativescheme would represent only ColorPoint’s locally defined methods in itsclass method vector, and would locate an inherited method by chasing orsup the superclass chain in a manner analogous to access links for lexicalscoping and ars.Object-Record Layout"Implementation" might be a compiler, aninterpreter, or a JIT. The layout problem is thesame.One subtle point in the example is that an implementation must maintainconsistent offsets, by name, up and down the superclass hierarchy. Fields,such as x and y, must appear at the same offset in an or of class Point andColorPoint for a method such as move to operate correctly on ors of eitherits class or its superclasses.

For the same reason, methods must appear at thesame offsets in the method vectors of related classes.Without inheritance, the compiler can assign offsets in arbitrary order to theclass’ fields and methods. It compiles those offsets directly into the code.The code uses the receiver’s pointer (e.g. this) and the offsets to locate anydesired field in the or or any method in the method vector.With single inheritance, or layout is straightforward. Since each class hasonly one direct superclass, the compiler appends the new fields to the endof the superclass or layout, extending the or layout. This approach, calledprefixing, ensures consistent offsets up and down the superclass hierarchy.When an object is cast to one of its superclasses, the fields in the or are intheir expected locations.

The ors in Figure 6.7 follow this scheme.In a language with a closed class structure, object-record layout can be doneat compile time, as soon as all the superclasses are known. In a languagewith an open class structure, object-record layout must be done between thetime when the superclass structure is known and the time when ors are allocated. If the class structure is unknown at compile time but cannot change atruntime, these issues can be resolved at linktime or at the start of execution.If the class structure can change at runtime, as in either Java or Smalltalk,then the runtime environment must be prepared to adjust object layouts andthe class hierarchy.6.3 Name Spaces 293nnIf classes change infrequently, the overhead for adjusting object-recordlayouts can be small.

The runtime environment, either an interpreter ora JIT and an interpreter, can compute object record layouts and buildmethod vectors for each affected class when the class structure changes.If classes change often, the compiler must still compute object-recordlayouts and adjust them. However, it may be more efficient for theimplementation to use incomplete method vectors and search ratherthan rebuilding class method vectors at each change. (See the nextsubsection.)In Java, for example, classes only change whenthe class loader runs. Thus, the class loader couldtrigger the rebuilding process.As a final issue, consider what happens if the language allows changes to thestructure of a class that has instantiated objects.

Adding a field or a method toa class with instantiated objects necessitates visiting those objects, buildingthem new ors, and connecting those ors back into the runtime environmentin a seamless way. (Typically, the latter requirement requires an extra levelof indirection on references to ors.) To avoid these complications, mostlanguages forbid changes to classes that already have instantiated objects.Static versus Dynamic DispatchThe runtime structures shown in Figure 6.7 suggest that every method callrequires one or more load operations to locate the method’s implementation. In a language with a closed class structure, the compiler can avoid thisoverhead for most calls. In c++, for example, the compiler can resolve anymethod to a concrete implementation at compile time, unless the methodis declared as a virtual method—meaning, essentially, that the programmerwants to locate the implementation relative to the receiver’s class.With a virtual method, dispatch is done through the appropriate methodvector.

The compiler emits code to locate the method’s implementation atruntime using the object’s method vector, a process called dynamic dispatch.If, however, the c++ compiler can prove that some virtual method call has aknown invariant receiver class, it can generate a direct call, sometimes calledstatic dispatch.Languages with open class structures may need to rely on dynamic dispatch.If the class structure can change at runtime, the compiler cannot resolvemethod names to implementations; instead, it must defer this process toruntime.

The techniques used to address this problem range from recomputing method vectors at each change in the class hierarchy to runtime nameresolution and search in the class hierarchy.nIf the class hierarchy changes infrequently, the implementation maysimply rebuild method vectors for the affected classes after eachchange. In this scheme, the runtime system must traverse the superclassDispatchThe process of calling a method is often calleddispatch, a term derived from the messagepassing model of OOLs such as Smalltalk.294 CHAPTER 6 The Procedure AbstractionMETHOD CACHESTo support an open class hierarchy, the compiler may need to producea search key for each method name and retain a mapping of keys toimplementations that it can search at runtime. The map from methodname to search key can be simple—using the method name or a hashindex for that name—or it can be complex—assigning each method namean integer from a compact set using some link-time mechanism.

In eithercase, the compiler must include tables that can be searched at runtime tolocate the implementation of a method in the most recent ancestor of thereceiver’s class.To improve method lookup in this environment, the runtime system canimplement a method cache—a software analog of the hardware data cachefound in most processors. The method cache has a small number of entries,say 1000.

Each cache entry consists of a key, a class, and a pointer to amethod implementation. A dynamic dispatch begins with a lookup in themethod cache; if it finds an entry with the receiver’s class and methodkey, it returns the cached method pointer. If the lookup fails, the dispatchperforms a complete search up the superclass chain, starting with thereceiver’s class. It caches the result that it finds and returns the methodpointer.Of course, creating a new entry may force eviction of some other cacheentry. Standard cache replacement policies, such as least recently usedor round robin, can select the method to evict.

Larger caches retainmore information, but require more memory and may take longer tosearch. When the class structure changes, the implementation can clearthe method cache to prevent incorrect results on future lookups.To capture type locality at individual calls, some implementations use aninline method cache, a single entry cache located at the actual call site. Thecache stores the receiver’s class and the method pointer from the lastinvocation at that site.

If the current receiver class matches the previousreceiver class, the call uses the cached method pointer. A change to theclass hierarchy must invalidate the cache, either by changing the class’ tagor by overwriting the class tags at each inline cache. If the current classdoes not match the cached class, a full lookup is used, and that lookupwrites its results into the inline cache.nhierarchy to locate method implementations and build subclass methodvectors.If the class hierarchy changes often, the implementor may choose tokeep incomplete method vectors in each class—record just the localmethods.

In this scheme, a call to a superclass method triggers aruntime search in the class hierarchy for the first method of that name.6.3 Name Spaces 295Either of these schemes requires that the language runtime retain lookuptables of method names—either source level names or search keys derivedfrom those names. Each class needs a small dictionary in its or. Runtimename resolution looks up the method name in the dictionaries through thehierarchy, in a manner analogous to the chain of symbol tables described inSection 5.5.3.ool implementations try to reduce the cost of dynamic dispatch through oneof two general strategies. They can perform analysis to prove that a givenmethod invocation always uses a receiver of the same known class, in whichcase they can replace dynamic dispatch with static dispatch.

Характеристики

Список файлов учебной работы