Hashconsing in an incrementally garbage-collected system: a story of weak pointers and hashconsing in ocaml 3.10.2

ABSTRACT

This article describes the implementations of weak pointers, weak hashtables and hashconsing in version 3.10.2 of the Objective Caml system, with focus on several performance pitfalls and their solutions.

REFERENCES

• 1: Andrew W. Appel and Marcelo J. R. Gonçalves. Hash-consing garbage collection. Technical Report CS-TR-412-93, Computer Science Department, 1993. URL citeseer.ist.psu.edu/111544.html.
• 2: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In J. Maluszyński and M. Wirsing, editors, Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming, number 528, pages 1--13. Springer Verlag, 1991. URL citeseer.ist.psu.edu/appel91standard.html.
• 3: 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]
• 4: David Beazley , Guido Van Rossum, Python; Essential Reference, New Riders Publishing, Thousand Oaks, CA, 1999
• 5: Richard Bonichon, David Delahaye, and Damien Doligez. Zenon : An extensible automated theorem prover producing checkable proofs. In Nachum Dershowitz and Andrei Voronkov, editors, LPAR, volume 4790 of Lecture Notes in Computer Science, pages 151--165. Springer, 2007. ISBN 9783540755586.
• 6: Emmanuel Chailloux, Pascal Manoury, and Bruno Pagano. Développement d'applications avec Objective Caml. O'Reilly, 2000.
• 7: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 8: Sylvain Conchon and Evelyne Contejean. The Alt-Ergo automatic theorem prover, 2006. URL http://altergo.lri.fr/.
• 9: Jeffrey Considine. Efficient hash-consing of recursive types, 2000. URL http://citeseer.ist.psu.edu/article/rey00ecient.html.
• 10: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 11: Conal Elliott , Paul Hudak, Functional reactive animation, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.263-273, June 09-11, 1997, Amsterdam, The Netherlands
• 12: Jean-Christophe Filliâtre , Sylvain Conchon, Type-safe modular hash-consing, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159876.1159880]
• 13: Frama-C development team. Frama-C: Framework for modular analysis of C, 2008. URL http://frama-c.cea.fr/.
• 14: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 15: Eiichi Goto. Monocopy and associative algorithms in an extended lisp. Technical Report TR 74-03, University of Tokyo, 1974.
• 16: Bruno Haible. Weak References, Data Types and Implementation, 2005. URL http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html.
• 17: Xavier Leroy. The Objective Caml system, release 1.07, Documentation and user's manual, 1997. URL http://caml.inria.fr/pub/distrib/ocaml-1.07/ocaml-1.07-refman.txt.
• 18: Xavier Leroy, Damien Doligez, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon. The Objective Caml system, release 3.10, Documentation and user's manual, 2007. URL http://caml.inria.fr/pub/distrib/ocaml-3.10/ocaml-3.10-refman.txt.
• 19: Zheng Li. Weaktbl, a weak hash table library for OCaml, 2007. http://www.pps.jussieu.fr/~li/software/weaktbl/README.
• 20: Laurent Mauborgne, Improving the Representation of Infinite Trees to Deal with Sets of Trees, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.275-289, April 02, 2000
• 21: Benjamin Monate , Julien Signoles, Slicing for Security of Code, Proceedings of the 1st international conference on Trusted Computing and Trust in Information Technologies: Trusted Computing - Challenges and Applications, March 11-12, 2008, Villach, Austria [doi>10.1007/978-3-540-68979-9_10]
• 22: Chris Okasaki and Andrew Gill. Fast mergeable integer maps. In Workshop on ML, pages 77--86, 1998. URL http://citeseer.ist.psu.edu/okasaki98fast.html.
• 23: Simon L. Peyton Jones , Simon Marlow , Conal Elliott, Stretching the Storage Manager: Weak Pointers and Stable Names in Haskell, Selected Papers from the 11th International Workshop on Implementation of Functional Languages, p.37-58, September 07-10, 1999
• 24: François Pottier and Yann Régis-Gianas. Menhir, December 2005. URL http://cristal.inria.fr/~fpottier/menhir/.
• 25: Zhong Shao. An overview of the FLINT/ML compiler. In Proc. 1997 ACM SIGPLAN Workshop on Types in Compilation (TIC'97), Amsterdam, The Netherlands, June 1997.
• 26: Wikipedia. File Allocation Table, 2008. URL http://en.wikipedia.org/wiki/File_Allocation_Table.
• 27: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques

General Terms:
Design, Performance

Keywords:
garbage collection, hash-consing, maximal sharing, ocaml, weak hashtables, weak pointers, weak references