### <== Previous | Contents | Next ==>

## How Adaptive Optimization Works

The basic concepts involved in how the Strongtalk VM works have been published or discussed publically in the past, and are discussed here. The basic idea is very simple: a two-phase execution system is used, with the first phase determining which code is frequently executed. The second, optimizing phase is invoked only for frequently executed code.

This takes advantage of a well-known property of programs: most programs spend the vast majority of their time executing a very small portion of their code. By only optimizing performance critical code, extensive inlining and optimization can be done, which would cause too much overhead in code space and compilation time if it were done on the whole program.

### The first step: Instrumented Interpretation

Just as in other Smalltalks, source code is compiled into a portable byte-code format that is kept in the image. When the code is first executed, it is interpreted, as in an interpreted Smalltalk. But the similarities end there. The interpreted code is instrumented in several ways, to determine the execution characteristics of each section of code. This is done with two measurement techiques:

- Invocation Counters: Counters are used to keep track of how many times each method is called, and how many times each loop iterates. This is used to determine how performance-critical each section of code is.

- Inline-caching: Each message send is instrumented to determine what methods are invoked by that send. There are three important cases that are distinguished:

  - Monomorphic Sends: A monomorphic send is one that only ever invoked for one receiver class during execution. This does not mean that it can't invoke others in the future- it only means that up to this point, the send has only been invoked with a single receiver class (perhaps many times). The VM keeps track of this class using a standard inline-cache. The vast majority (over 90%) of dynamic sends fall into this category.

  - Slightly Polymorphic Sends: A slighly polymorphic send is one that invokes one of a very small number of receiver classes, but more than just one. The VM keeps track of the small set of receiver classes using a polymorphic inline-cache (PIC).

  - Megamorphic Sends: A megamorphic send is one that has many different receiver classes, too many to keep track of. Very few sends fall into this category.

The smaller the number of receiver classes invoked by a send (called the arity), the easier it is to optimize it using inlining in the second phase. An important associated technique called customization is used to help reduce the arity of sends, so that more of them can be optimized. Customization works by making copies of performance-critical methods for each concrete subclass, just as if inheritance were treated as a form of code copying. Many sends can become monomorphic after customization. For example, a self-send in a superclass method would not ordinarily be monomorphic, because self can be any one of a number of different subclasses. But if a copy of the method is made for every subclass, then each copy only ever has one class for self, and thus all self sends become monomorphic.

### How Adaptive Optimization Works (cont.) ==>