This is an archived version of CCC's website. Please visit the new ccc website for the latest information.

Relevant Links

Research Papers


Memory Management, Garbage Collection, Algorithms


feed icon

feed icon

feed icon


Next Generation Automatic Memory Management

Modern object-oriented programming languages such as Java, JavaScript, Ruby, and C# are becoming ubiquitous. A primary reason for this trend is that these languages provide automatic memory management (garbage collection), which relieves programmers of the burden of explicitly freeing memory that is no longer needed. Professor Kathryn McKinley at the University of Texas at Austin has led an NSF-funded research project, in collaboration with Steve Blackburn at the Australian National University, that is exploring how to build the software infrastructure that executes managed programs, i.e., programs in languages that provide automatic memory management. Garbage collection provides a number of software engineering benefits such as preventing common programmer memory errors that are among the most difficult to diagnose and fix. However, in the past, programs in garbage collected languages tended to be slower.

The garbage collector makes a classic time-space tradeoff that seeks to provide space efficiency, fast reclamation of objects no longer in use, and fast run-time performance by packing contemporaneously-allocated objects together in space. The three canonical tracing garbage collectors: semi-space, mark-sweep, and mark-compact each sacrifice one of these objectives. Our team invented a garbage-collector family, called mark-region. Mark-region is the first new memory organization proposed for memory management in over 25 years.

The PIs also introduced opportunistic defragmentation, which mixes copying and marking in a single pass. Combining both, we implement immix a novel high performance garbage collector that achieves all three performance objectives. The key insight is to allocate and reclaim memory hierarchically at a coarse block grain when possible and otherwise divide blocks in to finer grain lines, similar to pages and cache lines in hardware memory systems. It is shown that immix outperforms existing canonical algorithms, improving total application performance by 7 to 25% on average across 20 benchmarks. As the mature space in a generational collector, immix matches or beats a highly tuned generational collector, e.g., it improves SPECjbb200 by 5%. These innovations and the identification of a new family of collectors open new opportunities for garbage collector design.

Kathryn McKinley (University of Texas at Austin)
Stephen M. Blackburn (Australian National University)

Agencies (that have supported the research):
National Science Foundation, University of Texas at Austin


Current Highlight | Past Highlights

Computing Research Highlight of the Week is a service of the Computing Community Consortium and the Computing Research Association designed to highlight some of the exciting and important recent research results in the computing fields. Each week a new highlight is chosen by CRA and CCC staff and volunteers from submissions from the computing community. Want your research featured? Submit it!.