📮 👩🏽‍💻 ✔️ C ++ガベージコレクター 🕺🏿 🖖🏽 🛎️

こんにちは、Habr！私はこの記事を長い間計画しています。 C ++での最も単純なコピーガベージコレクターについてです。かなりの制限があります（一部は干渉せず、一部の深刻なライブラリを書きたい場合は一部を回避できますが、一部の言語では基本的なサポートが得られると便利です）が、そのコードは100行強です。猫の下で興味を持ってください。少なくともOOP、最も単純なパターン、およびポインターを使用した不気味な魔法の儀式があります。

最初から始めましょう。ガベージコレクターとは何ですか？

Gargabe Collector（GC）は、リソース（通常はヒープに割り当てられたRAM）を管理するための方法です。一番下の行は簡単です-プログラマーはガベージコレクターにメモリの一部を割り当てるように要求しますが、彼は不要になり解放できる時期を既に決定しています。これにより、ほとんどのメモリリークの問題が解決されますが、セグメンテーションエラーを誇張して誇張することは不可能になります。なんて残念。

ガベージコレクターには、保守的とコピーの2種類があります。

最初のタイプのようなものが最新の標準に実装されています。 shared_ptrメカニズムは、newおよびdelete演算子の明示的な使用を排除します。オブジェクトを指すリンクをカウントし、それらの数がゼロになるとそれを取り除きます。このアプローチの問題は、多くの小さなオブジェクトが同じ寿命ではなく短い寿命で作成される場合に発生します。その結果、ヒープは有効なオブジェクトの血まみれの混乱に変わり、数十バイトの空きメモリの断片になります。このため、新しいオブジェクトの作成は永遠にかかり始め、ネイティブコードはPythonをvy望し始めます。

この問題を解決するために-ヒープの断片化-コレクターの2番目のタイプが発明されました-コピーします。当分の間、彼のごみ処理戦略は熟考です。過剰になった場合、彼は次のことを行います。

1.必要なすべてのデータを別のメモリ領域にコピーします。

2.すべてのポインターを関連するものに変更します。

3.使用されなくなったすべてのメモリを解放します。

ガベージコレクションアルゴリズムや、C ++の「アダルト」GCライブラリがどのように機能するかについては詳しく見ていないことをすぐに明らかにします。おそらく、ここで説明するアルゴリズムには名前、おそらく名前がありますが、これではソースへの参照なしで行います。

プログラムがまだ必要とするオブジェクトを決定するために、メモリを通常のグラフと見なすことを提案します。次に、ガベージコレクション後の「リビング」オブジェクトは、ポインターのチェーンを介して到達可能なオブジェクトと見なされます。これにより疑問が生じます。まず、プログラマーが作成を要求する可能性のあるオブジェクトについては、どこにポインターがあるかを判別します。最初の方法は、オブジェクトの各クラスにテンプレートマジックを使用して独自のアロケーターを作成することです。多くの理由で恐ろしいアイデア。 2つ目は、GCが機能するために必要なすべての情報を各オブジェクトのヘッダーに書き込むことです（そう、この実装は仮想関数を持つクラスには適していません。必要に応じていくつかのアイデアがあります）。

ヘッダーはさまざまな方法でも使用できます。私のものは、最も簡単なものです（実装のためですが、使用しないため）。まず、ガベージコレクターを介して作成される予定のすべてのオブジェクトは、定義の最初に次の構造を持つ必要があります。

enum { STRUCT_SZ = 0, REF_COUNT = 1 }; struct gcHeader { union { int gcData[2]; gcHeader* post_gcAddress; }; };

第二に、ヘッダーの直後で、ガベージコレクターにも適用されるすべてのポインターを移動する必要があります。したがって、それらの番号はgcData [REF_COUNT]に保存されます。これは、私の実装が課す制限の1つです。 GcData [STRUCT_SZ]は、構造体のサイズをバイト単位で保存します。ポインターの目的は後で明らかにします。便利なのは、構造のサイズがポインターのサイズに等しいことです（現在は2014年です！）。

素晴らしい、今私たちの記憶を回避することができます。問題は、どこに移動するかです。いつでも絶対にアクセスできるメモリの唯一の領域はスタックです。問題は、構造体のポインターの場合と同じです-大量のバイトがGCオブジェクトを指しているのかわかりません。したがって、このような各ポインターの場所は明示的に記述する必要があります。

 vector<gcHeader**> referencesStack; template <class T> class stackRef { public: T* ref; stackRef(){ ref = nullptr; referencesStack.push_back(reinterpret_cast<gcHeader**>(&ref)); } ~stackRef(){ referencesStack.pop_back(); } };

stackRefクラスは単純に機能します。初期化時に、アドレスをリンクスタックに追加するだけです。したがって、デストラクタは同じスタックから無関係なアドレスを削除します。デストラクタを使用した呼び出しとコンストラクタのスタックは同期されるため、異常は発生しません。

クラスでは、多くの演算子を再定義する必要があります-参照解除、割り当てなど。ただし、Boost Foundationの担当者から連絡が来てすぐにこれを行うのは理にかなっています。

支持構造は準備ができています。メモリの割り当てに移動できます。

このリソース管理方法の優れた機能は、まさにリソースの割り当て方法です。削除するたびに、標準C ++アロケーターは空きブロックのリストを更新し、新しいブロックの中で適切なブロックを見つけ、それを2つの小さなブロックに分割し、その後、現代のアロケーターが行うことを行います。ガベージコレクターの場合、削除操作は単純に必要ないため、すべての占有メモリは1つの固体ブロックに格納されます。新しいオブジェクトを作成するには、このブロックのサイズを大きくする、つまり1つのポインターを移動するだけです。 O（1）で実行される簡単な操作。実際、不要なメモリを再利用できる場合に大量のアセンブリを呼び出しますが、今はそこで停止できます。

ガベージコレクターによって制御されるメモリを4キロバイトの断片に分割し、それらをリストにリンクします。実際、4キロバイト強ですが、これは私の怠thisの問題です。

 const int CHUNK_SIZE = 4096; const int OVERDRAFT = 128; const int ACTUAL_SIZE = CHUNK_SIZE + OVERDRAFT; //      15  ,  -   . struct gcChunk { gcChunk* next; char data[ACTUAL_SIZE];//     . }; gcChunk* firstChunk; gcChunk* currentChunk; int chunkCount; int currentOffset;

firstChunkはリストの先頭、currentChunkは最後に作成されたメモリブロックです。 urrentOffset-currentChunkに関連する空きメモリセグメントの開始。

 gcHeader* gcRawAlloc(int size, int refCount){ if (size > CHUNK_SIZE)//  proof of concept,      return nullptr; if (currentOffset + size > CHUNK_SIZE){ //     list<gcChunk>  STL,   ,       . ++chunkCount; currentChunk->next = new gcChunk(); currentChunk = currentChunk->next; currentChunk->next = nullptr; currentOffset = 0; } gcHeader* new_obj = reinterpret_cast<gcHeader*>(&(currentChunk->data[currentOffset])); new_obj->gcData[STRUCT_SZ] = size; new_obj->gcData[REF_COUNT] = (refCount << 1)| 1; currentOffset += size; if (currentOffset % 4)//  4 .  ,    , ..         . currentOffset += 4 - currentOffset % 4; return new_obj;//        ,       ,    —   . }

すでに多くの明白でない点があります。 12行目を分析しましょう。

この段階では、新しいオブジェクトがどのタイプであるかを考えない方が便利です。彼がgcHeaderを持っていることは確かです。これで十分です。

新しいオブジェクトにメモリを割り当てたら、そのタイトルを初期化する必要があります。神秘的な割り当てが意味するもの

 temp->gcData[REF_COUNT] = (refCount << 1)| 1;

？

これを行うには、ヘッダーの定義をもう一度見てください。

 struct gcHeader { union { int gcData[2]; gcHeader* post_gcAddress; }; };

unionキーワードは、gcData配列とpost_gcAddressポインターの両方が同じアドレスにあることを意味します。これはメモリを節約するのに役立ちますが、問題は、C ++がunionのデータが最後にどのように使用されたか（配列または参照として）を覚えていないことです。データのアライメントの必要性など、プロセッサアーキテクチャの機能が役立ちます。

つまり、1バイトより長い変数は、バイト単位のマシンワードの倍数のアドレスに配置する必要があります。最新のプロセッサでのアライメント違反は、プログラムの速度を大幅に低下させ、一般的に古いARMはそのような状態での動作を拒否します。その結果、プログラマの裁量で、ポインタの最下位2ビットまたは3ビットを自由に使用できます。たとえば、赤黒木を実装する場合、ブール変数の代わりに最後のビットがよく使用されます。

ここも同じです。最下位ビットが1の場合、これらの8バイトには2つの整数の配列が保証されます。たとえば、もう少しビットを使用して、ガベージコレクターに「これはポリモーフィックオブジェクトへの参照であり、vtableポインターがあり、上書きしないでください」と示すことができます。

さて、アロケーターを使用してもそれほど苦痛が生じないように、関数の小さなラッパーです。

 template <class T> T* gcAlloc(){ return reinterpret_cast<T*>(gcRawAlloc(sizeof(T), T::refCount)); }

ここで、コンストラクターを持つオブジェクトが正しく初期化されるように、emplace newを配置する必要があります。ご覧のとおり、作成するオブジェクトのクラスには、静的定数refCountが必要です。外部プリプロセッサを使用して自動的に計算できます。そうでなければ、ここに私の足を撃つ少なくとも3つの方法があります。

この関数を使用する前に、ヒープを初期化する必要があります。

 void gcInit(){ firstChunk = currentChunk = new gcChunk; firstChunk->next = nullptr; currentOffset = 0; chunkCount = 1; }

ガベージコレクション自体の実装を見てみましょう。

最初の関数gcCollectは、古いリストへのポインターを保存することを忘れずに、一から開始する必要があります。これらの行は、初期化をほぼ繰り返します。

 void gcCollect(){ //execvp("rm", "cppgc.cpp");//       . gcChunk* newFirstChunk = currentChunk = new gcChunk; currentChunk->next = nullptr; currentOffset = 0; chunkCount = 1;

次に、スタックに格納されている各ポインターを使用してアセンブリプロセスを開始します。

  for (auto i = referencesStack.begin();i != referencesStack.end(); ++i ) gcMove(*i);

そして今、不要なメモリを解放してください。

  // ,       ,     gcChunk iter = firstChunk; firstChunk = newFirstChunk; while (iter != nullptr){ gcChunk* t = iter->next; delete[] iter; iter = t; } }

deleteは大きなメモリブロックに対してのみ呼び出されることに注意してください。したがって、ガベージコレクターのオブジェクトデストラクターは呼び出されません。これは、デストラクタがメモリを解放するだけのクラスでは問題になりませんが、たとえば、接続とファイル記述子を自動的に閉じる方法はありません。これにはMark＆Sweepアルゴリズムが役立ちますが、それらを記述するのははるかに困難です。

最後のタッチはgcMove関数です。

 bool isPointer(gcHeader a){ return (a.gcData[REF_COUNT] & 1) == 0; } void gcMove(gcHeader** current){ if (*current == nullptr) return; if (isPointer(**current)){//    .   ,    . (*current) = (*current)->post_gcAddress; return; } gcHeader* new_obj = gcRawAlloc((*current)->gcData[STRUCT_SZ], (*current)->gcData[REF_COUNT]); memcpy(new_obj, (*current), sizeof(char) * (*current)->gcData[STRUCT_SZ]); gcHeader** iterator = reinterpret_cast<gcHeader**>(new_obj) + 1; (*current)->post_gcAddress = new_obj; (*current) = new_obj; int refCount = new_obj->gcData[REF_COUNT] >> 1; for (int i = 0; i < refCount; ++i, ++iterator) gcMove(iterator); }

関数を真ん中から分析しましょう。リンクをリダイレクトする機能が必要なので、データへのポインターへのポインターが関数に渡されます。

GCは、必要な量のメモリを新しいヒープ内のオブジェクトに割り当て（ヘッダーからどれだけの量を知っているか）、古いインカネーションのすべてのデータを新しいものにコピーします。次に、オブジェクトの新しいアドレスを古いヘッダーに書き込みます。現在、複数の参照がオブジェクトを指している場合、アルゴリズムはオブジェクトがすでに1回（最下位ビット、保証、0）移動したことを判別でき、その後再びコピーすることはありません。古いポインターをオブジェクトの新しいコピーにリダイレクトするために残ります。

次に、オブジェクト自体のポインターを処理する必要があります。あなたも彼らと同じことをする必要があります。行

 gcHeader** iterator = reinterpret_cast<gcHeader**>(temp) + 1;

構造内の最初のリンクへのポインタを取得します（もしあれば）。 sizeof（gcHeader）== sizeof（void *）であることを忘れないでください。それ以外の場合は、さらに数行かかります。

次にすべきことは、論点です。各ポインターに対してgcMove関数を再帰的に呼び出すだけです。そのようなアルゴリズムは、深さのグラフ走査に対応します。ただし、これは最良の選択ではありません。

ガベージコレクターをコピーすることのキラー機能は、参照によってローカリティを維持する機能です。要するに、相互に参照するオブジェクトとメモリ内のオブジェクトは、できる限り近いものでなければなりません。そのため、プロセッサはキャッシュメモリをより効率的に使用できます。

非表示のテキスト

実験を行うことができます。リンクリストを作成し、任意の場所に要素を挿入し始めます。そして、リスト全体を印刷してください。おそらく、C ++プログラムは、強制的なガベージコレクションの後、JavaまたはC＃よりも最後のステップに時間がかかります。これは、C ++の場合、プロセッサがキャッシュミスで常にロックし、低速のRAMからのデータが到着するのを待つという事実によるものです。 Javaの場合、これはほとんどアレイ全体のバイパスになります。

私のGCはそうではありません。単純さのため、深さのバイパスを選択しました。 widthのトラバーサル順序でオブジェクトを移動することをお勧めします。最適なミス数を達成するために、このアルゴリズムのように、オブジェクトへのアクセスの統計に従って混乱してオブジェクトをメモリ内に構築することは非常にクールです。

それだけですコレクターとの作業を実証するために残っています。

最も単純な検索ツリーを例として取り上げます。

 struct searchTree { gcHeader gc; searchTree* left; searchTree* right; int key; static const int refCount = 2; };

既に述べたように、最初は見出しであり、見出しの後にはヒープのオブジェクトへのすべてのポインターがあります。

 void stAdd(searchTree* &target, int key){ if (target == nullptr){ target = gcAlloc<searchTree>(); target->left = target->right = nullptr; target->key = key; return; } if (target->key == key) return; if (target->key < key) stAdd(target->left, key); else stAdd(target->right, key); }

ツリーへの通常の追加。 gcAllocの使用方法に注意してください。

 searchTree* stFind(searchTree* target, int key){ if (target == nullptr || target->key == key) return target; if (target->key < key) return stFind(target->left, key); else return stFind(target->right, key); } void stPrint(searchTree* t, int indent = 0){ if (t == nullptr) return; for (int i = 0; i < indent; ++i) cout << " "; cout << t << ' ' << t->key << endl; stPrint(t->left, indent + 1); stPrint(t->right, indent + 1); } void stCut(searchTree* &target, int key){ if (target == nullptr || target->key == key){ target = nullptr; return; } if (target->key < key) stCut(target->left, key); else stCut(target->right, key); }

stFindは目的のキーを持つサブツリーへのリンクを返し、stPrintはサブツリーのキーとアドレスを出力し、stCutはキーが保存されているサブツリーを切り捨てます。

最後に、メイン。

 int main(){ gcInit(); stackRef<searchTree> root; stAdd(root.ref, 2); stAdd(root.ref, 1); stAdd(root.ref, 3); stAdd(root.ref, 6); stAdd(root.ref, 5); stAdd(root.ref, 4); stAdd(root.ref, 8); stackRef<searchTree> additionalRef; additionalRef.ref = stFind(root.ref, 3); cout << "Before GC" << endl; cout << additionalRef.ref << ' ' << currentOffset << endl <<endl; stPrint(root.ref); cout << endl; gcCollect(); cout << "After GC" << endl; cout << additionalRef.ref << ' ' << currentOffset << endl << endl; stPrint(root.ref); cout << endl; stCut(root.ref, 5); gcCollect(); cout << "Deleted some elements and GC'd." << endl; cout << additionalRef.ref << ' ' << currentOffset << endl << endl; stPrint(root.ref); return 0; }

 Before GC 0xd92058 224 0xd92018 2 0xd92058 3 0xd92078 6 0xd920d8 8 0xd92098 5 0xd920b8 4 0xd92038 1 After GC 0xd93108 224 0xd930e8 2 0xd93108 3 0xd93128 6 0xd93148 8 0xd93168 5 0xd93188 4 0xd931a8 1 Deleted some elements and GC'd. 0xd92038 160 0xd92018 2 0xd92038 3 0xd92058 6 0xd92078 8 0xd92098 1

ご覧のとおり、プログラマー用の構造体を使用してもほとんど変わりません。ここで何が起こっていますか：

1.検索ツリーを任意に埋めます。

2.いずれかの要素への別のスタックリンクを作成して、GCが1つのオブジェクトへの複数のリンクにどのように応答するかを確認します。

3.ツリー、additionalReference、currentOffsetを印刷します。

4.アイドルガベージコレクション。

5.ツリーを再度印刷します。必要なすべてのポインターが変更されました。

6. 1つのサブツリーをトリミングして、ガベージコレクションを再度呼び出します。すべてが正常に機能します。 currentOffsetが減少し、ツリーのルートが初めてアクセスしたのと同じアドレスに戻ったことに注意してください。

結論

したがって、C ++では、ガベージコレクターを使用できます。さらに、意図的な意見では、オーバーヘッドが最小限であっても、かなりきれいです。本当に便利で役立つように、実行する必要があるすべてのものをリストしようとします。

まず、組織のポイント。

1.グローバル変数-もちろん、これはまったくクールではありません。すべてを人間のクラスやC ++アロケーターとして設計する必要があります。

2.各クラスにヘッダーを強制することはほとんどサディズムです。 getSizeとgetLayoutの2つのメソッドが必要な抽象クラスから継承する必要があります。後者は、すべてのポインターの相対座標が格納されている配列への参照を返す必要があります（「すべてのリンクが先頭にある」という考えは、深刻なものにはまったく適していません）。この配列は間違いなく自動的に入力されるはずですが、これをどのように実装できるかはまだわかりません。

次の質問は自動アセンブリです。 GCのアイデアが提唱されたとき、誰もがgcCollect関数のようなものを絶えず呼び出すことを意味する人はいませんでした。ただし、C ++は特殊なケースです。実行の流れ全体を鼻の下で、または少なくとも予測可能なものにすることで有名です。ここで他の言語の気まぐれなガベージコレクターは、ほとんどイデオロギー犯罪です。したがって、少なくとも2つのモードが必要です。

1.透明。

2.特定のメモリクォータを使い果たした後、例外をスローします。ここで、メモリを強制的に削除するか割り当てるかを決定するのはプログラマー次第です。

そしてもう1つ質問があります。マルチスレッド。ここではすべてが悪いです。ガベージコレクションを開始するには、何も壊さないようにすべてのスレッドを中断する必要があります。最後に、JVMの半分を記述する必要があります。最良の解決策は彼の不在のようです。スレッドごとに、独自の専用GCを作成することができます。何かを別のサブプロセスに転送する必要がある場合、通常のshared_ptrをキャンセルしたユーザーはいません。共有メモリがなければ、生活は通常はるかに楽しいです。

悲しいメモで終わります。このようなガベージコレクターは、既製のライブラリと完全に互換性がありません。彼らの施設は必要なデータを提供することはできません。std :: list、std :: map、およびstd :: setは、GC専用に書き換えた場合にのみメリットがあるという事実にもかかわらず、たとえば、NギガバイトのBoostソースをやり直すことはまったく無駄です。ただし、小さなオブジェクトの場合にフラグメンテーションに対処するには、そのようなことは非常に便利だと思います。ここから

ダウンロードして再生できます。

C ++ガベージコレクター

結論 (adsbygoogle = window.adsbygoogle || []).push({});

More articles:

結論