1

私は（C11で）ある種のものを作る必要があり、Objective-C言語の場合liblispとほとんど同じように、基本的な機能を処理する必要があります。libobjc

編集

質問を一般的ではないものに書き直しています。

私は次のような実装を得ました：

typedef struct cons {
  void *car, *cdr;
} *cons_t;

cons_t cons_init(void *, void *);
void *cons_get_car(cons_t);
void *cons_get_cdr(cons_t);
void cons_set_car(cons_t, void *);
void cons_set_cdr(cons_t, void *);
void cons_free(cons_t);
bool cons_is_managed(cons_t);

したがって、コンス セルを作成できます (参照カウント オブジェクトでメモリ プールを使用します)。また、コンス セルがメモリ プール内にあるかどうかを確認するために使用することもできます (そのため、 (静的データのように)cons_is_managedで作成されたのではなく、外部で定義されたセルを使用できます)。cons_init

ここで自動参照カウントを効率的に実装するにはどうすればよいですcons_set_carか?cons_set_cdrvoid *

ハーレムとカメの問題はここでは役に立ちません。各セルには 2 つの可能な方法があるため (そして、car または cdr がコンスの場合はどこにも行かない可能性があります)、それらはリスト、ツリー、またはグラフである可能性があります。

cons_set_carそれらを含むサイクルを見つけるために、おそらく on /で使用される外部 (管理されていない) conses を登録する必要がありますが、これを効率的cons_set_cdrに行う方法はまだわかりません。

これは、グラフの一般的なサイクル (ノード上の最大 2 つの頂点) よりも制御されたコンテキストであるため、線形時間でこれを実行し、ガベージ コレクションを回避できる可能性はありますか (これが私のプラン B になります)。

主な問題は、これが関数型言語のコアであるため、これらの関数が( のように) 何度もobj_msgSend呼び出され、ボトルネックになることです。

ありがとう。

別のアプローチでは、質問を簡単にするために、Objective-C + ARC や Vala のような参照カウントに基づく言語にコンス セルを実装するにはどうすればよいでしょうか?

4

1 に答える 1

1

あなたが実装しようとしている参照カウントの主な目標は、効率的なガベージ コレクションであると想定しています (「ガベージ コレクションを回避する」と言っても、自動メモリ管理の実装を目指していることは明らかです)。

まず、最新の Lisp 実装のほとんどが使用するような、ある種のトレース ガベージ コレクションに切り替えるかどうかを検討することをお勧めします。それと参照カウント ガベージ コレクションの基本的な違いは、メモリに対する正対負の関係にあります。参照カウントでは、割り当てられた要素は、そうでないことが証明されるまで (通常はグラフ トラバーサル アルゴリズムによって) ライブであると見なされます。トレースを使用すると、割り当てられた要素は、(REPL インターフェースなどのオブジェクトのルート セットからの到達可能性によって) そうでないことが証明されるまで、ガベージであると見なされます。

はい、マーク アンド スイープ アルゴリズムの実行中に時折重大なパフォーマンス ヒットが発生する可能性がありますが、ライブラリで目的としている用途によっては、それだけの価値がある場合があります。同様に、スレッド化を慎重に管理すると、1 つのコアでガベージ コレクションを処理し、もう 1 つのコアで実行を続けることができます。最も効率的なのは、サイクルを処理できない「安価な」参照カウントを実行して頻度の高い簡単なケースを処理し、トレース メソッドを使用して循環ガベージが蓄積するのを収集するなどのハイブリッド戦略です。

それを効率的に行う方法については...参照カウントを行う場合は、cons ごとに 1 つの数値を格納する必要があります。構造体に保存しないのはなぜですか？

typedef struct cons {
   void *car, *cdr;
   size_t reference_count;
} *cons_t;

ハイブリッド戦略を採用すると、マップでのリスト処理、リダクション、再帰関数などの高頻度の操作を O(n) 時間で処理できます。ここで、n はガベージ コレクションされる要素の数です。

于 2014-10-09T19:16:13.853 に答える