Polymorphism Metrics

Last updated: November 27, 2002

Polymorphism is a salient feature of object-oriented languages like Java. A polymorphic call in Java takes the form of an invokeVirtual or invokeInterface byte code. The target method of a polymorphic call depends on the run time type of the object receiving the call. In programs that do not employ inheritance, this target never changes and no call is truly polymorphic. The amount of polymorphism can therefore serve as a measurement of a program's object-orientedness.

Some of the metrics have two variants. In the first variant, we take into consideration the number of receiver types, in the second we use the number of different target methods. There are more receiver types than targets, since two different object types may inherit the same method from a common super class. Some optimization techniques, such as class hierarchy analysis, optimize call sites with a restricted number of targets. Others, such as inline caching [13], optimize call sites with a restricted number of receiver types.

Polymorphism Metrics

polymorphism.callSites.value: The total number of different call sites executed. This measurement includes monomorphic virtual method calls with a single receiver, but not static invokes.

polymorphism.receiverArity.bin: This is a bin metric. We show the percentage of all call sites that have one, two and more than two different receiver types.

polymorphism.targetArity.bin: As previous, but counting the number of different method targets instead of different receiver types. This metric is useful for compiler optimizations aimed at devirtualization: whenever a compiler can prove that a call site only has a single possible target, the call can be replaced by a static call or inlined. This metric is more useful than a simple average of number of targets per call site, which is easily distorted by one heavily polymorphic call site.

polymorphism.receiverPolyDensity.value: This metric shows the number of call sites that have two or more receiver types divided by the total number of call sites. It is simply the sum of the two last bins of polymorphism.receiverArity.bin.

polymorphism.targetPolyDensity.value: As previous, but counting the number of different method targets instead of different receiver types. It represents the proportion of call sites which cannot be devirtualized by any static compiler, since they have at least two targets during execution.

polymorphism.receiverBiasMissRate.value: This metric shows as a percentage how often a call is made with other than a call site's biased receiver type. This metric measures the effectiveness of the following optimization: for every call site, we count the frequency of each receiver type. Many call sites are biased towards one receiver type. The polymorphic call can be replaced by a test that compares the run time receiver with the bias type and jumps directly to the correct target method (which can be inlined). The metric shows the percentage of calls in which this test fails.

polymorphism.targetBiasMissRate.value: As previous but measuring bias to method target instead of receiver type.

polymorphism.receiverCacheMissRate.value: This metric shows as a percentage how often a call site switches between receiver types. In other words, how often is the receiver type different from the one that would be cached inline? Usually this metric is smaller than polymorphism.receiverBias.rate, but there are exceptions. For example, a single call site with two equally likely receiver types will have a polymorphism.receiverBias.rate of 50%, but if it alternates between those two receiver types, polymorphism.receiverCache.rate will be 100%. On the other hand, if it executes with one receiver type for half of the duration of the program and then switches to the other receiver type for the rest of the execution, polymorphism.receiverCache.rate will be close to 0%. This is the most dynamic measurement of polymorphism, and it represents the miss rate of a true inline cache.

polymorphism.targetCacheMissRate.value: As previous, but the cache compares with method target instead of receiver type. This measurement represents the miss rate of an idealized branch target buffer. It is always lower than the previous polymorphism.receiverCache.missRate, since targets can be equal for different receiver types.

Of these metrics, polymorphism.targetPolyDensity.value has the advantage that devirtualization studies often report this number. However, for a more dynamic measurement of run time polymorphic behavior, polymorphism.receiverCacheMissRate.value is preferred.