Optimising the Memory Management of Higher-Order Functional Programs

Markus Mohnen

           In this thesis, we present escape analysis, a method for
           extracting safe approximations of the memory behaviour of
           higher-order functional programs and verify the correctness of
           this analysis.  Furthermore, we describe how the information
           gained by escape analysis can be used to improve the program's
           execution. Finally, we give measurements of the effect on
           the runtime behaviour of programs both in terms of memory
           consumption and execution time.

           This thesis presents a detailed study of escape analysis and
           its influence on the performance. The main contributions of
           the thesis are:

           * We define the notion of escaping as denotational property of
             programs. This allows us to validate the correctness of
             the analysis without the necessity to fix the operational
             model more than marginally. We intentionally avoid the
             use of abstract machines as operational model, since the
             implementation details imposed by the choice of an abstract
             machine are irrelevant for our approach.
           * Our escape analysis imposes only a very small compile--time
             overhead. We show that by using special properties of the
             analysis, we can improve the analysis from exponential
             to quadratic complexity in the worst--case. For realistic
             programs, the analysis can be performed at almost linear
             lime.
           * Since the standard theory of denotational semantics, which
           is based
             on the fixpoint theorem of Knaster and Tarski, does not allow
             the definition of a denotational model for graph reduction,
             we develop a suitable extension of the theorem.
           * We give the first model--based proof of correctness of escape
             analysis and applications based on escape information.
           * Detailed performance evaluations allow a precise
           understanding of
             the effects of the applications. We show that the combination
             of traditional and compile--time garbage collection not
             only improves the memory consumption immensely, but also
             the runtimes of the programs. The performance evaluations
             are the most detailed in literature.
           * Although the language we use lacks many of the advanced
           features of
             modern functional languages, we show that our results can
             be transfered to realistic languages, demonstrating the
             extensibility of our approach.