Unrolling Lists
Report ID: TR-453-94Author: Shao, Zhong / Appel, Andrew W. / Reppy, John H.
Date: 1994-03-00
Pages: 13
Download Formats: |Postscript|
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.