TGC (Template garbage collector)

TGC is a garbage collector for C++ designed for generic template libraries such as the Standard Template Library (STL). Class templates represent a particular challenge to garbage collectors because the memory layout of a template object varies, depending on the types that instantantiate the class templates, and important properties such as the size of an object or the (non-)existence of internal pointers no longer are fixed. The lack of type information at program design time implies restrictions for the two collection techniques that are known for C++. Fully conservative mark-sweep collectors run in non-optimized mode only, while mostly-copying collectors with traditional pointer locators fail to work at all. TGC is a mostly-copying collector with a new pointer locator that works with templates and can perform optimizations for the various types that instantiate them.

TGC distinguishes two groups of users: designers of generic libraries and users of those libraries. The former ones, following rigorous performance requirements and the C++ philosophy not to pay for features that are not used, won't integrate TGC if other parts of the library would slow down thereby. The latter ones, not necessarily expert programmers, won't use TGC if its set-up is too complicated. The different demands of the two types of users are reflected in the design of TGC.

Plug-in philosophy: library users simply plug the collector in the library and unplug it where other allocation schemes seem to be more appropriate; no changes to the source of the library or the user program are necessary.
Flexibility: a TGC-compliant library is prepared for TGC but does not hard-wire its use. Its pointer locator is designed in a generic fashion that allows using the library with other allocation methods (e.g. malloc, operator new) as well as other kinds of collectors that require type information, without any changes to the source. If TGC is not used, there is zero overhead in space and time.
Efficiency: most of our test cases show that TGC improves the overall computation time of a user program, sometimes significantly. It can even improve the run time of programs with mostly statically allocated data, since its its allocation policy can have positive cache effects.

Requirements:

TGC works easiest with libraries that are parameterized by an allocation component. Generic libraries typically meet this requirement anyway; for those that don't, there are (not recommended) workarounds, though.
TGC currently does not support virtual inheritance (we are not aware of generic libraries that use virtual inheritance.) Please contact us if such support would be needed.

Portability:

TGC integrates the system component of the Boehm-Weiser-Demers (BDW) collector, a collector that has been ported to all major platforms. TGC should be as portable as BDW, therefore.
Our own tests were performed on NT 4.0 (VC 5.0 , g++ 2.91.57), Solaris 5.6, and Irix64 (g++ 2.91.66 ).

Tests: the Boehm-Weiser-Demers collector is a mark-sweep collector that requires no cooperation by the library designer. For library users it is as easy to use as TGC. In most of our test cases it improved the memory usage of the user program, sometimes significantly. Those interested in a comparison of the two collectors can follow this link to the latest tests.

Related work:

TGC is a further development of Bartlett's collector and the Customisable Memory Manager (CMM). It adopts BDWs segregation policy and integrates its system-dependent part.
MCC is another mostly-copying collector, but for C. Like TGC, it modifies Bartlett's original approach to a hybrid mostly-copying collecting scheme.

Authors: Gor Nishanov, Sibylle Schupp

Acknowledgements: When designing TGC we gained from the study of the 3 collectors for C++ that are publicly available. Our thanks are to J. Bartlett, the CMM group, especially G. Attardi and T. Flagelli, and H. Boehm, M. Weiser, and A. Demers for providing their collectors and making the source code available.