improvements to Ruby’s GC algorithm
I first came across Narihiro Nakamura’s name while researching an article about garbage collection I wrote back in March. He had just committed a large code change to the upcoming MRI Ruby 2.0 release enabling a new garbage collection technique called “bitmap marking,” which promises to speed up your apps by improving the way Ruby processes work with shared memory. Later I watched a video of a great presentation Narihiro did at RubyConf Argentina 2011 called Parallel worlds of CRuby’s GC about a garbage collection technique called “parallel marking.” Then I noticed on his web site that Narihiro had committed various other GC related code changes to Ruby over the past few years. It was clear that garbage collection has been an ongoing passion for Narihiro – a passion that benefits all of us!
This month I decided to interview Narihiro for RubySource – I was curious to learn more about him and his work. Because of the language barrier we conversed via email, unlike my other RubySource interviews, but I’ve included his original Japanese answers here for those of you who understand Japanese. Read on to learn more about Narihiro, and to get a sense of all the improvements Narihiro and the core team have made to GC over the past few years.
Who is Narihiro Nakamura?
Q: Hi Narihiro, thanks so much for your time. How are you?
Hi – no problem at all… I’m doing great!
Q: こんにちはNarihiro、お時間をいただきありがとうございます。お元気ですか？
こんにちは、いえいえ問題ないですよ。元気です！
Q: Can you tell us a little about yourself? Where you are from? Where do you work? What are you interested in beyond Ruby?
I currently live in the Shimane Prefecture, Japan. Oh, by the way, the RubyWorld conference will be held here on November 8-9. We hope all of you can come and join us!
I work at NaCl (Network Applied Communication Laboratory Ltd.). Six Ruby core committers work here, including Yukihiro Matsumoto.
Umm… beyond Ruby? Well, I’m really interested in garbage collection. And, of course, I also like Ruby because it has its own garbage collector.
Q: あなた自身について少し教えていただけますか？ どこ出身ですか？ あなたは、どこで働いています？ 何かRubyを越える興味を持っていますか？
今は日本の島根県に住んでいます。 今度の11月に島根ではRubyWorldConference というイベントがあるのでぜひみなさんいらっしゃってください！
NaCl（Network Applied Communication Laboratory Ltd.）で働いています。 この会社にはMRIのコミッターが6人もいます。 世界でもっとも多くのRubyコミッタが働いている会社ですね。そして、そのうちの一人が@yukihiro_matzです。
beyond Ruby. GCには興味があります！ でも、Rubyも好きですよ。 だって自前のGCを持っているじゃないですか。
Q: Who are the other 5 Ruby committers at NaCl?
Shugo Maeda, Shyouhei Urabe, Yuuzou Gotou, Koji Takao, and me :)
Q: NaClの他の5人のコミッタは誰ですか？
Shugo Maeda, Shyouhei Urabe, Yuuzou Gotou, Koji Takao, and me :)
Q: How did you first get involved with Ruby?
I first got involved with Ruby about five years ago when I came across some articles on the web about Ruby. I was also inspired by Kakutani Shintaro’s From Java to Ruby talk – it made me believe that Ruby was here to stay. Then I started coding in Ruby as a hobby.
Q: Rubyとの最初の出会いは？
5年以上前にRailsの記事をWEBページ上で読んだのが最初のきっかけだと思います。 そのあと、@kakutaniの『JavaからRubyへ』を紹介している動画を見て「これからRubyだ！」と思いました。 そして趣味でRubyプログラミングをはじめました。
Q: How did you decide to work on garbage collection?
The Ruby Hacking Guide, my favorite book, states that one of Ruby’s weak points is GC performance. When I read this I thought: “Maybe I can take care of that.” Since I’ve never been formally educated in garbage collection algorithms, I had to learn about it on my own. Now I want to apply what I’ve learned to improve MRI’s garbage collector.
Q: どのようにしてGCの研究をやることを決めたのですか？
Ruby Hacking Guideというわたしの好きな本がありまして、この最後の方の『Rubyの解決すべき課題』として『GCの性能』が上げれていて、「じゃあわたしがやろう」と思ったのがきっかけです。 私は大学などで専門の教育を受けていないので、独学でGCの知識を深めています。 私が学んだことをMRIのGCに生かしていきたいですね。
Q: What is it like working with the Ruby core team?
The members of the Ruby core team are all very unique and cool people. I respect them and I’m really honored to work with them.
Q: Rubyのコアチームと一緒に仕事をするのはどんな感じですか？
Rubyのコアチームは個性的ですごい人たちです。 とても尊敬していますし、そのような方々と一緒にMRIの開発ができることを光栄におもいますよ。
Q: Can you think of a funny or interesting story about working with the core team that readers would enjoy?
Oh, please see the joke category of Ruby’s Redmine. I highly recommend “Compress a sequence of ends”.
Q: コアチームとの仕事で、楽しい・興味深い話がありますか？
RubyのRedmineのJokeカテゴリを見てみてください。私のオススメは「Compress a sequence of ends」です :)
Why learn about garbage collection?
Q: At first glance, GC seems like a boring topic. Why should the rest of us be interested in it?
The purpose of garbage collection is to free up unused memory segments. This seems to be a very easy and straightforward task, but actually it’s very difficult. There is no perfect solution. But that’s what makes it interesting to me. Since most programmers like the challenge of difficult problems, they will certainly enjoy GC.
Also, many GC algorithms were invented by legendary hackers: John McCarthy, Edsger Wybe Dijkstra, Donald Ervin Knuth, and of course our own “Matz.” GC has attracted the attention of even legendary hackers.
Q: 一見したところ、GCは退屈なトピックのように思えます。なぜ私たちの以外の人々 – 読者 – はGCに興味をもつべきなのでしょうか？
GCは「自動で利用していないメモリ領域を解放する」という単純なミッションに見えるにも関わらず、それを解決しようとなると大変に難しい問題になってしまうところが面白いですね。 プログラマは本質的に難しい問題が好きだと思います。きっとGCも気に入るでしょう。
また、いくらかのGCアルゴリズムは伝説的なハッカーたちによって作られています。 たとえばJohn McCarthyやEdsger Wybe Dijkstra、Donald Ervin Knuth、そしてまつもとさん。 彼らのような偉大なハッカーでさえも巻き込んでしまうような魅力をGCは持っていると思います。
Q: Should Ruby developers think about GC when they are writing their code? Or just assume that it will happen “magically?”
One goal of garbage collection is to function properly even if people don’t pay any attention to it. If a developer thinks of garbage collection as “magic” and nothing bad happens, then it is working as intended – and the GC system’s author will be happy. However, in a practical application you sometimes need to worry about GC, for example when an application requires smooth execution without pauses.
Q: Ruby開発者はコードを記述しているときGCのことを考えるべきでしょうか？ それてもただ「魔法のようなこと」が起こると思うだけでいいでしょうか？
「開発者にGCを気づかせなくてもよい状態」がGCのひとつの目標です。 なのでGCが単に「魔法」と思われていて、問題が起きていないなら、それはGCがうまく作れている証拠ですので、これほど嬉しいことはありません。 ただし、とりわけ実践的なアプリケーションでは、GCについて考えなければならないでしょう。 たとえば、停止時間にシビアなアプリケーションなどです。
A Quick Tour of GC Innovations
Q: What does “Mark and Sweep” mean?
Before I explain Mark and Sweep (M&S), let me first explain a few basic GC concepts. A garbage collector’s basic task is to collect all dead objects. A dead object is an object that is never referenced by the program.
M&S is one of many GC algorithms. All Mark and Sweep GC systems have two separate phases: the mark phase and the sweep phase.
- In the mark phase, the collector marks live objects objects that are still referenced by program code.
- In the sweep phase, it scans the entire heap and “sweeps” away “dead” (unmarked) objects.
Q: マークアンドスープとはどういう意味ですか？
まずはGCの簡単なコンセプトを説明させてください。 GCとはすべての死んだオブジェクトを回収するものです。 死んだオブジェクトとは、プログラムから二度と参照できなくなったオブジェクトを指します。
そして、マークアンドスイープ（M&S）はGCのアルゴリズムの一種で、処理はマークフェーズとスイープフェーズに別れています。 マークフェーズでは生きているオブジェクトに印を付けていきます。 スイープフェーズではヒープ全体をスキャンし、死んでいる（マークされていない）オブジェクトを開放します。
Q: How does the GC system know which objects are currently referenced by the program during the mark phase?
The GC system can find live objects by traversing a set of pointers (e.g. to Ruby’s local variables, global variables, etc…) that directly reference objects in the program.
Q: GCはマーク時にどのようにしてプログラムからオブジェクトが参照されているということを知りますか？
GCはプログラム中からオブジェクトを直接参照するポインタの集合（例えばRubyのローカル変数やグローバル変数…）をトラバースすることで、生きているオブジェクトを知ります。
Q: What does “Lazy Sweep” mean? How is it different from Mark and Sweep?
Since traditional M&S GC systems execute mark and sweep in one single, atomic operation, the application will pause while garbage collection is in progress.
In Lazy sweeping, sweeping is lazy. Each invocation of the object allocator sweeps Ruby’s heap until it finds one appropriate free object and then returns. This improves the response time of GC; i.e. the worst case running time of the garbage collector decreases.
Q: “遅延スイープ”とはどういう意味ですか？ マークアンドスイープとどのように違いますか？
従来のM&S(マークアンドスープ)ではマークとスイープがatomicallyに実行されます。 そして、GCの間、Rubyアプリケーションは止まってしまいます。
LazySweepingでは、スイープを遅延しておこないます。 オブジェクトアロケーションのタイミングで、適切な死んだオブジェクトを見つけるまでsweepをおこないます。 LazySweepingによって、GCのレスポンスタイムが向上、つまり、GCによる最悪停止時間が減ります。
Q: But the Lazy Sweep GC algorithm still needs to mark all the objects? The mark phase is still the same? The only difference is that the sweep phase is faster?
This is right. However, the throughput of the sweep phase doesn’t decrease, because Lazy Sweeping just amortizes the cost of sweeping by having the allocator perform the sweep.
Q: LasySweepアルゴリズムでもぜんぶのオブジェクトはマークしないといけないんですよね？ マークフェーズは依然として同じですか？ スイープフェーズが速くなったのが唯一の違いですか？
そうですね。ただし、アロケータでスイープさせることによってスイープのコストを分割しているだけなので、スイープフェーズのスループットは減少しません。
Q: What is the “Long Life GC” patch?
The “Long Life GC” patch treats long-life objects as a special case. it’s similar to Generational GC. However, The patch is not in use in any current Ruby version.
Q: “長寿命GC”パッチとは何ですか？
これは長寿命のオブジェクトを特別扱いするもので、世代別GCに似たようなものです。 ただ、LongLifeGCはRuby 1.9.2でrejectされていることに注意してください :)
Q: What is “Parallel Marking?”
The Parallel Marking collector runs several marking processes in parallel by using native threads. This might improve your performance if you use a multi-core machine.
This might sound easy, but is in fact a very difficult and complex process.
Please see my presentation Parallel Worlds of CRuby’s GC
if you are interested.
Q: “並列マーキング”とは何ですか？
Parallel Marking collectorはマーク処理を複数のネイティブスレッドで実行します。 複数のCPUコアを持っているマシンで幸せになれるでしょう。
簡単に実装できると思われるかもしれませんが、意外と面倒で奥が深いです。 詳細が知りたい方は[私のスライドを参照してください。
Q: What is the “Heap Subdivision Patch?”
What a fond memory! The “Heap Subdivision Patch” was my first contribution for MRI GC.
In Ruby 1.8.x, when extending the heap we allocated a new contiguous memory block of 1.8 times the size of the old heap. In this approach, we couldn’t free up a large block if it had even one live object. My “Heap Subdivision Patch” divides the contiguous block into sub-blocks. This patch increases chances of freeing dead sub-blocks, which again improves GC performance.
Q: “ヒープ細分パッチ”とは何ですか？
懐かしい！ これは私が一番最初にMRIにコントリビュートしたパッチですね。
Ruby1.8ではヒープを拡張時に拡張前のヒープサイズの1.8倍の連続したメモリのブロックを確保していました。 このアプローチでは、ブロック内に1つでも生きているオブジェクトがあればそのブロックは解放してはいけませんので、巨大なブロックはいつまでも解放されません。
「Heap Subdivision Patch」ではブロックを小さく分割して確保するようにしました。 分割されたブロックは大きなブロックに比べて解放されやくなります。
Q: What is “Bitmap Marking?”
In Bitmap Marking, the “live object” flags are stored in a separate bitmap table, instead of in each objects header. Oh, I think your article is the best source of information for this topic!
Q: “Bitmap Marking”とは何ですか？
Bitmap Markingではマークビットを、オブジェクトヘッダではなく、ヒープと別の空間のビットマップテーブルで保持し、ビットマップに対してマークをおこなうアルゴリズムです。あ、このトピックについてはあなたの記事が最高の情報だと思います！
Q: Thanks Narihiro! Are there any other GC innovations you want to mention?
Recently, I have been looking into the G1GC garbage collection algorithm used in OpenJDK7. This can control the maximum pause time of GC operations. Also, I have an interest in C4 by Azule. This algorithm achieve pauseless garbage collection by utilizing special CPU instructions. It’s fun!
Q: あなたが言及したい他のGCの技術革新はありますか？
ずっと調べてきたのはOpenJDK7に入ったG1GCですね。 これはGC停止時間を指定できるというアルゴリズムです。
また、AzuleのC4も注目しています。 こちらはハードウェアサポートによって無停止GCを実現しています。 面白いですよ！
The future of GC
Q: What is coming next for Ruby GC?
First, I plan to introduce several small fixes to M&S – for example, non-recursive marking, and a prefetching marking loop. And I’d like to refactor gc.c to make it easy to implement small fixes like these. Then, I plan to implement the parallel marking patch that I mentioned previously.
Q: 次はRubyのGCに何が入るでしょう？
M&Sに対して細かい修正を入れていきたいと思っています。 例えば、非再帰的マーキング、とprefetchを使ったマーキングです。 あとはgc.cをリファクタリングして、上記のような小さな修正をとりこみやすくしたいですね。
その後に、並列マーキングを取り込みます。
Q: Can MRI Ruby learn anything from JRuby, Rubinius or other versions of Ruby?
JRuby uses the JVM’s GC. I envy it :) And whenever I read Rubinius’s GC source code, I’m always surprised how beautiful the code is.
I think MRI’s garbage collector lags behind a bit when compared to other GC implementations. For historical reasons, most of which relate to Ruby’s C extensions, it is hard to change this situation substantially. However, I hope to do something about this.
Q: MRIのRubyは、JRuby、RubiniusのやRubyの他のバージョンから何かを学ぶことができますか？
JRubyはJVMのGCを使っていますからね。うらやましいな、と思います :) RubiniusのGCは以前読んだときにかなりきれいに書かれていて驚きました。
MRIのGCは他のバージョンのGCに比べて劣っていると思います。 ただ歴史的な理由から（主にC拡張ライブラリの仕様によって）、MRIのGCの大きな変更は難しいんですよね。これはどうにかしたいです。
Q: What else are you working on that you’d to tell everyone about?
I recently wrote a book! Dissecting G1GC’s implementation …sorry, it’s only in Japanese.
Q: その他になにかみんなに伝えるべき取り組みがありますか？
電子書籍を書きました！ 徹底解剖G1GC: 実装編
Q: What are your future plans?
I have no specific plans… but I want to continue improving Ruby’s GC algorithm little by little.
I’d like to acknowledge my colleague Mr. Tor, who helped me translate these answers into in English. Thanks!
Q: あなたの将来の計画は？
将来のことは考えていませんが、GCの取り組みはコツコツと続けたいです。
Pat ShaughnessyPat Shaughnessy writes a blog about Ruby development and recently self-published an eBook called Ruby Under a Microscope. When he's not at the keyboard, Pat enjoys spending time with his wife and two kids. Pat is also a fluent Spanish speaker and travels frequently to Spain to visit his wife's family.
