Unrolling lists

Zhong Shao, John H. Reppy, Andrew W. Appel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

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 cons cells, with each cons cell containing a car (the data) and a 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 dependencies (in checking for nil) and data dependences (in fetching cdr fields). We present a data structure for 'unrolled lists,' where each cell has several data items (car fields) and one link (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.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on LISP and Functional Programming
PublisherPubl by ACM
Pages185-195
Number of pages11
Edition3
ISBN (Print)0897916433, 9780897916431
DOIs
StatePublished - Jan 1 1994
EventProceedings of the 1994 ACM Conference on LISP and Functional Programming - Orlando, FL, USA
Duration: Jun 27 1994Jun 29 1994

Publication series

NameProceedings of the ACM Conference on LISP and Functional Programming
Number3
Volume7

Other

OtherProceedings of the 1994 ACM Conference on LISP and Functional Programming
CityOrlando, FL, USA
Period6/27/946/29/94

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Unrolling lists'. Together they form a unique fingerprint.

  • Cite this

    Shao, Z., Reppy, J. H., & Appel, A. W. (1994). Unrolling lists. In Proceedings of the ACM Conference on LISP and Functional Programming (3 ed., pp. 185-195). (Proceedings of the ACM Conference on LISP and Functional Programming; Vol. 7, No. 3). Publ by ACM. https://doi.org/10.1145/182590.182453