Dynamic Optimization

Abstract

We distinguish static and dynamic optimization of programs: whereas static optimization modifies a program before runtime and is based only its syntactical structure, dynamic optimization is based on the statistical properties of the input source and examples of program execution. Explanation-based generalization is a commonly used dynamic optimization method, but its effectiveness as a speedup-learning method is limited, in part because it fails to separate the learning process from the program transformation process. This paper describes a dynamic optimization technique called a learn-optimize cycle that first uses a learning element to uncover predictable patterns in the program execution and then uses an optimization al-gorithm to map these patterns into beneficial transformations. The technique has been used successfully for dynamic optimization of pure Prolog.