A reference-counting garbage collection algorithmfor cyclical functional programming

ABSTRACT

Reference-counting garbage collection is known to have problems with the collection of cyclically connected data. There are two historically significant styles of cycle-aware algorithms: The style of Brownbridge that maintains a subset of marked edges and the invariant that every cycle contains at least one marked edge, and the style of Martinez-Lins-Wachenchauzer (MLW) that involves local mark-and-scan procedures to detect cycles. The former is known to be difficult to design and implement correctly, and the latter to have pathological efficiency for a number of very typical situations. We present a novel algorithm that combines both approaches to obtain reasonably efficient local mark-and-scan phases with a marking invariant that is rather cheap to maintain. We demonstrate that the assumptions of this algorithm about mutator activity patterns make it well-suited, but not limited, to a functional programming technique for cyclic data. We evaluate the approach in comparison with simple and more sophisticated MLW algorithms using a simple benchmark based on that functional paradigm.

REFERENCES

• 1: David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 3: P. A. Bigot and S. K. Debray. Return value placement and tail call optimization in high level languages. Journal of Logic Programming, 38(1):1--29, 1999.
• 4: R. S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21:239--250, 1984.
• 5: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 6: D. R. Brownbridge, Cyclic reference counting for combinator machines, Proc. of a conference on Functional programming languages and computer architecture, p.273-288, January 1985, Nancy, France
• 7: D. P. Friedman and D. S. Wise. Reference counting can manage the circular environments of mutual recursion. Information Processing Letters, 8(1):41--45, 1979.
• 8: Richard E. Jones , Rafael D. Lins, Cyclic Weighted Reference Counting without Delay, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.712-715, June 14-17, 1993
• 9: James Richard Larus , Paul Hifinger, Restructuring symbolic programs for concurrent execution on multiprocessors, University of California, Berkeley, 1989
• 10: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 11: Rafael D. Lins, Cyclic reference counting with lazy mark-scan, Information Processing Letters, v.44 n.4, p.215-220, Dec. 10, 1992 [doi>10.1016/0020-0190(92)90088-D]
• 12: Rafael D. Lins, Generational cyclic reference counting, Information Processing Letters, v.46 n.1, p.19-20, April 29, 1993 [doi>10.1016/0020-0190(93)90190-K]
• 13: Rafael Dueire Lins, An efficient algorithm for cyclic reference counting, Information Processing Letters, v.83 n.3, p.145-150, 16 August 2002 [doi>10.1016/S0020-0190(01)00328-3]
• 14: R. D. Lins, F. Heron de Carvalho Junior, and Z. D. Lins. Cyclic reference counting with permanent objects. Journal of Universal Computer Science, 13(6):830--838, 2007.
• 15: A. D. Martínez , R. Wachenchauzer , R. D. Lins, Cyclic reference counting with local mark-scan, Information Processing Letters, v.34 n.1, p.31-35, February 1990 [doi>10.1016/0020-0190(90)90226-N]
• 16: E. Pepels, M. van Eekelen, and M. Plasmeijer. A cyclic reference counting algorithm and its proof. Technical Report 88?10, Computing Science Department, University of Nijmegen, 1988.
• 17: D. Pereira and J. Aycock. Dynamic region inference. Technical Report TR 2002 709 12, Department of Computer Science, University of Calgary, 2002.
• 18: P. Roy , S. Seshadri , A. Silberschatz , S. Sudarshan , S. Ashwin, Garbage collection in object-oriented databases using transactional cyclic reference counting, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.179-193, August 1998 [doi>10.1007/s007780050062]
• 19: J. D. Salkild. Implementation and analysis of two reference counting algorithms. Master?s thesis, University College, London, 1987.
• 20: B. Trancón y Widemann. Advanced strict corecursion. In Proceedings of the Symposium on Implementation of Functional Languages. Heriot-Watt University, Edinburgh, 2003.
• 21: B. Trancón y Widemann. Ein striktes coalgebraisches Berechnungsmodell. In Programmiersprachen und Rechenkonzepte (22. Workshop der GI-Fachgruppe 2.1.4). Christian-Albrechts-Universität, Kiel, 2005.
• 22: B. Trancón y Widemann. Strikte Verfahren Zyklischer Berechnung. PhD thesis, Technische Universität Berlin, 2008.
• 23: D. H. D.Warren. DAI Research Report 141, University of Edinburgh, 1980.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Performance, Theory

Keywords:
cycles, functional programming, garbage collection, memory management, reference counting