2011-02-01 8 views
16

私は、静的型オブジェクト指向言語用のコンパイラを作成しています。現在、私は使用するガベージコレクションアルゴリズムを研究しています。コレクターがあるかどうか疑問に思っています:これらの要件を満たすガベージコレクションアルゴリズムはありますか?

  • オープンソースで文書化されていますので、実装することができます。
  • Acurrate
  • 世代
  • グローバル、すなわちプロセスごとに1つだけのコレクタは、スレッドごとに言うとは対照的に、存在します。
  • 重要なコレクションからの長い休止を避けるために、インクリメンタルおよび/またはコンカレント。
  • このプログラミングパラダイムに適合します。破壊的な割り当ての存在下で非常に遅くなるコレクタではないものの例。

編集:明確にするためにこれを行うに実現アルゴリズムがありますならば、私は既製のコレクターがありますされていない場合、疑問に思いました。

+3

は、.NETやJavaプラットフォームをターゲットにする場合、あなたが自由のための1つを取得します。 –

+4

ここにはうんざりして良い記事があります(http://blogs.msdn.com/b/abhinaba/archive/2009/01/25/back-to-basic-series-on-dynamic-memory-management.aspx )をガベージコレクションに追加しました。 – jason

+1

@Henk、彼はコンパイラを作成しています – ThomasMcLeod

答えて

2

(私はむしろコメントとしてこれを聞かせてだろうが、私は十分に担当者を持っていない。)

あなたはアルゴリズムではなくコードを探しているなら、私はdefinetely学術論文に見てみます。

http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-1.html
http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-2.html

をそれらの「ビッグバン」の瞬間の利点:彼らはガベージコレクションの2つののセッションを持っていた---私はOOPSLA 2003の議事録につまずいた、とすぐに私はあなたの質問を思い出しました研究を始めるにあたっては、有望な記事にGoogle Scholarを使用して、最新のフォローアップがあるかどうかを確認し、タイトルを探して「引用者」リンクをクリックしてください例:

http://scholar.google.com/scholar?cites=11437015034573374705&as_sdt=2005&sciodt=0,5&hl=en

(あなたは非常に多くの要求を持っているので、あなたがあなたのオンザフライコレクタを見つける前に多くのカエルにキスをする必要がある場合があります。)

0

おそらく、.NETのオープンソースの実装であるmonoからガベージコレクタを盗む可能性があります。彼らは最近、(私が思う)上記のすべての要件を満たす新しいGCエンジンをリリースしました。

+0

いくつかの研究の後、Monoの新しいコレクターは世界が止まっていることが分かったので、それは必要条件を満たすものではありません。 – keiter

0

このようなコレクタを盗む問題:ガベージコレクタは、書かれた言語で結ばれていることがよくあります。関数型言語の優れたコレクターは、命令型コレクターとは異なる働きをする傾向があります。オープンソースから盗むべき理由はおそらく存在し配置します

  • はモノ
  • OCamlの
  • Pythonの
  • ...
0

これは(明らかに)いくつかの良いアイデアなしに答えることは困難ですホストしようとしている言語のうち、Parrot VMを見ましたか? PDD 9: Garbage Collection Subsystemは、そのGCについて議論し、あなたが求めている流行語を打ち明けたようです。そして、それが設計された言語(主にPerl6と強力な型のjavascript-ishのものが強力な秒としてwinxedと呼ばれます)は、

VMターゲットですが、スタンドアロンGCではありません。何らかのVMに関連付けられていない市販のGC(Boehmのような)以外のGCを見つけられるのは本当に疑問です。正確になるようにするには、逆アセンブリよりも多くのスタックフレームに関する情報が必要です。

5

実際にすべての要件を満たしている実験的でないガベージコレクションアルゴリズムがあります。単純な自動参照です。全体として、実際にはrefcountingは実行可能なオプションとして十分なクレジットを得ることはできませんが、実際には多くの状況でうまく機能し、大きなバッチ遅延はなく、複雑な魔法の必要はありません。

懸念事項の1つは依然として循環参照をクリーンアップしていることです。速度を心配しているアプリ開発者は、オブジェクトがなくなる必要があるときにループを明示的に解除できます。

refcountingのごくわずかな点は、他のガベージコレクションよりもはるかにdcacheに優しいことです。ループを実行するたびに小さな一時オブジェクトを割り当てるループを実行している場合、refcounting GC(または明示的なメモリ管理)は毎回同じメモリを再利用できるため、不要なキャッシュフラッシュを回避できます。他の種類のGCでは、オブジェクトを定期的に解放するだけで、メモリフットプリントが非常に大きくなるため、速度が遅くなります。

Refcountに触れるたびにロックを取得する必要があるため、Refcountingは多量のマルチスレッドシステムではあまり効率的ではありません。しかし、もしあなたが新しい言語を設計しているのであれば、あなたの言語でのパフォーマンスと信頼性を向上させるためにできることはたくさんあります。ほとんどのオブジェクトがスレッド間で共有されないようにします。すなわち、共有を明示的にする。これを行うと、どのオブジェクトが共有されていないかを知ることができるため、refcountを増減するときにロックする必要があり、ロックされていないオブジェクトをロックする必要があります。ロックがない場合は、実際の再生回数は非常に優れています。

0

アズールガベージコレクタは独自のものですが、あなたはそれのようなものを実装することができるはず彼らのアルゴリズムについての利用可能な十分な情報があります:http://news.ycombinator.com/item?id=2022723

これを行うの複雑さがあるのにそれは間違いなく、「pauseless」コレクションをサポートしています人々が通常しない理由の良い兆候です。

関連する問題