List processing in real time on a serial computer

ABSTRACT

A real-time list processing system is one in which the time required by the elementary list operations (e.g. CONS, CAR, CDR, RPLACA, RPLACD, EQ, and ATOM in LISP) is bounded by a (small) constant. Classical implementations of list processing systems lack this property because allocating a list cell from the heap may cause a garbage collection, which process requires time proportional to the heap size to finish. A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool. The program is small and requires no time-sharing interrupts, making it suitable for microcode. Finally, the system requires the same average time, and not more than twice the space, of a classical implementation, and those space requirements can be reduced to approximately classical proportions by compact list representation. Arrays of different sizes, a program stack, and hash linking are simple extensions to our system, and reference counting is found to be inferior for many applications.

REFERENCES

• 1: Arnborg, S. Storage administration in a virtual memory SIMULA system. BIT 12 (1972), 125-141.
• 2: Arnborg, S. Optimal memory management in a system with garbage collection. BIT 14 (1974), 375-381.
• 3: Barbacci, M. A LISP Processor for C.ai. Memo CMU-CS-71-103, Comptr. Sci. Dept., Carnegie-Mellon. Pittsburgh, Pa., 1971.
• 4: Bennett, C.H. Logical reversibility of computation. IBM J. Res. Develop. 17 (1973), 525.
• 5: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 6: Bishop, P.B. Garbage collection in a very large address space. Working Paper l 11, M.I.T.A.I. Lab., M.I.T., Sept. 1975.
• 7: Bishop, P.B. Computer systems with a very large address space and garbage collection. Ph.D. Th., TR-178, MIT Lab. for Compter Sci., Cambridge, Mass., May 1977. Forthcoming.
• 8: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 9: 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]
• 10: Campbell, J.A. Optimal use of storage in a simple model of garbage collection. Inform. Processing Letters 3, No. 2 (Nov., 1974), 37-38.
• 11: 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]
• 12: 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]
• 13: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 14: Ole-Johan Dahl , Kristen Nygaard, SIMULA: an ALGOL-based simulation language, Communications of the ACM, v.9 n.9, p.671-678, Sept. 1966 [doi>10.1145/365813.365819]
• 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: Dijkstra, E.W., Lamport, L., Martin, A.J., Scholten, C. S., Steffens, E.F.M. On-the-fly garbage collection: An exercise in cooperation. E.W. Dijkstra note EWD496, June 1975.
• 17: Dijkstra, E.W. After many a sobering experience. E.W. Dijkstra note EWD500.
• 18: 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]
• 19: Greenblatt, R. LISP Machine Progress Report memo 444, A.I. Lab., M.I.T., Cambridge, Mass., Aug. 1977.
• 20: Greenblatt, R. Private communication, Feb. ! 977.
• 21: Hoare, C.A.R. Optimization of store size for garbage collection. Inform. Processing Letters 2 (1974), 165-166.
• 22: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 23: Lamport, L. Garbage collection with multiple processes: An exercise in parallelism. CA-7602-25 ! 1, Mass. Computer Associates, Wakefield, Mass., Feb. 1976.
• 24: Lamport, L. On-the-fly garbage collection: Once more with rigor. CA-7508-1611, Mass. Computer Associates, Wakefield, Mass., Aug. 1975.
• 25: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 26: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 27: Moon, D.A. MACLISP Reference Manual. Project MAC, M.I.T., Cambridge, Mass., December 1975.
• 28: Muller, K.G. On the feasibility of concurrent garbage collection. Ph.D. Th., Tech. Hogeschool Delft, The Netherlands, March 1976 (in English).
• 29: A. Schonage, REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 30: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 31: Steele, G.L. Jr. Private communication, March 1977.
• 32: Teitelman, W., et al. INTERLISP Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.
• 33: Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
• 34: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Design, Performance, Theory

Keywords:
CDR-coding, LISP, compacting, file or database management, garbage collection, list processing, real-time, reference counting, storage allocation, storage management, virtual memory