An Advanced Memory Management Seminar

Organized by Erez Petrank


 






This seminar is run bi-weekly in IBM Haifa Research Lab during 1998-1999 and is aimed at broadening our knowledge in memory management techniques. The seminar covers issues that we do not directly handle in our projects. It is mostly attended by Hillel Kolodner's group (Runtime Subsystems) in the department of System Technology

The papers are organized in 4 groups :


List of papers

Group 1: Classical papers

  1. Incremental copying collector:

    2.  

     

    Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978. Also AI Laboratory Working Paper 139, 1977. Available here.

    (Presented by Dafna Sheinwald)

  2. Generational Garbage Collections - first papers:

    3.  

     

    Henry Lieberman and Carl E. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419-429, 1983. Also report TM-184, Laboratory for Computer science, MIT, Cambridge, MA, July 1980 and AI Lab Memo 569, 1981.

    David M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157-167, April 1984. Also published as ACM Software Engineering Notes 9, 3 (May 1984) - Proceedings of the ACM/SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 157-167, April 1984.

    (Presented by Sagie Snir)

  3. On-the-fly Garbage collection:

    4.  

     

    Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, No. 46. Springer-Verlag, New York, 1976.

    Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965-975, November 1978.

    Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM,
    18(9):495-508, September 1975.

    Guy L. Steele. Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM, 19(6):354, June 1976.

    (Will not be presented, since it is known to the participants.) 

> Back to the groups index

Group 2: Interesting advances throughout the years

  1. Write barriers:

    2.  

     

    Anthony L. Hosking, J. Eliot B. Moss, and Darko Stefanović. A comparative performance evaluation of write barrier implementations. In Andreas Paepcke, editor. OOPSLA'92 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 27(10) of ACM SIGPLAN Notices, Vancouver, British Columbia, October 1992. ACM Press, pages 92-109. Available here.

    Urs Hölzle. A fast write barrier for generational garbage collectors. In Eliot Moss, Paul R. Wilson, and Benjamin Zorn, editors. OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, October 1993. Available here.

    Paul R. Wilson and Thomas G. Moher. A card-marking scheme for controlling intergenerational references in generation-based garbage collection on stock hardware. ACM SIGPLAN Notices, 24(5):87-92, 1989.

    Patrick Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Technical Report AITR-1417, MIT AI Lab, February 1988. Bachelor of Science thesis. Available here.

    Robert A. Shaw. Improving garbage collector performance in virtual memory. Technical Report CSL-TR-87-323, Stanford University, March 1987. Also Hewlett-Packard Laboratories report STL-TM-87-05, Palo Alto, 1987.

  2. The Train algorithm:

    3.  

     

    Richard L. Hudson and J. Eliot B. Moss. Incremental garbage collection for mature objects. In Yves Bekkers and Jacques Cohen, editors. Proceedings of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, St Malo, France, 16-18 September 1992. Springer-Verlag. Available here.

    Jacob Seligmann and Steffen Grarup. Incremental mature garbage collection using the train algorithm. In  Nierstras, editor. Proceedings of 1995 European Conference on Object-Oriented Programming, Lecture Notes in Computer Science. Springer-Verlag, August 1995. Available here.

    (Presented by Katherine Barabash)

  3. Generational Garbage Collection - More issues:

    4.  

     

    David A. Moon. Garbage collection in a large LISP system. In Guy L. Steele, editor. Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, Austin, TX, August 1984. ACM Press, pages 235-245.

    David M. Ungar and Frank Jackson. Tenuring policies for generation-based storage reclamation. ACM SIGPLAN Notices, 23(11):1-17, 1988.

    David M. Ungar and Frank Jackson. An adaptive tenuring policy for generation scavengers. ACM Transactions on Programming Languages and Systems, 14(1):1-27, 1992.

  4. Card Marking and Remembered Sets for Generational Collection:

    5.  

     

    Antony L. Hosking and Richard L. Hudson. Remembered sets can also play cards. In Eliot Moss, Paul R. Wilson, and Benjamin Zorn, editors. OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, October 1993. Available here.

    Alain Azagury, Elliot K. Kolodner, Erez Petrank, and Zvi Yehudai. Combining card marking with remembered sets: How to save scanning time. In Richard Jones, editor. Proceedings of the First International Symposium on Memory Management, Vancouver, October 1998. ACM Press, pages 10-19. ISMM is the successor to the IWMM series of workshops. Available here.

  5. Mostly Parallel Garbage Collection:

    6.  

     

    [boeh91] Hans-Juergen Boehm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157-164, 1991. Available here.

    (Presented by Ron Sivan)

  6. Replication-based Garbage Collection:

    7.  

     

    Scott M. Nettles, James W. O'Toole, David Pierce, and Nicholas Haines. Replication-based incremental copying collection. In Yves Bekkers and Jacques Cohen, editors. Proceedings of International Workshop on Memory Management,volume 637 of Lecture Notes in Computer Science, St Malo, France, 16-18 September 1992. Springer-Verlag. Available here.

    Scott M. Nettles and James W. O'Toole. Real-time replication-based garbage collection. In Proceedings of SIGPLAN'93 Conference on Programming Languages Design and Implementation, volume 28(6)of ACM SIGPLAN Notices, Albuquerque, NM, June 1993. ACM Press. Available here.

    Alain Azagury, Elliot K. Kolodner, and Erez Petrank. A note on the implementation of replication-based garbage collection for multithreaded applications and multiprocessor environments. In Parallel Processing Letters, 1999. To appear. Available here.

  7. Use of paging system for incremental collection:

    8.  

     

    Andrew W. Appel, John R. Ellis, and Kai Li. Real-time concurrent collection on stock multiprocessors. ACM SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation, June 1988.  ACM SIGPLAN Notices, 23(7):11-20, 1988.  Available here

  8. Cache Performance with Heap Allocation and GC:

    9.  

     

    Henry G. Baker. Cache-conscious copying collection. In Paul R. Wilson and Barry Hayes, editors. OOPSLA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems, Addendum to OOPSLA'91 Proceedings, October 1991. Available as an html or as a postscript file.

    Benjamin Zorn. The effect of garbage collection on cache performance. Technical Report CU-CS-528-91, University of Colorado at Boulder, May 1991. Available here.

    Paul R. Wilson, Michael S. Lam, and Thomas G. Moher. Caching consideration for generational garbage collection: A case study of large and set-associative caches. Technical Report UIC-EECS-90-5, University of Illinois at Chicago EECS Department, Chicago, Illinois, December 1990. Improved version (available here) appears in Conference Record of the 1992 ACM Symposium on Lisp and Functional Programming, San Francisco, CA, June 1992. ACM Press.

    Marcelo J. R. Gonçalves and Andrew W. Appel. Cache performance of fast-allocating programs. Technical Report CS-TR-482-94, Department of Computer Science, Princeton University, December 1994. Available here.

    Mark B. Reinhold. Cache performance of garbage-collected programs. In Proceedings of SIGPLAN'94 Conference on Programming Languages Design and Implementation, volume 29 ofACM SIGPLAN Notices, Orlando, FL, June 1994. ACM Press. Also Lisp Pointers VIII 3, July-September 1994. Available here.

    Brad Calder, Chandra Krintz, Simmi John, and Todd Austin. Cache-Conscious Data Placement. In the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, California, October, 1998.  Available here.

    Trishul M. Chilimbi and James R. Larus. Using generational garbage collection to implement cache-conscious data placement. In Richard Jones, editor. Proceedings of the First International Symposium on Memory Management, Vancouver, October 1998. ACM Press, pages 37-48. Available in pdf and postscript.

    (To be presented by Tamar Domany and Erez Petrank)

  9. Virtual memory performance:

    10.  

     

    Robert Courts. Improving locality of reference in a garbage-collecting memory management-system. Communications of the ACM, 31(9):1128-1138, 1988.

    David A. Moon. Garbage collection in a large LISP system. In Guy L. Steele, editor. Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, Austin, TX, August 1984. ACM Press. , pages 235-245

    (To be presented by Victor Umansky)

  10. Conservative mark & sweep + mostly copying garbage collection by Bartlett.

    11.  

     

    Joel F. Bartlett. Compacting garbage collection with ambiguous roots. Technical Report 88/2, DEC Western Research Laboratory, Palo Alto, CA, February 1988. Also in Lisp Pointers 1, 6 (April-June 1988), 2-12. Available here.

    Joel F. Bartlett. Mostly-Copying garbage collection picks up generations and C++. Technical note, DEC Western Research Laboratory, Palo Alto, CA, October 1989. Sources available in ftp://gatekeeper.dec.com/pub/DEC/CCgc. Available here.

    (Presented by Tamar Domany)

  11. Parallel on-the-fly collector:

    12.  

     

    Leslie Lamport. Garbage collection with multiple processes: an exercise in parallelism. In Proceedings of the 1976 International Conference on Parallel Processing, pages 50-54, 1976.

    Christian Queinnec, Barbara Beaudoing, and Jean-Pierre Queille. Mark DURING Sweep rather than Mark THEN Sweep. Lecture Notes in Computer Science, 365:224-237, 1989. Available here.

    Lorenz Huelsbergen and Phil Winterbottom. Very concurrent mark-&-sweep garbage collection without fine-grain synchronization. In Richard Jones, editor. Proceedings of the First International Symposium on Memory Management, Vancouver, October 1998. ACM Press, pages 166-175.

  12. Parallel mark & sweep:

    13.  

     

    Toshio Endo, Kenjiro Taura, and Akinori Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of High Performance Computing and Networking (SC'97), 1997. Available here.

    (Presented by Erez Petrank)

  13. Generations without moving the objects:

    14.  

     

    Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In [POPL90] Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, San Francisco, CA, January 1990. ACM Press, pages 261-269.

    (Partially presented by Erez Petrank in summary of the generations project).

  14. Compiler Support for garbage collection:

    15.  

     

    Amer Diwan, J. Eliot B. Moss, and Richard Hudson. Compiler Support for Garbage Collection in a Statically Typed Language. In [PLDI '92] Proceedings of SIGPLAN'92 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices 1992, pp. 273-282. Available here.

    (Presented by Victor Umansky).

  15. The Treadmill algorithm:

    16.  

     

    Henry G. Baker. The Treadmill, real-time garbage collection without motion sickness. ACM SIGPLAN Notices, 27(3):66-70, March 1992. Available in HTML format or postscript.

    Tian F. Lim, Przemyslaw Pardyak, and Brian N. Bershad. A memory-efficient real-time non-copying garbage collector. In Richard Jones, editor. Proceedings of the First International Symposium on Memory management, Vancouver, October 1998. ACM Press, pages 118-129.

    (Presented by Eitan Lewis)

  16. Garbage collection using a snapshot of the heap:

    17.  

     

    Shinichi Furusou, Satoshi Matsuoka, and Akinori Yonezawa. Parallel conservative garbage collection withfast allocation. In Paul R. Wilson and Barry Hayes, editors. OOPSLA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems, Addendum to OOPSLA'91 Proceedings, October 1991.]. Available here.

    (Idea appears earlier in Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In [POPL90] Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, San Francisco, CA, January 1990. ACM Press, pages 261-269.)

  17. Reference counting: basic algorithm + a few tricks + concurrent version.

    18.  

     

    Richard E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996. With a chapter on Distributed Garbage Collection by R. Lins. Webpage here.

    John DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.

    (Presented by Yossi Levanoni) 

> Back to the groups index

Group 3: State of the art

  1. pretenuring objects and generational scanning of stacks (PLDI98)

    2.  

     

    Perry Cheng, Robert Harper, and Peter Lee. Generational stack collection and profile-driven pretenuring. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Montreal, June 1998. ACM Press. Available here.

    (Presented by Shlomit Pinter)

  2. Advanced on-the-fly garbage collection

    3.  

     

    Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1994. Available here.

    Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1993. Pages 113-123. Available here.

  3. Precise Garbage Collection for Java

    4.  

     

    Ole Agesen and David Detlefs. Finding references in Java stacks. In Dickman and Paul R. Wilson, editors. OOPSLA '97 Workshop on Garbage Collection and Memory Management,October 1997. Available here.

    Ole Agesen and David Detlefs. Garbage collection and live variable type-precision and liveness in Java Virtual Machines. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Montreal, June 1998. ACM Press.

    (Presented by Hillel Kolodner)

  4. The garbage collection general interface:

    5.  

     

    Derek White and Alex Garthwaite. The GC Interface in the EVM. Sun Labs TR 98-67. Available in PDF (307KB) or postscript (419KB).

    (Presented by Boaz Shmueli)

  5. A new approach to generations:

    6.  

     

    Darko Stefanovic, J. Eliot B. Moss, K. S. McKinley. Age-Based Garbage Collection. A preliminary version of a paper to appear in OOPSLA'99. Available here.

    (To be presented by Dafna Sheinwald)

  6. Stop-the-world with many safe points:

    7.  

     

    J.M. Stichnoth, G.Y. Lueh and M. Cierniak, Support for Garbage Collection at Every Instruction in a Java Compiler,  Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, May 1999

    (To be presented by Ronny Sivan)

  7. Complexity bounds for multiprocessor GC:

    8.  

     

    Guy Blelloch and Perry Cheng. On Bounding Time and Space for Multiprocessor Garbage Collection. Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, May 1999

    (To be presented by Kathy Barabash)

  8. Cache-conscious structures:

    9.  

     

    Trishul M. Chilimbi, Bob Davidson, and James R. Larus. Cache-conscious structure definition. In Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, May 1999, pages 13-24.  Available in pdf and postscript.

    Trishul M. Chilimbi, Mark D. Hill, and James R. Larus. Cache-conscious structure layout. In Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, May 1999, pages 1-12.  Available in pdf and postscript.

    (Presented by Hillel Kolodner)

  9. An improved sweep for sparse heaps:

    10.  

     

    Yoo C. Chung, Soo-Mook Moon, Kermal Ebcioglu, Dan Sahlin. Reducing Sweep Time for a Nearly Empty Heap. In Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. January 19 - 21, 2000.

    (To be presented by Shlomit Pinter)

  10. Reference counting for servers:

    11.  

     

    David F. Bacon, Clement R. Attanasio, Han B. Loc, and Stephen Smith. Java without the Coffee Breaks:  A Nonintrusive Multiprocessor Garbage Collector.  In Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, June 2000.

    Josseph Levanoni and Erez Petrank.   A Scalable Reference Counting Garbage Collector.   Technical Report
    CS-0967, Dept. of Computer Science, Technion, Nov. 1999.  Available here.

    (To be presented by Kathy Barabash and Yossi Levanoni)

> Back to the groups index

Group 4: Miscelleneous

  1. Distributed GC:

    2.  

     

    Marc Shapiro, David Plainfossé, Paulo Ferreira, and Laurent Amsaleg. Some key issues in the design ofdistributed garbage collection and references. In Unifying Theory and Practice in Distributed Systems, Dagstuhl (Germany), September 1994. Available here.
    A more appropriate introductory paper from the first two authors is available here.

    Richard E. Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996. See a chapter on Distributed Garbage Collection. Book content described here.

    (Presented by Yael Gavish)

  2. Allocation Methods:

    3.  

     

    Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic storage allocation: A survey and critical review. In Henry Baker, editor. Proceedings of International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science, Kinross, Scotland, September 1995. Springer-Verlag. Available here.

    Benjamin Zorn and Dirk Grunwald. Empirical measurements of six allocation-intensive C programs. Computer Science Technical Report CU-CS-604-92, University of Colorado, July 1992. Available here.

    Benjamin Zorn and Dirk Grunwald. Evaluating models of memory allocation. Computer Science Technical Report CU-CS-603-92, University of Colorado, July 1992. Available here.

    (Presented by Eliot Salant)

  3. How to measure GC performance.

    4.  

     

    Benjamin G. Zorn. Comparative Performance Evaluation of Garbage Collection Algorithms. PhD thesis, University of California at Berkeley, March 1989. Technical Report UCB/CSD 89/544. Available here.

    B. Zorn. Designing systems for evaluation: A case study of garbage collection. In Eric Jul and Niels-Christian Juul, editors. OOPSLA/ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems, Ottawa, October 1990. Available here.

    (To be presented by Liran Katzir)

> Back to the groups index