This project has three important goals: to propose and investigate new effective algorithms for conservative generation of garbage collection in C and C++ (using true generation techniques), to use a new simulation-based evaluation technique that is largely language and system independent, and to prototype the most attractive algorithms and measure them directly. In recent years, conservative collection algorithms have been used in C and C++. This project focuses on developing, evaluating and implementing the most efficient generation techniques available in the context of conservative collection. All existing conservative algorithms for C and C++ require that every living object in the heap is scanned during each garbage collection-eliminating two essential advantages of generation collection (locality and efficiency). The new algorithms investigated will only require that a small subset of the heap is scanned during each collection. By investigating the use of garbage collection in such widely-used languages as C and C++, and by providing a thorough comparative evaluation of these techniques, this research may lead to widely-used versions of efficient garbage collection implementations. In the past, evaluation of garbage collection algorithms has been limited by the high cost of implementing the algorithms. As a result, substantially different algorithms have rarely been compared in a systematic way. Recently, however, Zorn showed that trace-driven simulation using object-level traces can be successfully used to evaluate and compare different garbage collection algorithms. This project extends previous work by combining object-level tracing with abstract execution, thus allowing evaluation of garbage collection algorithms in a mostly language-independent manner.
