Unrolling Lists

Abstract:

Lists are ubiquitous in functional programs,
thus supporting lists efficiently is a major concern to
compiler writers for functional languages. Lists are normally represented
as linked {em cons} cells, with each {em cons} cell containing a {em car}
(the data) and a {em cdr} (the link); this is inefficient in
the use of space, because 50\% of the storage is used for links.
Loops and recursions on lists are slow on modern machines
because of the long chains
of control dependences (in checking for {em nil}) and data dependences
(in fetching {em cdr} fields).
We present a data structure for ``unrolled lists,'' where each cell
has several data items ({em car} fields) and one link ({em cdr}).
This reduces the memory used for links, and it significantly shortens
the length of control-dependence and data-dependence chains in
operations on lists.
We further present an efficient compile-time analysis that transforms
programs written for ``ordinary'' lists into programs on unrolled
lists. The use of our new representation requires no change to
existing programs.
We sketch the proof of soundness of our analysis---which is based on
refinement types---and present some preliminary measurements
of our technique.

This technical report has been published as

Unrolling Lists. Zhong Shao, John H. Reppy, and Andrew W. Appel,
Proc. 1994 ACM Conf. on Lisp and Functional
Programming, June 1994.