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.

By: Michael Hind, V. T. Rajan, Peter F. Sweeney

Published in: RC23058 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .