ABSTRACT
Generational garbage collectors are more efficient than their non-generational counterparts. Unfortunately, however, generational algorithms require both write barriers and write barrier handlers and therefore degrade worst-case performance.
In this paper, we present novel hardware support for generational garbage collection. In contrast to previous work, we introduce a hardware write barrier that does not only detect inter-generational pointers, but also executes all related book-keeping operations entirely in hardware. For the first time, write barrier detection and handling occur completely in parallel to instruction execution, so that the runtime overhead of generational garbage collection is reduced to near zero.
For evaluation purposes, we extended a system with hardware-supported real-time garbage collection with our hardware support for generational garbage collection. Measurements of Java programs on an FPGA-based prototype show that the generational extensions reduce the total duration of garbage collection activities by a factor of 5 and the memory traffic caused by the collector by a factor of 4 on average.
- Altera. STRATIX II device family data sheet, 2006.Google Scholar
- H. G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280--94, 1978. Google ScholarDigital Library
- H. G. Baker. The treadmill: real-time garbage collection without motion sickness. ACM Sigplan Notices, 27(3), 1992. Google ScholarDigital Library
- H. Lieberman and C. E. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983. Google ScholarDigital Library
- M. Meyer. A novel processor architecture with exact tag-free pointers. IEEE Micro, 24(3):46--55, 2004. Google ScholarDigital Library
- M. Meyer. An on-chip garbage collection coprocessor for embedded real-time systems. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Hong Kong, Aug. 2005. Google ScholarDigital Library
- M. Meyer. A true hardware read barrier. In ISMM'06 Proceedings of the Fifth International Symposium on Memory Management, Ottawa, June 2006. Google ScholarDigital Library
- D. A. Moon. Architecture of the Symbolics 3600. In Proceedings of the 12th Annual International Symposium on Computer Architecture, pages 76--83, Boston, MA, June 1985. Google ScholarDigital Library
- K. D. Nilsen and W. J. Schmidt. A high-performance hardware-assisted real time garbage collection system. Journal of Programming Languages, 2(1), 1994.Google Scholar
- M. Pfeffer. Ein echtzeitfähiges Java-System für einen mehrfädigen Java-Mikrocontroller. PhD thesis, University of Augsburg, Germany, Feb. 2004.Google Scholar
- M. Pfeffer, T. Ungerer, S. Fuhrmann, J. Kreuzinger, and U. Brinkschulte. Real-time garbage collection for a multithreaded Java microcontroller. Real-Time Systems, 26(1):89--106, 2004. Google ScholarDigital Library
- A. D. Samples, D. M. Ungar, and P. Hilfinger. SOAR: Smalltalk without bytecodes. In OOPSLA'86 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 21(11), pages 107--118, Oct. 1986. Google ScholarDigital Library
- W. J. Schmidt and K. D. Nilsen. Performance of a hardware-assisted real-time garbage collector. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 76--85, Oct. 1994. Google ScholarDigital Library
- D. Ungar, R. Blau, P. Foley, D. Samples, and D. Patterson. Architecture of soar: Smalltalk on a risc. In ISCA '84: Proceedings of the 11th International Symposium on Computer Architecture, pages 188--197, New York, NY, USA, June 1984. Google ScholarDigital Library
- D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5): 157--167, Apr. 1984. Google ScholarDigital Library
- P. R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, Jan. 1994.Google ScholarDigital Library
Index Terms
- Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection
Recommendations
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsModern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments