10

正確なコピーアロケータを作成できるように、自分でmalloc/freeを作成したいと思います。

どんな教祖にもヒントや提案がありますか？

今のところいくつか質問があります：

  1. システムコールを呼び出す必要がないように、メモリの大きなチャンクをmallocして、そこから分散する必要がありますか？
  2. コレクターのコピーは通常どのように行われますか？この部分を効率的に行うには少し複雑だと思います。私の素朴な実装では、残りのオブジェクトのサイズのブロックをmallocするだけで、2倍のスペースが必要になります。
4

3 に答える 3

20

malloc や同様のものの実装に関する優れた文献がかなりあります。しかし、ここに C++ が含まれていることに気付きました。C++ で独自の実装を作成できることをご存知newですかdelete? 手軽にできる方法として重宝しそうです。

いずれにせよ、必要な特性はワークロード、つまり時間の経過に伴う使用パターンに大きく依存します。malloc と新しい free しかない場合は、明らかに簡単です。1 つまたはいくつかの異なるブロック サイズの malloc しかない場合、それも簡単です。

他の言語では、メモリを連結する機能を利用することである程度の活用が可能ですが、C はそれほどスマートではありません。

malloc の基本的な実装では、データ長、「使用中フラグ」、および割り当てられたメモリを含むヘッダーを割り当てるだけです。次に、malloc はそのスペースの最後に新しいヘッダーを作成し、メモリを割り当て、ポインターを返します。解放すると、使用中フラグがリセットされるだけです。

秘訣は、mallooc と free を大量に実行すると、使用されていない小さな BLOB がすぐに大量に取得され、割り当てが困難になることです。したがって、メモリのブロックをマージするには、ある種のバンプ GC が必要です。

もっと複雑な gc を実行することもできますが、時間がかかることに注意してください。無料で多くの時間を費やしたくありません。

Solaris の malloc 実装に関する興味深い論文があります。これも Solaris で別のmalloc を作成する方法ですが、基本は同じです。そして、ガベージ コレクションに関するウィキペディアの記事を読み、それに従ってより正式な論文をいくつか読んでください。

アップデート

ご存知のように、世代別ガベージ コレクターを確認する必要があります。基本的な考え方は、何かが割り当てられたままになる時間が長ければ長いほど、割り当てられたままになる可能性が高くなるということです。これは、言及した「コピー」GCの拡張です。基本的に、メモリプールの一部に新しいものを割り当て、それを g0 と呼びます。その最高水準点に到達したら、割り当てられたブロックを調べて、まだ使用されているブロックをメモリの別のセクションにコピーし、それを g1 と呼びます。次に、g0 スペースをクリアして、そこに割り当てを開始できます。最終的に g1 は最高水準点に到達し、g0 をクリアして修正し、g1 をクリーンアップして g0 に移動します。完了したら、古い g1 を g0 に、またはその逆に名前を変更して続行します。

秘訣は、特に C では、malloc されたメモリに渡すハンドルが生のポインタであることです。ヒープの大きな薬がなければ、実際に物事を動かすことはできません。

2回目の更新

コメントで、@unknown は「memcpy() だけでは物を動かさないだろう」と尋ねます。そして確かにそうなるでしょう。ただし、次のタイムラインを考慮してください。

警告: これは完全ではなく、テストもされていません。説明のため、娯楽のみを目的としており、明示または黙示の保証はありません。

/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/

一部のメモリを割り当て解除します

/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
    exit(-1);

malloc の実装では、メモリを作成し、ポインタをバッファに返します。

unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];


void * newMalloc(size_t size){
   void * rtn ;
   if( /* memory COMPLETELY exhausted */)
      return NULL;
   /* otherwise */
   /* add header at nextUnused */
   newHeader(nextUnused);     /* includes some pointers for chaining
                               * and a field with values USED or FREE, 
                               * set to USED */
   nextUnused += HEADERLEN ;  /* this could be niftier */
   rtn = nextUnused ;
   nextUnused += size ;
}

解放されたものもある

  newFree(void * aHandle){
     *(aHandle-offset) = FREE ; /* set the flag in the header, 
                                 * using an offset. */
  }

これですべての作業が完了し、最高水準点に到達します。

 for( /* each block in your memory pool */ )
    if( /* block header is still marked USED */ ) {
        memcpy(/* block into other partition */);
    }
 /* clear the partition */
 bzero(g0, partitionSize);

ここで、myMemHdl に保存した元のハンドルに戻ります。それは何を指していますか？(答え、bzero(3) で 0x00 に設定するだけです。)

ここで魔法の出番です。少なくとも C では、malloc から返されたポインタはもはや制御できません。事後に移動することはできません。C++ では、ユーザー定義のポインターのような型を使用すると、これを修正できます。

于 2009-04-09T03:11:15.400 に答える
1

あなたがしようとしていることについてもう少し知っておくと役に立ちます。こちらはシングルタイプですか？それとも、比較的均一なタイプのセットですか?

  • 特定のタイプの割り当てを高速化する必要がある場合、メモリプールは実証済みの手法です (考えられる欠点の 1 つは、メモリ全体をホッピングして、キャッシュのパフォーマンスに影響を与える可能性があることです)。
  • アプリケーション全体の割り当て手法には、通常、すべての割り当てをプロファイル主導のバケット サイズに切り上げて、断片化を抑えることが含まれます。
  • 通常、マルチスレッド アプリには、他のスレッドとの競合の危険を冒さずに割り当てることができるスレッドごとのプールがあります。

tcmalloc のドキュメントは、これらの手法の現在の最先端技術を説明するのに非常に優れています。

ここにはそれほど複雑なことはありませんが、おそらく車輪の再発明をしているでしょう. これを行うオープン ソース ライブラリがいくつかあります。

于 2009-04-09T03:54:13.317 に答える
0

アイデア #1 を使用しないでください。アプリケーションの実行全体で未使用のままになる可能性のある多くのリソースを浪費し、その間ずっと他のプロセスがそれを利用するのを停止します (使用する計画によって異なります)。

于 2009-04-09T03:13:48.873 に答える