A new list compaction method

Kai Li, Paul Hudak

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


List compaction, or so‐called ‘cdr‐coding’, can greatly reduce the storage needs of list processing languages. However, existing methods do not perform well when several lists are being constructed simultaneously from the same heap, since the non‐contiguous nature of the cells being allocated eliminates the opportunity for compaction. This situation arises not only in true parallel systems sharing a common memory, and sequential systems supporting multiple processes, but also quite often in purely sequential systems, where it is not uncommon to build several different lists simultaneously within a single loop. In this paper, a new list compaction method is presented that performs well during both sequential and ‘parallel’ list generation. The method is essentially a generalization of cdr‐coding, in which lists are represented explicitly as linked vectors rather than implicitly as compacted memory. In addition, an encoding scheme is used that is as simple or simpler than all known encodings, and destructive operations are supported with no greater overhead than existing schemes. Performance figures in a simulated environment suggest that the strategy consistently performs better than conventional cdr‐coding, with essentially the same complexity.

Original languageEnglish (US)
Pages (from-to)145-163
Number of pages19
JournalSoftware: Practice and Experience
Issue number2
StatePublished - Feb 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software


  • LISP programming
  • List compaction
  • List structure
  • Memory management
  • Shared‐memory parallel
  • computing


Dive into the research topics of 'A new list compaction method'. Together they form a unique fingerprint.

Cite this