Browse Prior Art Database

Optimistic write barrier removal with zero overhead in a generational garbage collector

IP.com Disclosure Number: IPCOM000191611D
Original Publication Date: 2010-Jan-08
Included in the Prior Art Database: 2010-Jan-08
Document File: 4 page(s) / 31K

Publishing Venue

IBM

Abstract

Disclosed is an optimization for a generation garbage collector which allows write barriers to be removed for writes to recently allocated objects. Recently allocated objects are identified on the stack using metadata, and are automatically remembered by the garbage collector.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 4

Optimistic write barrier removal with zero overhead in a generational garbage collector

Disclosed is an optimization technique for a generational garbage collector. The disclosed technique may be a part of certain computer programs. The optimization disclosed provides a capability for "write barriers" to be optimistically removed, and introduces zero overhead into

program execution and only a negligible overhead into the garbage collector.

Generational garbage collectors traditionally require a write barrier that checks to identify every time a reference to a 'new' object is written into an 'old' object [1]. The references must be 'remembered'. The runtime system must make a trade-off in which the write barrier reduces throughput by increasing the typical path length, but the presence of a remembered set allows the garbage collector to operate much more efficiently. In most applications this trade off leans towards greater overall throughput. Throughout may be further improved if the barrier can be avoided in some circumstances. Omitting the write barriers would result in smaller compiled code and shorter code paths at runtime.

A common opportunity for removal of a write barrier occurs is a store operation into a newly allocated object. Only references from old objects to new objects must be saved. When an object has just been allocated, a presumption exists that the object must be in new space and barriers for store operations into that object may be omitted.

For example in the following Java code snippet,

Book dh = new Book();
dh.title = new String("Harry Potter and the Deathly Hallows"); dh.author = new String("J.K. Rowling");
dh.

published = new Date(2007);

pages = new Integer(784);

 dh is a newly allocated object. If dh is in a new space, barriers for the four writes (into title , author ,

published

      , or tenured) due to garbage collection activity occurring between the allocation and the assignments. Alternatively, the object may, in some unusual circumstances, be allocated directly in an old space. For example, an old space allocation may occur when the system is very low on memory, or if the object is unusually large.

Researchers, for example Urs Hölzle [2], have proposed techniques to optimize write barriers by making them faster. Other researchers have proposed techniques to remove write barriers in certain cases, for example Karen Zee [3], Martin Vechev [4] or Krishna Nandivada [5].

Zee's proposal for "optimistic write barrier removal" is particularly interesting, because the situation is similar to the situation of the current disclosure. Zee describes a system where

d

dh.

and

pages

) are not necessary.

However a runtime system cannot safely assume dh is in a new space. Even if dh was initially allocated in a new space, it is possible, although unlikely, that dh was moved to an old space (

promote

1

Page 2 of 4

setting a bit in the header of the object identifies newly allocated ob...