言語別GCの仕組み

Question

ある質問のある回答で、JavaやC#が参照カウントを使用していると言うのがありました。しかし、私の記憶では、JavaやC#は参照カウントは使用していなかったと思います。色々調べましたが、公式または(個人ブログとかじゃない)信頼できる準公式な情報がうまく見つからず、わからない状態です。

そこで、参照カウントの有無やGCの種類をまとめたいと思っています。それぞれの言語について情報(公式なドキュメント、信頼できる企業・団体のサイト、多数の技術者によってメンテナンスされているWikiなど)を知っている方は教えていただけませんか？ 公式のみだと情報が少なくなりそうなので、この際、個人ブログ等でもかまいません(ただし、参考資料扱いにさせていただきます)。

【言語/実装別GC一覧】

言語	参照カウント	GC
C	×	×
C++(スマートポインタ)	○	×
D	不明	世代別GC
Go(gc)	不明	よくわからない、解説求む
Go(gccgo)	不明	未実装?
Rust	○	×
Swift	○	×
Haskell(GHC)	不明	世代別GC?
Java(Oracle)	不明	世代別GC+コンカレントGC+G1
Java(OpenJDK)	不明	不明
C#(.NET Framework)	×	世代別GC
C#(Mono)	不明	不明
Erlang	不明	インクリメンタルGC?
Perl5	○	×
Perl6(MoarVM)	不明	世代別GC
Python(CPython)	○	世代別GC
PHP	○	M&S
Ruby(MRI)	×	世代別GC+インクリメンタルGC
JavaScript(V8)	○?	M&S?
JavaScript(SpiderMonkey)	○?	M&S?
JavaScript(JavaScriptCore)	○?	M&S?
JScript(Chakra)	○?	M&S?

※ __斜体__はよくわかっていない部分です。
※ 循環参照も確実に回収できる方式をGCとしています。よって、スマートポインタはGCではありません。
※ 各言語は最新バージョンが対象です。なお、Python2とPython3は同じのようです。PHPにGCが追加されたのは5.3からです。RubyはRubyはM&S→世代別GC→インクリメンタルGCと進化して行っています。
※ 実装は明記されていない限り各言語の公式なものとします。
※ JavaはJava仮想マシン、C#は.NET Framework/Mono依存の可能性があります。ScalaやKotlin、F#やVB.NETについても情報があれば教えて下さい。
※ MozillaにJavaScriptにおけるメモリ管理のドキュメントがありますが、概要だけではっきりしません。
※ その他、この言語はこれを使っているという情報があれば教えて下さい。
※ Java8にはインクリメンタルGCもあるようですが、非推奨になっています。
※ Rustの参照カウントは標準ライブラリとして提供されます。
※ MoarVMはPerl6のVM。RakudoもMoarVMを使っているはず。

間違い等があれば、ご指摘下さい。「無い」ことを証明するのは悪魔の証明になり得るため、しばらくして指摘が無ければ、不明部分は「×」にしていきたいと思います。世代数も調べていった方が良いかちょっと悩んでいます(世代別GCでは無い場合は1世代しかないという扱いをするとか)。

【用語集】

• 参照カウント: オブジェクトへの参照数をカウントしていき、0になれば即座に削除される方式。実装が単純で高速だが、多数の小さなオブジェクトを生成・破棄する場合はオーバーヘッドが大きくなる。また、循環参照は回収できないという致命的な欠点があるため、これだけではGCとは言えない。
• GC: ガベージコレクション。ゴミ収集。不要になったオブジェクトを破棄する機能。
• M&S: マーク・アンド・スイープ。ルートオブジェクトから一つ一つ使っているかどうかマークをしていき、マークが無い物をまとめて回収する方式。循環参照を回収するための最も単純なGC。マークを付けるときに全体を停止(STW)する必要がある。
• コピーGC: マークするのでは無く、別の領域にコピーしていく方式。コピー自体が遅く、二倍弱のメモリが必要になる。
• 世代別GC: 世代別ガベージコレクション。M&SとコピーGCを組み合わせ、オブジェクトを世代に分けることで効率よく回収を行う方式。
• コンカレントGC: STWせずに並列処理でできるだけマーク付けをすることで、STWを極力なくす方式。
• インクリメンタルGC: 少しずつ小まめにできるだけマーク付けをすることで、一回あたりのSTWを短くする方式。
• G1: ガベージファースト・コレクタ。ヒープをいくつかに分割して、余り使っていないヒープを収集、圧縮し、一気に解放する方式らしい。
• STW: Stop the World。時よ止まれ！止まった時の中で動けるのはGCだけ。

【その他】

Teratailのタグでは「ガーベジコレクション」なんですよね。Wikipediaとかは「ガベージコレクション」なんですけど、日本語としてはどちらが正しいのでしょうか。

Answer 1

https://blogs.msdn.microsoft.com/brada/2005/02/11/resource-management/
.netの中の人からの文書で、参照カウントを採用していない理由が述べられています。

In summary:

•   We feel that it is very important to solve the cycle problem without
  

forcing programmers to understand, track down and design around these
complex data structure problems.

•   We want to make sure we have a high performance (both speed and
  

working set) system and our analysis shows that using reference counting for
every single object in the system will not allow us to achieve this goal.

•   For a variety of reasons, including composition and casting issues,
  

there is no simple transparent solution to having just those objects that
need it be ref counted.

•   We chose not to select a solution that provides deterministic
  

finalization for a single language/context because it inhibits interop with
other languages and causes bifurcation of class libraries by creating
language specific versions.

パフォーマンス上の問題があり、かつ一部のオブジェクトだけ参照カウントの対象にすることもできないので、と。

Comments

[raccy]

資料ありがとうございます。中の人が言っているのでC#に参照カウントなしと判断したいと思います。そういや、元々参照カウントしか無かったPHPはまだしも、Pythonが未だに参照カウント使うのって、こういったパフォーマンス面ってどう考えているんでしょうかね…。

Answer 2

Java(Oracle、OpenJDKとも)は起動オプションによってGCの方式を切り替えできます。
一覧に書かれている資料内にもあるように、パラレルGC、コンカレント・マーク・スイープGC、ガベージファーストGC、シリアルGCなどです。
ガベージファーストGCはJava7から導入されています。
ガベージファーストGCは以下にソースコードレベルでの詳しい事が書かれています。
http://www.narihiro.info/g1gc-impl-book/

Comments

[raccy]

情報ありがとうございます。G1については抜けていました。Java8の資料も見つけられたので、Javaに追加しておきます。シリアルGCやパラレルGCは選択できるけど、デフォルトでは選ばれることはなさそうなので、記載はどうしようかなと…。
でも、CMSとG1はモーストリ・コンカレント・コレクタとして一つにまとめるべきなのかどうか、もうちょっと勉強しておきます。

Answer 3

RustにはGCがありません。標準ライブラリに参照カウントを含みます。
https://www.rust-lang.org/faq.html#is-rust-garbage-collected

Comments

[raccy]

情報ありがとうございます。Rustについて表に反映しました。

[hello-world]

Swift は参照カウントを提供しています。
https://developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/AutomaticReferenceCounting.html

GCはなさそうです。
https://www.quora.com/Why-doesnt-Apple-Swift-adopt-the-memory-management-method-of-garbage-collection-like-in-Java

[raccy]

Swift足しておきます。GCなしの話は公式サイトとかじゃないから参考資料ってことで足しておきます。

[hello-world]

raccy さんが挙げられたリストにはないですが、D言語は世代別GCっぽいですね
http://www.kmonos.net/alang/d/garbage.html

[raccy]

リストに無くても全然オッケーです。神言語であるLISPを含めるのを忘れているぐらいですから。ドキュメントは本家の方をリンクして反映しておきます。

Answer 4

ある質問のある回答で

おっと、私ですね。ガベージコレクションについては認識不足でした。変数自体はポインタのような挙動を示すので、スマートポインタと関連づけて「使われなくなったオブジェクト」を手っ取り早く判定するのは参照カウントだと思ってしまったわけですが、そうではなさそうです。技術資料に書かれているならともかく、そうでもないのに決めつけは良くないですね。確かに、参照カウントで管理しているのなら不要になった時点でデストラクタを呼んでくれても良さそうなのに、そうなっていませんし。
認識を改めるいいきっかけになりました。
できればその場で指摘していただければありがたかったのですが、そっちの回答の方も直しておきます。質問者さんに誤解を与えるといけないので。

Teratailのタグでは「ガーベジコレクション」なんですよね。Wikipediaとかは「ガベージコレクション」なんですけど、日本語としてはどちらが正しいのでしょうか。

日本語としては「ガベージ」が一般的のような気がしますが、なぜかJava関連のサイトでは「ガーベジ」が多いように思います。ここでもガーベジコレクションとしていますがJavaに分類されていますし。Java特有の文化なのでしょうか（ORACLEのサイトではガベージですが……）。

Comments

[raccy]

実は指摘しようかと色々と資料をあさったのですが、参照カウントじゃないっていうドキュメント類が見つからなかったんで、私も本当に無いのか全然自信が無いんです。個人サイトレベルでも使ってないって書いているところは見当たらないんですよね。ドキュメントだけだと悪魔の証明になりそうで、ソースコードレベルで確認するしかないかなと思いつつあります。なんでもいいですので、参考資料があれば、あげて貰うと助かります。

[catsforepaw]

いろいろ検索してみましたが、明確に書かれている資料は見つかりませんね。ただ、検索して見つけた資料(http://www.slideshare.net/ufcpp/cnet-36422788)で.NETのGC(M&S)と参照カウントの比較をしており、それを見る限りC#(.NET)では参照カウントではないという説明になっています。

[raccy]

参考資料ありがとうございます。yubaさんのと合わせてC#が参照カウントを使っていないのは確実そうなので反映させていただきます。