Compact Encodings of List Structure

ABSTRACT

List structures provide a general mechanism for representing easily changed structured data, but can introduce inefficiencies in the use of space when fields of uniform size are used to contain pointers to data and to link the structure. Empirically determined regularity can be exploited to provide more space-efficient encodings without losing the flexibility inherent in list structures. The basic scheme is to provide compact pointer fields big enough to accommodate most values that occur in them and to provide “escape” mechanisms for exceptional cases. Several examples of encoding designs are presented and evaluated, including two designs currently used in Lisp machines. Alternative escape mechanisms are described, and various questions of cost and implementation are discussed. In order to extrapolate our results to larger systems than those measured, we propose a model for the generation of list pointers and we test the model against data from two programs. We show that according to our model, list structures with compact cdr fields will, as address space grows, continue to be compacted well with a fixed-width small field. Our conclusion is that with a microcodable processor, about a factor of two gain in space efficiency for list structure can be had for little or no cost in processing time.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: BATES, M. The use of syntax in a speech understanding system. IEEE Trans. Acoustics, Speech, and Signal Processing 23, 1 (Feb. 1975), 112-117.
• 3: BAWDEN, A., GREENBLATT, R., HOLLOWAY, J., KNIGHT, T., MOON, D., AND WEINREB, D. LISP machine progress report. Memo 444, M.I.T. Artificial Intelligence Lab., Cambridge, Mass., Aug. 1977.
• 4: Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
• 5: Daniel G. Bobrow , Jerry D. Burchfiel , Daniel L. Murphy , Raymond S. Tomlinson, TENEX, a paged time sharing system for the PDP - 10, Communications of the ACM, v.15 n.3, p.135-143, March 1972 [doi>10.1145/361268.361271]
• 6: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 7: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 8: Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976 [doi>10.1145/360238.360247]
• 9: Douglas Wells Clark, List structure: measurements, algorithms, and encodings., 1976
• 10: CLARK, D.W. Measurementsof dynamic list structure use in Lisp. IEEE Trans. Software Eng. SE-5, i (Jan. 1979), 51-59.
• 11: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 12: DEUrSCH, L.P. A LISP machine with very compact programs. Proc. 3rd IJCAI, Stanford, Calif., 1973, pp. 697-703.
• 13: DEUTSCH, L.P. An interactive program verifier. Ph.D. Thesis, Comptr. Sci. Dep., U. of California, Berkeley; May 1973.
• 14: L. Peter Deutsch, Experience with a microprogrammed Interlisp system, Proceedings of the 11th annual workshop on Microprogramming, p.128-129, November 19-22, 1978, Pacific Grove, California, United States
• 15: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 16: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 17: GREENBLATT, R. The LISP machine. Working Paper 79, M.I.T. Artificial Intelligence Lab., Cambridge, Mass., No~. 1974.
• 18: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 19: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 20: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 21: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 22: F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
• 23: Earl David Sacerdoti, A structure for plans and behavior., 1975
• 24: B. A. Sheil, Median split trees: a fast lookup technique for frequently occuring keys, Communications of the ACM, v.21 n.11, p.947-958, Nov. 1978 [doi>10.1145/359642.359653]
• 25: SMITH, D.H., MASlNTER, L.M., AND SRIDHZRAN, N.S. Heuristic DENDRAL: analysis of molecular structure. In W.T. Wipke, S. Heller, R- Feldman, and E. Hyde, Eds., Computer Representation and Manipulaton of Chemical Information. Wiley, New York, 1974.
• 26: TEITELMAN, W. INTERLISP Reference Manual. Xerox Palo Alto Research CenteL Palo Alto~ Calif., 1974.
• 27: ZIPF, G.Ki Human Behavior and the Principle of Least Effort: An Introductioa to Human Ecology. Hafner, New York, 1949.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Design, Languages, Performance, Theory