Compiling Standard ML for Efficient Execution on Modern Machines (Thesis)
Report ID: TR-475-94Author: Shao, Zhong
Date: 1994-11-00
Pages: 169
Download Formats: |Postscript|
Abstract:
Many language theoreticians have taken great efforts in designing higher-level programming languages that are more elegant and more expressive than conventional languages. However, few of these new languages have been implemented very efficiently. The result is that most software engineers still prefer to use conventional languages, even though the new higher-level languages offer a better and simpler programming model. This dissertation concentrates on improving the performance of programs written in Standard ML (SML)---a statically typed functional language---on today's RISC machines. SML poses tough challenges to efficient implementations: very frequent function calls, polymorphic types, recursive data structures, higher-order functions, and first-class continuations. This dissertation presents the design and evaluation of several new compilation techniques that meet these challenges by taking advantage of some of the higher-level language features in SML. Type-directed compilation exploits the use of compile-time type information to optimize data representations and function calling conventions. By inserting coercions at each type instantiation and abstraction site, data objects in SML can use the same unboxed representations as in C, even with the presence of polymorphic functions. Measurements show that a simple set of type-based optimizations improves the performance of the non-type-based compiler by about 19% on a DECstation 5000. Space-efficient closure representations utilizes the compile-time control and data flow information to optimize closure representations. By extensive closure sharing and allocating as many closures in registers as possible, the new closure conversion algorithm achieves very good asymptotic space usage, and improves the performance of the old compiler by about 14% on a DECstation 5000, even without using a stack. Further empirical and analytic studies show that the execution cost of stack-allocated and heap-allocated activation records is similar, but heap allocation is simpler to implement and allows very efficient first-class continuations. Unrolling lists takes advantage of the higher-level language abstraction in SML to support more efficient representations for lists. By representing each cons cell using multiple car fields and one cdr field, the unrolled list reduces the memory used for links and significantly shortens the length of control-dependence and data-dependence chains in operations on lists.