29

私は常にヒープ (データ構造)を使用してヒープ (動的メモリ割り当て)を実装すると想定していましたが、間違っていると言われました。

ヒープ (たとえば、典型的なmallocルーチンによって実装されたもの、または WindowsHeapCreateなどによって実装されたもの) は、通常どのように実装されますか? 彼らはどのようなデータ構造を使用していますか?

私が求めていないこと：

オンラインで検索しているときに、厳しい制限付きでヒープを実装する方法についての説明をたくさん見てきました。 いくつか例を挙げると、実装方法に関する多くの説明を見てきました。

  • OS にメモリを解放しないヒープ (!)
  • 小さい、同様のサイズのブロックでのみ妥当なパフォーマンスを発揮するヒープ
  • 大きな連続したブロックに対してのみ妥当なパフォーマンスを提供するヒープ
  • 等

そして面白いことに、彼らは皆、より難しい質問を避けています:
「通常の」汎用ヒープ ( の背後mallocにあるものなどHeapCreate) はどのように実装されているのでしょうか?

彼らはどのようなデータ構造 (およびおそらくアルゴリズム) を使用していますか?

4

2 に答える 2

14

アロケータは非常に複雑になる傾向があり、実装方法が大きく異なることがよくあります。

1 つの共通のデータ構造またはアルゴリズムの観点からそれらを実際に説明することはできませんが、いくつかの共通のテーマがあります。

  1. メモリは大きなチャンクでシステムから取得されます。多くの場合、一度に数メガバイトです。
  2. これらのチャンクは、割り当てを実行すると、さまざまな小さなチャンクに分割されます。割り当てたサイズとまったく同じではありませんが、通常は特定の範囲 (200 ～ 250 バイト、251 ～ 500 バイトなど) です。場合によっては、これが多層化され、実際のリクエストの前に「中程度のチャンク」のレイヤーが追加される場合があります。
  3. どの「大きなチャンク」から分割するかを制御することは、非常に困難で重要なことです。これは、メモリの断片化に大きく影響します。
  4. これらの範囲ごとに、1 つまたは複数のフリー プール (別名「フリー リスト」、「メモリ プール」、「ルックアサイド リスト」) が維持されます。場合によっては、スレッドローカル プールも。これにより、同様のサイズの多くのオブジェクトの割り当て/割り当て解除のパターンを大幅に高速化できます。
  5. 大規模な割り当ては、RAM を大量に浪費せず、プールされたとしてもあまりプールされないように、少し異なる方法で処理されます。

いくつかのソース コードを確認したい場合、jemallocは最新の高性能アロケーターであり、他の一般的なアロケーターの複雑さを代表するものである必要があります。TCMallocは、もう 1 つの一般的な汎用アロケーターであり、その Web サイトには、すべての面倒な実装の詳細が記載されています。Intel のThread Building Blocksには、高い同時実行性のために特別に構築されたアロケーターがあります。

Windows と *nix の間には、興味深い違いが 1 つあります。*nix では、アロケーターは、アプリが使用するアドレス空間を非常に低レベルで制御します。VirtualAllocWindows では、基本的に、独自のアロケーターのベースとなる粗粒度の遅いアロケーターがあります。

これにより、* nix 互換のアロケーターは通常、すべてに 1 つのアロケーターのみを使用すると想定される / 実装を直接提供します(そうmallocしfreeないと、お互いを踏みにじる可能性があります)。、調和して使用できます (たとえば、HeapCreate を使用して、他のヒープと一緒に機能するプライベート ヒープを作成できます)。mallocfree

実際には、この柔軟性のトレードオフにより、*nix アロケーターはパフォーマンス面でわずかに有利になります。アプリが Windows で意図的に複数のヒープを使用することは非常にまれです。ほとんどの場合、それぞれが独自のmalloc/freeを持つ異なるランタイムを使用する異なる DLL が原因であり、どのヒープを追跡することに熱心でない場合、多くの頭痛の種となる可能性があります。いくつかの記憶が生まれました。

于 2012-12-09T05:34:14.767 に答える
6

注: 次の回答は、仮想メモリを備えた一般的な最新のシステムを使用していることを前提としています。C および C++ 標準では、仮想メモリは必要ありません。したがって、もちろん、この機能のないハードウェアでは、そのような仮定に頼ることはできません (たとえば、GPU には通常、この機能がなく、PIC のような非常に小さなハードウェアにもありません)。

これは、使用しているプラ​​ットフォームによって異なります。ヒープは非常に複雑な獣になる可能性があります。単一のデータ構造のみを使用するわけではありません。「標準」のデータ構造はありません。ヒープ コードの配置場所もプラットフォームによって異なります。たとえば、ヒープ コードは通常、Unix ボックスの C ランタイムによって提供されます。ただし、通常は Windows のオペレーティング システムによって提供されます。

  1. はい、これは Unix マシンでは一般的です。*nix の基礎となる API とメモリ モデルが動作する方法が原因です。基本的に、これらのシステムのオペレーティング システムにメモリを返す標準 API では、ユーザー メモリが割り当てられている場所と、ユーザー メモリとスタックなどのシステム機能の間の「穴」との間の「フロンティア」でのみメモリを返すことができます。(問題の API はbrkまたはsbrkです)。多くのヒープは、メモリをオペレーティング システムに返す代わりに、プログラム自体で使用されなくなったメモリを再利用しようとするだけで、メモリをシステムに返そうとしません。sbrk( )に相当するものにVirtualAllocはこの制限がないため、これは Windows ではあまり一般的ではありません。（しかし、sbrk、非常に高価であり、ページサイズおよびページ整列チャンクのみを割り当てるなどの注意事項があります。したがって、ヒープは可能な限りめったにどちらかを呼び出そうとします)
  2. これは、メモリを固定サイズのチャンクに分割し、空いているチャンクの 1 つを返す「ブロック アロケータ」のように聞こえます。私の (限られた) 理解では、WindowsRtlHeapはさまざまな既知のブロック サイズに対して、このような多数のデータ構造を維持しています。(たとえば、サイズ 16 のブロック用に 1 つ持つことになります) RtlHeap はこれらを「ルックアサイド リスト」と呼びます。
  3. このケースを適切に処理する特定の構造についてはよく知りません。大きなブロックは、アドレス空間の断片化を引き起こすため、ほとんどの割り当てシステムで問題になります。

主要なプラットフォームで採用されている一般的な割り当て戦略について説明している、私が見つけた最良の参考文献は、Robert Seacord による著書Secure Coding in C and C++です。第 4 章はすべて、ヒープ データ構造 (およびユーザーがヒープ システムを誤って使用した場合に発生する問題) に専念しています。

于 2012-12-09T05:29:18.960 に答える