395T Memory Management Schedule

    Date Presenter Topic/Presentation Reading
    Jan 19 Kathryn McKinley Garbage Collection Setting the Stage & Course Organization
    Jan 26 Curtis Dunham Mark-Sweep An efficient machine-independent procedure for garbage collection in various list structures, Schorr & Waite, CACM, 10(8): 501--506, 1967.
    2011 Talk / 2009 Talk
    plus Section 3.0 & 3.1 Myths and Realities: The Performance Impact of Garbage Collection, S. M. Blackburn, P. Cheng, and K. S. McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pages 25--36, New York, NY, June 2004.
    Cas Craven Copying List processing in real time on a serial computer, Baker, CACM, 21(4) 280--294, 1978.
    2011 Talk / 2009 Talk
    plus scanning A nonrecursive list compacting algorithm , Cheney, CACM, 13(11): 677--678, 1970.
    Feb 2 Mrinal Deo MS-Compact Comparison of compacting algorithms for garbage collection , Cohen & Nicolau, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 4, pages 532--553, October 1983.
    2011 Talk / 2009 Talk
    Curtis Dunham Mark-Region Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance, Blackburn & McKinley, ACM Conference on Programming Language Design and Implementation, pages 22--32, Tucson, AZ, June 2008.
    2011 Talk / 2009 Talk
    Feb 9 Curtis Dunham Generational A real-time garbage collector based on the lifetimes of objects, Lieberman & Hewitt, CACM, 26(6): 419--429, 1983.
    2011 Talk / 2009 Talk
    Cas Craven Generation scavenging: A non-disruptive high-performance storage reclamation algorithm, Ungar, ACM Symposium on Practical Software Development Environments, pages 157--167, 1984.
    2011 Talk / 2009 Talk
    discussion Variable Nursery Simple generational garbage collection and fast allocation, Appel, Software--Practice and Experience 19(2):171--183, February 1989.
    Feb 16 Reference Counting (RC)
    Ivan Jibaja Deferred An Efficient Incremental Automatic Garbage Collector, Deutsch & Bobrow, CACM, 19(9): 522--526, September 1976.
    2011 Talk / 2009 Talk
    Na Meng Ulterior Ulterior Reference Counting: Fast Garbage Collection without the Wait, S. M. Blackburn and K. S. McKinley , Proceedings of the ACM 2003 SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pages 344-359, Annehiem, CA, October 2003.
    2011 Talk / 2009 Talk
    Feb 23 Cas Craven RC Cycles Cycle Tracing, Chapter 4, pages 41--56, 2010. From: "Garbage Collection and the Case for High-level Low-level Programming," Daniel Frampton, Doctoral Dissertation, Australian National University.
    2011 Talk / 2009 Talk
    Ivan Jibaja Mark-Copy MC2: High-Performance Garbage Collection for Memory-Constrained Environmentsw, Sachindran, Berger & Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications, pages 81-96, Vancouver, BC, October 2004.
    2011 Talk / 2009 Talk
    Mar 2 Yuhao Zhu Older-First Age-Based Garbage Collection, D. Stefanovic, K. S. McKinley, J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), pages 370--381. Denver CO, November 1999.
    2011 Talk / 2009 Talk
    discussion OF Results Older-first Garbage Collection in Practice: Evaluation in a Java Virtual Machine, D. Stefanovic, M. Hertz, S. M. Blackburn, K. S. McKinley, and J. E. B. Moss, Memory System Performance, Berlin, Germany, pages 175--184, June 2002.
    Mrinal Deo Beltway Beltway: Getting Around Garbage Collection Gridlock, S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss, ACM Conference on Programming Language Design and Implementation, Berlin, Germany, pages 153--164, June 2002.
    2011 Talk / 2009 Talk
    Mar 9 Steve Blackburn Experiments Myths and Realities: The Performance Impact of Garbage Collection, S. M. Blackburn, P. Cheng, and K. S. McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pages 25--36, New York, NY, June 2004.
    Benchmarks The DaCapo Benchmarks: Java Benchmarking Development and Analysis, S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann,, The ACM SIGPLAN Conference on Object Oriented Programming Systems, Languages and Applications (OOPSLA), Portland, OR, pp. 169--190, October 2006.
    2011 Talk / 2009 Talk
    Mar 16 Spring Break no class
    Mar 23 Suman Jana Concurrent MS Multiprocessing compactifying garbage collection, Guy L. Steele, Jr., CACM 18(9): 495-508, 1975.
    2011 Talk / 2009 Talk
    Jason VanFickell Concurrent MS On-the-fly garbage collection: an exercise in cooperation, E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, Communications of the ACM, 21(11):966--975, November 1978.
    2011 Talk / 2009 Talk
    Mar 30 no class
    Apr 6 Jason VanFickell Real Time A Real-time Garbage Collector with Low Overhead and Consistent Utilization,, Bacon, Cheng, and Rajan, ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, pages 285-298, 2003.
    2011 Talk / 2009 Talk
    Suman Jana Correct Derivations Correctness-Preserving Derivation of Concurrent Garbage Collection Algorithms, Vechev, Yahav, and Bacon, ACM Conference on Programmfile:///Users/mckinley/classes/395Tmm/talks/Apr-6-zrays.ppting Language Design and Implementation, Ottawa, Ontario, pages 341-353, 2006.
    2011 Talk / 2009 Talk
    Yuhao Zhu Quantizing Arrays Z-rays: Divide Arrays and Conquer Speed and Flexibility, Sartor, Blackburn, Frampton, Hirzel, and McKinley, ACM Conference on Programming Language Design and Implementation, Toronto, Ontario, Canada, pages 471-482, 2010.
    2011 Talk
    Apr 13 Na Meng Locality The Garbage Collection Advantage: Improving Program Locality Huang, Blackburn, McKinley, Moss, Wang, & Cheng, ACM Conference on Object-Oriented Programming Systems, Languages, & Applications, Vancouver, BC, pages 69-80, October 2004.
    2011 Talk / 2009 Talk
    Suman Jana Conservative MM Garbage collection in an uncooperative environment, H. Boehm and M. Weiser, Software Practice and Experience, 18(9):807-820, 1988.
    2011 Talk / 2009 Talk
    Ivan Jibaja Explicit Parallel MM Hoard: A Scalable Memory Allocator for Multithreaded Applications, E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson, The Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, pages 117--128, November 2000.
    2011 Talk / 2009 Talk
    Apr 20 Yuhao Zhu Memory Leaks Cork: Dynamic Memory Leak Detection for Garbage-Collected Languages,Jump & McKinley, In submission to ACM Transactions on Software Practice & Experience, 2009.
    2011 Talk / 2009 Talk
    Na Meng Leak Pruning Leak Pruning, Bond & McKinley, ACM Conference on Architecture Support for Programming Languages and Operating Systems, Washington, DC, pages 277-288, March 2009.
    2011 Talk / 2009 Talk
    Apr 27 Course evaluation
    Jason VanFickell Free in GC Free-me: A Static Analysis for Individual Object Reclamation, Guyer & McKinley, ACM Conference on Programming Language Design and Implementation, Ottawa, Canada, pages 364-375, June 2006.
    2011 Talk / 2009 Talk
    discussion Garbage collection can be faster than stack allocation, Appel, Information Processing Letters 25(4):275-279, 17 June 1987.
    Mrinal Deo Thoughts A unified theory of garbage collection, Bacon, Cheng, & Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, BC, Canada, pages 50-68, 2004.
    2009 Talk

    Sources for clairification, summaries, and the big picture

    • Wake Up and Smell the Coffee: Evaluation Methodology for the 21st Century, S. M. Blackburn, K. S. McKinley, R. Garner, C. Hoffman, A. M. Khan, R. Bentzur A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann, Communications of the ACM, Research Highlights (Invited), 51(8) pages 83--89, August, 2008. [DaCapo Java Benchmark Suite]

    • Uniprocessor Garbage Collection Technique, Paul Wilson, unpublished.

    • Dynamic Storage Allocation: A Survey and Critical Review, P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles, in International Workshop on Memory Management, Kinross, Scotland, UK, September 1995.

    • Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Jones & Lins, 1999, John Wiley & Sons, Ltd, ISBN 0-471-94148-4.

    Other recommended & potential papers (an incomplete list!)

    • Effective static-graph reorganization to improve locality in garbage collected systems , P. R. Wilson, M. S. Lam, and T. G. Moher. ACM Conference on Programming Language Design and Implementation, Ontario Cananda, pages 177-191, 1991.

    • Fast Allocation and Deallocation of Memory Based on Object Lifetimes , D. Hanson, Software Practice and Experience, 20(1):5-15, January 1990.

    • Remembered sets can also play cards A. L. Hosking and R. L. Hudson. In Proceedings of the ACM OOPSLA'93 Workshop on Memory Management and Garbage Collection Washington, DC, October 1993.

    • A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks, S. Dieckmann and U. Hoelzle, Proceedings of the 13th European Conference on Object-Oriented Programming (ECOOP'99), Lisbon, Springer Verlag, 1999.

    • On the Usefulness of Liveness for Garbage Collection and Leak Detection M. Hirzel, A. Diwan, and A. L. Hosking, European Conference on Object Oriented Programming, Budapest, Hungary, pages 181-206, June 2001.

    • Efficient representations and abstractions for quantifying and exploiting data reference locality, Chilimbi, ACM Conference on Programming Language Design and Implementation, Snowbird UT, pages 191--202, 2001.

    • Cache-Conscious Structure Layout, T. M. Chilimbi, M. D. Hill, J. R. Larus, ACM Conference on Programming Language Design and Implementation (PLDI), Atlanta, GA, pages 1--12, June 1999.

    • Using generational garbage collection to implement cache-conscious data placement, T. Chilimbi and J. R. Larus, Proceedings of the International Symposium on Memory Management, Vancouver, British Columbia, Canada, pages 37--48, 1998.

    • Composing High-Performance Memory Allocators, E. D. Berger, B. G. Zorn, and K. S. McKinley, Proceedings of the SIGPLAN 2001 Conference on Programming Language Design and Implementation, Salt Lake, UT, June 2001.

    • In or Out? Putting Write Barriers in Their Place, S. M. Blackburn and K. S. McKinley , International Symposium on Memory Management (ISMM), Berlin, Germany, June 2002.

    • Error-Free Garbage Collection Traces: How to Cheat and Not Get Caught, M. Hertz, S. M. Blackburn, K. S. McKinley, J. E. B. Moss, and D. Stefanovic, Proceedings of the International Conference on Measurement and Modeling of Computer Systems, Marina Del Rey, CA, June 2002.

    • Reconsidering Custom Memory Allocation, Emery D. Berger, Benjamin G. Zorn, and Kathryn S. McKinley, OOPSLA 2002: ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, pages 1--12, Seattle, WA, USA, November 2002.

    • Connectivity-Based Garbage Collection M. Hirzel, A. Diwan, and M. Hertz. Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), October 2003.

    • Using key object opportunism to collect old objects, B. Hayes, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Phoenix AZ, pages 33--46, 1991.

    • Pretenuring Pretenuring for Java, S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinley, and J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), Tampa Bay FL, pages 342--352, October 2001.

    • An on-the-fly Mark and Sweep Garbage Collector Based on Sliding Views, H. Azatchi, Y. Levanoni, H. Paz, and E. Petrank, Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'03), October 2003.

    • Concurrent Cycle Collection in Reference Counted Systems, Bacon & Rajan, Proceedings of 15th European Conference on Object-Oriented Programming, Budapest, Hungary, Lecture Notes in Computer Science 2072, Springer-Verlag, June 2001, pages 207--235.

    • An On-the-fly Reference Counting Garbage Collector for Java, Y. Levanoni and E. Petrank. An abbreviated version ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, October, 2001.

    • A Practical Flow-Sensitive and Context-Sensitive C and C++ Memory Leak Detector, D. L. Heine and M. S. Lam, Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), June 2003.

    • Oil and Water? High Performance Garbage Collection in Java with MMTk Blackburn, Cheng, & McKinley, ACM International Conference on Software Engineering, pages 137-146, Scotland, UK, 2004.

    • Demystifying Magic: High-level Low-level Programming, Daniel Frampton, Stephen M. Blackburn, Perry Cheng, Robin Garner, David P. Grove, J. Eliot B. Moss & Sergey I. Salishev. ACM International Conference on Virtual Execution Environments, Washington DC, March 2009. (To appear.)

    • Real Time Tax-and-spend: democratic scheduling for real-time garbage collection, Auerbach, Bacon, Cheng, Grove, Biron, Gracie, McCloskey, Micic, and Sciampacone, ACM International Conference On Embedded Software, Atlanta, GA, pages 245-254, 2008.
    Kathryn S. McKinley