An Improvement to Sliding Garbage Collection

ABSTRACT

Garbage collection algorithms are divided into three main categories, namely mark-and-sweep, mark-and-compact, and copying collectors. The collectors in the mark-and-compact category are frequently overlooked, perhaps because they have traditionally been associated with greater cost than collectors in the other categories. Among the compacting collectors, the sliding collector has some advantages in that it preserves the relative age of objects. The main problem with the traditional sliding collector by Haddon and Waite [4] is that building address-forwarding tables is costly. We suggest an improvement to the existing algorithm that reverses the order between building the forwarding table and moving the objects. Our method improves performance of building the table, making the sliding collector a better contestant for young generations of objects (nurseries).

References

1. D. Abuaiadh, Y. Ossia, E. Petrank, and U. Silbershtein. An efficient parallel heap compaction algorithm. In Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '04, pages 224--236, New York, NY, USA, 2004. ACM.
2. J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage collection. ACM Trans. Program. Lang. Syst., 5(4):532--553, Oct. 1983.
3. D. A. Fisher. Bounded workspace garbage collection in an address order preserving list processing environment. Inf. Process. Lett., 3(1):29--32, July 1974.
4. B. K. Haddon and W. M. Waite. A compaction procedure for variable length storage elements. Computer Journal, (10):162--165, Aug. 1967.
5. R. Jones, A. Hosking, and E. Moss. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall/CRC, 1st edition, 2011.
6. R. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, Inc., New York, NY, USA, 1996.
7. H. B. M. Jonkers. A fast garbage compaction algorithm. Inf. Process. Lett., 9(1):26--30, July 1979.
8. H. Kermany and E. Petrank. The compressor: Concurrent, incremental, and parallel compaction. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '06, pages 354--363, New York, NY, USA, 2006. ACM.
9. S. Marlow and S. Peyton Jones. Multicore garbage collection with local heaps. SIGPLAN Not., 46(11):21--32, June 2011.
10. F. L. Morris. A time- and space-efficient garbage compaction algorithm. Commun. ACM, 21(8):662--5, 1978.
11. P. R. Wilson. Uniprocessor garbage collection techniques. In Proceedings of the International Workshop on Memory Management, IWMM '92, pages 1--42, London, UK, UK, 1992. Springer-Verlag.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection