メモリ割り当ての時間の複雑さ

Question

new、mallocなどを使用した動的メモリ割り当ての時間の複雑さは？メモリアロケータの実装方法についてはほとんど知りませんが、答えは実装に依存していると思います。したがって、いくつかのより一般的なケース/実装について回答してください。

編集： 最悪の場合、ヒープの割り当てに制限がないと聞いたことを漠然と覚えていますが、平均/典型的なケースに本当に興味があります。

Answer 1

O表記を扱う際に理解しなければならないことの1つは、 n が何であるかを理解することがしばしば非常に重要であることです。 n が制御可能なものに関連するもの（例：並べ替えるリスト内の要素の数）である場合、それをよく見るのは理にかなっています。

ほとんどのヒープ実装では、 n はマネージャが処理しているメモリの連続したチャンクの数です。これは明らかに、通常はクライアントの制御下にあるものではありません。クライアントが実際に制御できる唯一の n は、必要なメモリチャンクのサイズです。多くの場合、これはアロケーターの所要時間とは関係ありません。大きな n は、小さな n と同じくらい迅速に割り当てられる場合があります。また、さらに時間がかかる場合や、サービス不能になる場合もあります。これはすべて、同じ n に対して、以前の割り当てと他のクライアントからの割り当て解除がどのように行われたかに応じて変わる可能性があります。したがって、実際には、 -決定論的。

これが、ハードリアルタイムプログラマーが（起動後）動的割り当てを回避しようとする理由です。

Answer 2

ヒープアロケーターの時間の複雑さは、最適化の対象に応じて、システムによって異なる場合があります。

デスクトップシステムでは、ヒープアロケータは、最近の割り当てのキャッシュ、一般的な割り当てサイズのルックアサイドリスト、特定のサイズ特性を持つメモリチャンクのビンなど、さまざまな戦略の混合を使用して、割り当て時間を抑えながら、フラグメンテーション管理可能。使用されるさまざまな手法の概要については、Doug Leaのmalloc実装に関する注意を参照してください。 http： //g.oswego.edu/dl/html/malloc.html

より単純なシステムの場合、最初の適合または最良の適合の戦略が使用され、リンクされたリストにフリーブロックが格納されます（Nはフリーブロックの数でO（N）時間を与えます）。ただし、AVLツリーなどのより洗練されたストレージシステムを使用して、O（log N）時間（ http://www.oocities.org/wkaras/heapmm/heapmm.html ）。

リアルタイムシステムは、TLSF（Two-Level Segregate Fit）などのヒープアロケーターを使用する場合があります。これには、O（1）割り当てコストがあります。 http://www.gii.upv.es/tlsf/

Answer 3

一般にO（n）になると思います（nは使用可能なメモリブロックの数です）（使用可能なメモリブロックをスキャンして適切なメモリブロックを見つける必要があるため）。

とはいえ、サイズ範囲に応じて利用可能なブロックの複数のリストを具体的に維持することで、高速化できる最適化を見てきました（1k未満のブロックは1つのリストに含まれ、1kから10kのブロックは別のリストに含まれます）など）。

これはまだO（n）ですが、nが小さいだけです。

無制限のヒープ割り当てがあることをソースに確認したいと思います（それによって、永遠にかかる可能性がある場合）。

Answer 4

典型的なアロケータがどのように機能するかを確認してください。

bump-the-pointerアロケータは、 O（1）で動作します。それは小さな「 1 」です。

分離ストレージアロケーターの場合、kバイトの割り当てとは、「List（ n ）から最初のブロックを返す」ことを意味します。 List（ n ）は、 n＆gt; = k のnバイトのブロックのリストです。 List（ n ）が空であることを発見する可能性があるため、次のリスト（List（ 2n ））のブロックは結果として生じる n バイトの両方のブロックがList（ n ）に配置され、この効果が利用可能なすべてのサイズに波及し、 n O（ns）の複雑さ。ここで、nsは使用可能なさまざまなサイズの数です。 ns = log（N）ここで、 N は利用可能な最大のブロックサイズなので、それでも小さくなります。ほとんどの場合、特にいくつかのブロックが割り当てられ、割り当て解除された後、複雑さは O（1）です。

Answer 5

2つのコメント：

• TLSF はO（1）です。シングルループ;最大2Gbを管理します。 信じがたいですが、コードを確認してください。

• 「ベストフィット」が正しいとは限りません。ポリシー（タイトなブロックを見つける）が最も適しています 小さな断片化を達成します。 この主張を実証するのは簡単なことではありません。実際、正式に証明されたわけではありませんが、その方向に向かう証拠はたくさんあります。 （素敵な研究トピック）。