Why You Should Be Excited About Garbage Collection in Ruby 2.0

http://patshaughnessy.net/2012/3/23/why-you-should-be-excited-about-garbage-collection-in-ruby-2-0#

by DavidChouinard • 14 years ago

106 35 14 years ago

xenophanes• 14 years ago

So what's REE's solution and how does it differ from this approach?

REE developer here. REE's solution is almost the same. Except we don't align heaps; we identify the containing heap using binary search instead.

subwindow• 14 years ago

Not really excited. Sorry. To me this is an incremental improvement to a method of GC that is just not going to cut it.

Rubinius uses Generational GC. There are definitely some parts of Rubinius that are (currently) slower than MRI, but memory management stands to be one of places where Rubinius will demolish MRI in the long-run.

JRuby/JVM uses (from what I understand) a Generational-first hybrid GC. There's been so much work and analysis done on the JVM that there's no way in hell any mark and sweep GC is going to compete.

Honestly if MRI is going to remain competitive it needs to completely rethink the way it does GC.

bluemoon• 14 years ago

Jruby seems like it has the most potential in the GC department. It seems like most of the interesting GC papers I've seen are work that's been done on the JVM.

jacaetevha• 14 years ago

And (IIRC) much of the JVM's GC and VM work came directly from the Smalltalk world and the Strongtalk guys.

ajasmin3• 14 years ago

How do other garbage collectors handle this?

Can I fork a Java or V8 process and take advantage of the copy-on-write optimization?

oconnore2• 14 years ago

Most [1] modern GC implementations use generational copying collectors. A copying GC does not need to maintain a bit for each allocated object, and therefore will not break copy-on-write.

They are also much faster for many common loads.

[1] I suppose this is debatable. Oddly, many modern scripting languages use ancient compiler technology for no discernible reason. See also: the GIL.

ajasmin3• 14 years ago

Can't we get into problems with heap compaction though? It seems that modern GCs try to keep the heap tidy by moving objects around.

ootachi4• 14 years ago

I have a theory, which has so far held up [1], that every remotely popular language that needs automatic storage reclamation ends up growing a generational and incremental/concurrent collector, either in its main branch or in a fork [2]. It's just a matter of time. Efficient automatic storage reclamation is hard.

[1] Language developers sometimes claim they don't need it. I believe they're on the wrong side of history.

[2] Forks are common for this, and for good reason; often times languages that start with reference counting end up taking large dependencies on external libraries that manipulate reference counts (like Python with its Py_INCREF and Py_DECREF), at which point the language can't fully move to tracing GC without breaking its ecosystem.

masklinn• 14 years ago

> Oddly, many modern scripting languages use ancient compiler technology

Historical: most of them are 10~20 years old, "new compiler technologies" had not trickled down much when they were created and they had no real need for the things those provided (not to mention they have drawback, a GIL has better single-threaded performances than fine-locking which is important when single-treaded is your primary workload).

Also manpower, probably, it's harder to implement a generational concurrent GC than a refcounting or a basic M&S, and it's even harder to retrofit that into an existing codebase (hence pypy having pluggable GC backends and defaulting to a hybrid GC)

FooBarWidget3• 14 years ago

What? A copying GC copies objects and therefore inherently breaks copy-on-write.

jbellis• 14 years ago

Wake me up when they add compaction.

http://en.wikipedia.org/wiki/Fragmentation_(computing)#Memor...

(CPython has this weakness too. http://www.slideshare.net/jbellis/pycon-2012-what-java-can-l...)

pkulak• 14 years ago

I was expecting a lot more. It's still just mark and sweep, which is old news.

txttran• 14 years ago

it took 3+ years to develop this technique? it seemed like the most straightforward approach to the problem.

silentbicycle3• 14 years ago

Second most straightforward, perhaps. They previously had the bit for marking inside objects, rather than on a separate memory page of just mark bits, which interacts poorly with copy-on-write.

riffraff• 14 years ago

Narihiro Nakamura did a lot of hacking on the ruby GC ("longlife" used in twitter's Kiji, parallel marking, lazy sweeping, bitmap marking).

It's nice to see more of it ending up in the ruby mainline.

cpr• 14 years ago

Gosh, I hate to be that "old guy," but using bitmaps for mark & sweep GC dates from the early 70's.

In particular, in GC implementations for Lisp and Lisp-like languages (such as the ECL implementation we used at Harvard in the mid-70's) where CONS cells were two eighteen-bit halfwords (CAR and CDR) fitting in a 36-bit word, there was no place for mark bits, so you'd use a bitmap instead (as rediscovered here).

And we used the same technique for finding the page headers (e.g., containing the mark bitmaps) for each part of the heap, aligning to a larger power of two so you could chop any pointer down by and'ing off the lower bits to get to the page header.

There really ain't much new under the sun. Too bad every generation has to rediscover all this stuff.

silentbicycle3• 14 years ago

Indeed - information about good garbage collectors is readily available. Paul R. Wilson's "Uniprocessor Garbage Collection Techniques" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2...) is an excellent survey, and Jones, Hosking, and Moss's _The Garbage Collection Handbook_ is an excellent reference. (The previous book by Jones and Lins is also great, but the new one adds important material on concurrent GCs, real-time GC, and interactions between the GC and runtime systems.)

As an exercise, I wrote a simple standalone mark-bit-page & lazy sweeping garbage collector for C. (https://github.com/silentbicycle/oscar) Marking occurs in a user-provided callback, since I don't assume any particular data structure. It's only ~300 LOC.

gruseom• 14 years ago

That's a great name for a garbage collector :)

joblessjunkie• 14 years ago

I don't think this is rediscovery. These things just take time to implement. Ruby hasn't been around all that long.

true_religion• 14 years ago

Ruby has been around since 1995. That's over 15 years.

Implementing bitmaps for mark-and-sweep a project well within the skills of a final year undergrad, or first year graduate student of CS.

You can say many things, but I doubt they didn't implement this because they didn't have time, or didn't have the skills to do so. They merely prioritized against it from day-one.

kbd• 14 years ago

Ruby is almost 20 years old...

Fluxx• 14 years ago

> Too bad every generation has to rediscover all this stuff.

Even though this technique existed 30 years ago, doesn't mean that it's been recently "rediscovered" by the Ruby folks and excitedly implemented to the musings of, "how did we miss this technique?!?" There are likely lots of reasons why this wasn't used before. The abstract of their paper seems to shed some light on this:

[...]But Ruby interpreter runs on various platforms, and we do not have portable memory allocation API to obtain aligned memory region without wasting region. In this paper, we propose portable scheme to map from object pointers to corresponding bitmap table in constant time.[...]

I may be totally wrong, and the paper is entirely in Japanese, but I think there is more to it.

verelo• 14 years ago

"Excited about Ruby" is something that I cant say I've ever been. Still...

Why You Should Be Excited About Garbage Collection in Ruby 2.0

Related Stories