A compacting incremental collector and its performance in a production quality compiler

ABSTRACT

We present a new near-real-time compacting collector and its implementation in a production quality Scheme compiler (Gambit-C). Our goal is to use this system as a base for an implementation of Erlang for writing soft real-time telecommunication applications. We start with a description of Gambit-C's memory organisation and its blocking collector. The design and integration of the incremental collector within Gambit-C are then explained. Finally we measure the performance of the incremental collector and compare it to the original blocking collector. We found that the overhead of the incremental collector is high (a factor of 1.3 to 8.1, with a median of 2.24) but nevertheless the collection pauses are compatible with typical soft real-time requirements (we get an average pause of 2.9 milliseconds and a maximum pause of 15 milliseconds on a 133Mhz DEC Alpha 21064).

REFERENCES

• AVWW96: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• AXD98: AXD 301 High-performance ATM switching system. Ericsson Telecom AB, 1998.
• BW88: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• Che70: 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]
• DFS96: Danny Dub@, Marc Feeley, and Manuel Serrano. Un GC temps r@el semi-compactant. In Guy Lapalme and Christian Queinnec, editors, Journ~es Francophones des Langages Applicatifs, volume 7, pages 165-181, Val-Morin, Qu@bec, Janvier 1996. INRIA.
• DLM+78: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• Dub96: Danny Dub@. Un syst~me de programmation Scheme pour micro-contrSleur. Master's thesis, D~partement d~Informatique et de Recherche Op@rationnelle, Universit~ de Montr@al, April 1996o
• Fee93: Marc Feeley, Polling efficiently on stock hardware, Proceedings of the conference on Functional programming languages and computer architecture, p.179-187, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165205]
• FL98: Marc Feeley and Martin Larose. Compiling Erlang to Scheme. In Proceedings of the 1998 Programming Languages, Implementations, Logics and Programs Conference, September 1998.
• FM90: Marc Feeley , James S. Miller, A parallel virtual machine for efficient scheme compilation, Proceedings of the 1990 ACM conference on LISP and functional programming, p.119-130, June 27-29, 1990, Nice, France [doi>10.1145/91556.91606]
• FMRW97: M. Feeley, J. Miller, G. Rozas, and J. Wilson. Compiling Higher-Order Languages into Fully TaiI-Recursive Portable C~ Technical Report 1078, D@partement d'Informatique et de Recherche Ope!rationnelle, Universitd de Montr@al, Aofit 1997.
• Gab85: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• HDB90: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, ACM SIGPLAN Notices, v.25 n.6, p.66-77, Jun. 1990
• HFA+96: Pieter H. Hartel, Marc FeeIey, Martin Alt, Lennart Augustsson, Peter Baumann, Marcel Beemster, Emmanuel Chailloux, Christine H. Flood, Wolfgang Grieskamp, John H. G. van Groningen, Kevin Hammond, Bogumi~Hausman, Melody Y. Ivory, Richard Jones, Peter Lee, Xavier Leroy, Rafael Lins, Sandra Loosemore, Niklas RSjemo, Manuel Serrano, Jean-Pierre Talpin, Jon Thackray, Stephen Thomas, Pierre Weis, and Peter Wentworth. Benchmarking implementations of functional languages with "pseudoknot", a floatintensive benchmark. Journal of Functional Programming, 6(4), 1996.
• NO93: Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
• Ste75: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SCHEME
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory