The Phase Shift Detection Problem is Non-Monotonic

Object-oriented languages have enabled the creation of large commercial applications, where high performance is critical. To achieve high performance, dynamic optimization, which is performed at execution time, must be continuously tailored to the application’s changing runtime behavior. One important technology to enable this continuous optimization is phase shift detection, which allows a dynamic optimization system to react appropriately to improve the system’s performance.

However, there has been limited success in exploiting phase shift detection in virtual machines. To help evaluate phase detection algorithms, we attempted to find the canonical phase structure of a program’s profile. Starting with a simple phase shift detection algorithm specified by three fundamental parameters, we demonstrate with examples and profile data that two of the three parameters are non-monotonic with respect to the phase shift detection algorithm’s decisions. This result implies that to determine the “best” value for a non-monotonic parameters may require an exhaustive search of all possible values. Furthermore, once the "best" value for a parameter is found for a particular profile, tuning the parameter’s value for another profile is no easier than attempting to find the value from scratch.

This fundamental result is important for dynamic optimization systems because it implies that the choice of values for a phase shift detection algorithm’s parameters can have a dramatic impact on the quality of the information that is produced, and thus the choices should be carefully studied.