×

A mostly-copying collector component for class templates. (English) Zbl 1009.68874

Summary: Class templates represent a difficulty for C++ garbage collectors since relevant information is available only very late, at instantiation time. Current collectors therefore either fail to work with class templates or have to run in a non-optimized mode. This paper introduces the template garbage collector (TGC), the first mostly-copying collector that can handle class templates. It discusses the design decisions that are suggested by the specifics of generic template programming and presents performance results and memory measurements of tests with MTL and GTL, two generic C++ libraries based on the Standard Template Library. The tests show that TGC substantially improves the run times of programs with many small objects with short lifetimes or large objects with long lifetimes. The memory usage at the same time is reasonable. Since TGC modifies the mostly-copying technique, the heap sizes are in many cases considerably smaller than they are for traditional mostly-copying collectors. The tests also show that TGC is competitive with the Boehm-Demers-Weiser collector, the most widely used collector for C++.

MSC:

68U99 Computing methodologies and applications
68N01 General topics in the theory of software

Software:

STL; GC; GTL; LiDIA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] The standard template library. Technical Report HPL-95-11, Hewlett Packard, 1995.
[2] STL Tutorial and Reference Guide. C++ Programming with the Standard Template Library. Addison-Wesley, 1996.
[3] ANSI-ISO-IEC. C++ Standard, ISO/IEC 14882:1998, ANSI standards for information technology edition, 1998.
[4] The matrix template library: A generic programming approach to high performance numerical linear algebra. International Symposium on Computing in Object-Oriented Parallel Environments, 1998.
[5] A modern framework for portable high performance numerical linear algebra. Master’s Thesis, Notre Dame, 1999.
[6] The graph template library. http://www.fmi.uni-passau.de/Graphlet [15 July 2000].
[7] The generic graph component library. Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA’99), 1999; 34:399-414.
[8] The bioinformatics template library. http://www.cryst.bbk.ac.uk/?classlib/bioinf/BTL99.html [15 July 2000].
[9] Powell, C/C++ Users Journal 18 pp 40– (2000)
[10] et. al. MPC++. Parallel Programming Using C++, (ed.). MIT Press, 1996; 427-466.
[11] Compacting garbage collection with ambiguous roots. Technical Report 88-2, DEC Western Research Laboratory, 1988.
[12] Boehm, Software Practice & Experience 18 pp 807– (1998) · doi:10.1002/spe.4380180902
[13] Comparing mostly-copying and mark-sweep conservative collection. Proceedings of the International Symposium on Memory Management 1998, (ed.). ACM: Vancouver, Canada, 1998; 68-78.
[14] Space efficient conservative garbage collection. Proceedings of the ACM SIGPLAN ’93 Conference on Programming Languages Design and Implementation, vol. 28. ACM, 1993; 197-206.
[15] Design and implementation of the fgc garbage collector. Technical Report 98-7, RPI: Troy, CA. 1998.
[16] The template garbage collector (TGC). http://www.cs.rpi.edu/research/gpg/tgc.html [15 July 2000].
[17] Garbage Collection. Algorithms for Automatic Dynamic Memory Management. Wiley, 1996. · Zbl 0945.68508
[18] Uniprocessor garbage collection techniques. Proceedings of International Workshop on Memory Management (Lecture Notes in Computer Science, vol. 637), (eds.). Springer-Verlag: Berlin, 1992; 1-42.
[19] The Boehm-Weiser-Demers collector. http://www.hpl.hp.com/personal/Hans_Boehm/gc [15 July 2000].
[20] The LiDIA group. LiDIA. A C++ library for computational number theory. http://www.informatik.tu-darmstadt.de/TI/LiDIA [15 July 2000].
[21] Mostly-copying garbage collection picks up generations and C++. Technical Note, DEC Western Research Laboratory, October 1989.
[22] Experience with concurrent garbage collectors for Modula-2+. Technical Report SRC-064, Digital System Research Center, 1990.
[23] Modula-3 report (revised). Technical Report SRC-052, Digital Systems Research Center, 1989.
[24] Attardi, Journal of Symbolic Computation 21 pp 293– (1996) · Zbl 05474558 · doi:10.1006/jsco.1996.0013
[25] Performance tuning in a customisable collector. Proceedings of the International Workshop on Memory Management (Lecture Notes in Computer Science, vol. 986), (ed.). Springer Verlag: Berlin, 1995; 179-196. · doi:10.1007/3-540-60368-9_24
[26] Garbage collection in generic libraries. Proceedings of the International Symposium on Memory Management, 1998, (ed.). ACM: Vancouver, Canada, 1998; 86-97.
[27] Effective static-graph reorganization to improve locality in garbage collected systems. Proceedings of the ACM SIGPLAN Conference on Programming Languages Design and Implementation (PLDI 1991), 1991; 177-191.
[28] Stamos, ACM Transactions on Computer Systems pp 155– (1984) · doi:10.1145/190.194
[29] Garbage collection in a small LISP system. Proceedings of the 1984 ACM Conference on LISP and Functional Programming, 1984. ACM: Austin, Texas; 235-245.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.