Home

Generational Real-time Garbage Collection

Generational Real-time Garbage Collection: A Three-part Invention for Young Objects, Daniel Frampton, David F. Bacon, Perry Cheng, David Grove. ECOOP 2007.

While real-time garbage collection is now available in production virtual machines, the lack of generational capability means applications with high allocation rates are subject to reduced throughput and high space overheads.

Since frequent allocation is often correlated with a high-level, object-oriented style of programming, this can force builders of real-time systems to compromise on software engineering.

We have developed a fully incremental, real-time generational collector based on a tri-partite nursery, which partitions the nursery into regions that are being allocated, collected, and promoted. Nursery collections are incremental, and can occur within any phase of a mature collection.

We present the design, mathematical model, and implementation of our collector in IBM's production Real-time Java virtual machine, and show both analytically and experimentally that the collector achieves real-time bounds comparable to a non-generational Metronome-style collector, while cutting memory consumption and total execution times by as much as 44% and 24% respectively.

Since the last post on GC was so popular, I figured I should post another one. The next few days I'll probably post links to a subset of the papers presented at ECOOP that a) I saw the talk for, and b) I found particularly striking from a language design POV.

By neelk at 2007-08-12 16:38 | Implementation | other blogs | 19951 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The next few days I'll

The next few days I'll probably post links to a subset of the papers presented at ECOOP that a) I saw the talk for, and b) I found particularly striking from a language design POV.

Great!

I am not really into GC at the moment, so I'll leave that for others to comment on...

By Ehud Lamm at Sun, 2007-08-12 16:47 | login or register to post comments

Besides Java, what VMs / languages have real-time GC?

By "real time" I mean "incremental," not just generational (where you still have to scavenge all generations at some point). The Lisps and Smalltalks I've looked at don't, nor does Erlang, nor OCaml. Erlang's GC is incremental in the sense that each process has its own heap, which tends to cut down on overall GC pauses.

By James Hague at Mon, 2007-08-13 15:13 | login or register to post comments

Squeak (mostly), Io, Lua,

Squeak (mostly), Io, Lua, etc.

Squeak uses a mix of generational/mark and sweep to avoid long GCs, Io uses an incremental (Baker's treadmill) GC, and Lua switched to an incremental GC around v 5.0.

By Gavin Harrison at Mon, 2007-08-13 15:41 | login or register to post comments

libgarbagecollector

Io uses libgarbagecollector, which despite claims, is not incremental. For example, at the end of a collection it performs a loop over each white object, calling its finalizer.

By James McCartney at Mon, 2007-08-13 16:37 | login or register to post comments

By real time, I mean HARD real time

This collector is a hard real time collector, with max 1 millisecond pauses and 70% MMU (ie, in every ten millisecond period at least seven will be used by the program and not the collector).

That said, incremental collectors can't be that uncommon, can they? I mean, they're in Jones's and Lins's book.

By neelk at Mon, 2007-08-13 15:42 | login or register to post comments

SuperCollider

SuperCollider implements the Johnstone-Wilson real time collector.

By James McCartney at Mon, 2007-08-13 15:47 | login or register to post comments

O'Caml

O'Caml's GC is incremental in its second generation. This does not make it real-time but good enough for many applications with soft real-time demands.

By Mattias Engdeg at Wed, 2007-08-15 19:53 | login or register to post comments