[TYPES] a paper available on "Record Unboxing", a new type-based optimization

Atsushi Ohori ohori at riec.tohoku.ac.jp
Wed Jul 4 04:09:16 EDT 2007

Dear Colleagues,

Some of the types-list readers may be interested in the following
paper, which shows a new type-based optimization method that "unboxes"
tuples/records by flattening component tuples and changing top-level
tuples to multiple value passing. The required type based analysis is
simple but the resulting method shown to be quite effective.

This is implemented in the SML# (an extension of the Standard
ML) compiler version 0.30, which is available from:

Any comments are welcome.

Best regards,


			Record Unboxing
               Huu-Duc Nguyen  and  Atsushi Ohori
                    RIEC, Tohoku University


In the conventional implementation of functional languages, tuples
(records) are uniformly implemented as heap allocated objects even
when they are used only for multiple parameter passing.  This paper
develops a type-based ``record unboxing'' optimization method that
reduces the overhead due to those unnecessary heap allocation and
associated memory accesses.  We first develops a type-based algorithm
that infers where each record expression is ``rigid'' or not, i.e. it
requires heap allocation or not based on the observation that change
of a representation of a record type that does not interact with the
external environment does not affect the behavior of the program.  We
then develop a record unboxing algorithm that transforms a functional
language with records to a multiple value calculus in which a function
can take/return multiple values by transforming all non rigid records
into multiple values.  The combination of the two yields a simple and
yet surprisingly effective optimization method.  We have implemented
the proposed method in a compiler for full Standard ML language, and
have evaluated it with a typical benchmark programs.  The results show
significant speed ups for non trivial benchmarks, including 21% speed
up of mlyacc and 27% speed up for lexgen.

More information about the Types-list mailing list