4

私はおもちゃの手続き型言語の趣味のコンパイラ/インタプリタに取り組んでおり、良いガベージ コレクション アルゴリズム (この男に似ています) を除いて、探索しようとしているほとんどの機能を実装しました。私はさまざまなアルゴリズムについてかなり読んだことがあり、それらを実装する方法についての一般的な考えを持っています。私の言語ランタイムの以前の反復では参照カウントを使用していましたが、より高度なことを学ぶためにそれをやめたので、現在はマークとコピーの圧縮アルゴリズムを検討しています。

開始時の私の最初の問題は、アルゴリズムがネイティブ拡張関数 (つまり、C で記述された関数) の「オブジェクト」を収集できないことです。ルート セットは、インタープリターのスタック上の「オブジェクト」とシンボル テーブル内の「オブジェクト」で構成されています。これらについてはあまり問題にならないはずですが、コンテナの「オブジェクト」が C 関数で作成されてから、子「オブジェクト」、実際にはインタープリタースタック上にないか、シンボルにバインドされていないため、GC がそれらを収集しないようにするにはどうすればよいですか?

GC の実装を容易にするもの:

  • 私の言語のすべての「オブジェクト」は組み込み型です (たとえば、オブジェクト指向ではありません)。
  • インタプリタ スタックは、構造体へのポインタの単なるスタックです。
  • シンボル テーブルは、構造体へのポインタの単なる配列です

ユーザーコード:

f = open('words.txt', 'r');
lines = readlines(f);
close(f);

インタプリタ (解析後、バイトコードにコンパイル...):

  1. pushファイル名、open_mode
  2. builtin_fopenをラップする構造体を返す呼び出しFILE*
  3. 結果をシンボルに格納f
  4. プッシュ記号f
  5. builtin_flinesリストタイプを作成する呼び出しl、次にCfreadを使用してファイルの各行を文字列タイプとして読み取り、リストに追加しますl
  6. 結果をシンボルlinesに格納するなど....

ファイル内の行を含む文字列の 1 つが割り当てられている間に GC が実行された場合、ルート セットにはまだ への参照がないlため、収集されるはずです。これをより適切に処理する方法についてのアイデアはありますか?

4

4 に答える 4

3
  1. インタプリタのヒープ用に別の連続した割り当て領域を専用にします。アリーナの外で何かを収集しないでください。
  2. あなたは常にアリーナの現在のトップを持っています (それがより低いアドレスからより高いアドレスに成長すると仮定します)。一番上にあるものはすべて収集可能ではありませんが、ルート セットと見なされます。複数のリンクされたオブジェクトを割り当てなければならない組み込み関数は、それらを一番上に割り当て、次に一番上に移動して、割り当てられたすべてのオブジェクトが一度に収集可能なヒープに収まるようにします。関数の実行中にコレクションが発生した場合、最上位のオブジェクトは新しいヒープにまとめて移動されます。
于 2013-04-07T21:41:51.183 に答える
1

ネイティブ関数にインターフェイスを提供する必要があります。これを介して、ガベージコレクターに参照しているオブジェクトを伝え、そのインターフェイスを使用させることができます。

おそらく最も簡単な方法は、ネイティブ コードがインタプリタ/ガベージ コレクション データへの直接ポインタを持たないようにすることです。代わりに、ネイティブ コードにオブジェクトへのハンドルを与え、ランタイムにコールバックしてオブジェクトから値を取得します。あなたの例でbuiltin_flinesは、ランタイムを呼び出してリストを割り当て、そのハンドルを取得します。次に、行を読み取り、ランタイムを呼び出して各行をリストに追加し、最終的に完全なリストを返します。ランタイムは、特定のネイティブ呼び出しのすべてのハンドルを管理し、ネイティブ呼び出しが戻った後にそれらを解放します。

于 2013-04-07T23:52:00.290 に答える
-1

いくつかの合併症：

100 if X then gosub 5000 のように解釈される行を入力すると

しかし、5000 はまだ存在しません。あなたはスパゲッティ コーディングをしています...おそらく、x にはまだ値やデータ型が割り当てられていません。今すぐインデックスを作成しない場合、誰かが「実行」と入力するか、プロンプトから直接行を実行するまで待ちますか?

後で高速化するために今インデックスを作成した場合、「100」、「X」、または「5000」の最後のインスタンスが削除されたことをどのように知ることができますか?

「もの」のマスターインデックスにはどのようなエントリを作成しますか? これらには、名前または行番号で処理したい基本コード、文字列、およびその他の変数の行が含まれていると仮定します。

ガベージ コレクションの必要性が生じたときに、ガベージ コレクションの可能性を戦略的に特定するために使用します。

サイズが変化する可能性のあるもののインデックスで、どのくらいの静的スペースを消費しますか? 索引付けを正当化するのに十分な、ラベル、位置、および長さ以外の詳細はどれですか? 変数が縮小するときに、空のスペースにインデックスを付けようとする必要がありますか? それとも、変数の最大の履歴サイズと現在のサイズをインデックス化するだけですか? 最も頻繁にサイズが変化する変数を特定するにはどうすればよいでしょうか。また、それらを消去することを避けるべきでしょうか、あるいは意図的に埋めるべきでしょうか?

混乱全体を片付けるのはいつですか？それとも、他の方法では既存の穴に横向きに詰め込むことができないものを詰め込むのに十分な空き領域だけを最適化する方がよいでしょうか?

意図的な遅延と「入力」の待機は、混乱の一部を事前にクリーンアップするために悪用できる良いターゲットのようです。基本的なプログラムにそのようなデッドタイムがあるという保証はありません。

申し訳ありませんが、これは答えではありませんが、元の質問は、より良いスキームに向けてブレインストーミングを促しているようです。問題全体を定義する明確な戦略が必要です。

于 2014-01-07T00:38:23.490 に答える