std.experimental.allocator.building_blocks.kernighan_ritchie

struct KRRegion(ParentAllocator = NullAllocator);

KRRegion地域配分戦略からヒントを得る 戦略からインスピレーションを得ている。 の8.7節でブライアン・カーニガンとデニス・リッチーによって説明された有名なアロケータからヒントを得ている。 のセクション8.7でブライアン・カーニガンとデニス・リッチーによって説明されている "The C Programming Language", Second Edition, Prentice Hall, 1988の8.7節でブライアン・カーニガンとデニス・リッチーによって説明されている有名なアロケータからインスピレーションを得ている。

KRRegion=Region + カーニガン・リッチー・アロケータ

最初は KRRegionリージョン "モードで開始する。 メモリチャンクからリージョン方式で割り当てが行われる。したがって、十分なメモリが残っている限り が残っている限り、 KRRegion.allocateはリージョンアロケータの性能プロファイルを持つ。 割り当て解除は、(Ο(1)時間で)割り当て解除されたブロックを非構造化フリーリストに挿入する。 リージョン・モードでは読み込まれない。

リージョンがallocate リクエストに対応できなくなると、次のようになる、 KRRegionに切り替わる。 に切り替わる。これは、以前に割り当て解除されたブロックのリストをアドレスでソートする。 アドレスでソートし、その空きリストから割り当て要求を出す。割り当てと 割り当てと割り当て解除は、KernighanとRitchieが記述したパターンに従う。

推奨される KRRegionの推奨される使用法は、割り当て解除を伴うリージョンとしての使用である。もし KRRegionが適切な大きさであるならば、フリーリスト モードにならないことが多い。したがって、単純なリージョンと同程度に高速である。 を提供する。リージョンのメモリが使い果たされたとき リージョンのメモリが使い果たされても、以前に割り当て解除されたメモリは、性能上のコストはかかるが、まだ使用可能である。もし リージョンが過度に大きく断片化されていなければ、直線的な割り当てと割り当て解除のコストはまだ補えるかもしれない。 割り当てと割り当て解除のコストは、優れた局所性によって補われる。 特性によって補うことができる。

管理されるメモリの塊が大きい場合は、最初からフリー・リスト管理に切り替えるのが望ましいかもしれない。 に切り替えるのが望ましいかもしれない。そうすれば、リージョン・モードよりもコンパクトにメモリーを使用することができる。 リージョン・モードよりもコンパクトになる。フリー・リスト・モードを強制するには、switchToFreeList を構築直後か、適切と思われるときに呼び出す。

割り当て可能な最小サイズは2ワード(64ビットシステムでは16バイト、32ビットシステムでは8バイト)である。 システムでは16バイト、32ビットシステムでは8バイト)である。これは、フリー・リスト管理 これは、空きリストの管理に2つのワード(1つは長さ、もう1つは単一リンクリストの次のポインタ)が必要だからである。 の次のポインタ)が必要だからである。

ParentAllocator "型"パラメータは、メモリチャンクのアロケーショ ンに使われるアロケータの型である。 オブジェクトの基礎となるメモリチャンクを割り当てる KRRegionオブジェクトの基礎となるメモリチャンクの割り当てに使われるアロケータの型である。デフォルトの デフォルトの (NullAllocator) を選ぶと、構築時にバッファを渡す(そして必要であればそれを解放する)責任はユーザーにあることを意味する。 を渡す(そして必要であればそれをデアロケートする)責任がユーザーにあることを意味する。そうでなければ KRRegion は破棄時に自動的にバッファを確保する。そのため ParentAllocator がNullAllocator でない場合 KRRegionは コピーできない。

実装の詳細

フリー・リスト・モードの場合、 KRRegion空きブロックリストを メモリに埋め込む。フリーリストは循環的で、合体され、常にアドレスでソートされる。 でソートされる。割り当てと割り当て解除には、以前に割り当て解除されたブロック数に比例した時間がかかる。 に比例した時間がかかる。(実際には、例えば (実際にはコストはもっと低くなる可能性がある。 一定の時間がかかる)。メモリ使用率が良い(制御構造が小さく、割り当てごとのオーバーヘッドがない)。 割り当てごとのオーバーヘッドがない)。フリーリスト・モードの欠点は以下の通りである。 フラグメンテーションが起こりやすいこと、最小割り当てサイズが2ワードであること、割り当てと割り当て解除にかかる時間がワーストケースで直線的であることである。 である。

の類似点 KRRegion(フリーリストモード)と Kernighan-Ritchieアロケータと似ている:

• フリーブロックのサイズは可変で、単一リンクリストにリンクされる。
• フリーリストはアドレスの増加順で管理される。 合体を容易にする。
• 次に利用可能なブロックを見つけるための戦略は、まず適合する。
• フリーリストは循環しており、最後のノードが最初のノードを指す。
• 併合は割り当て解除時に行われる。

Kernighan-Ritchieアロケータとの違い:

• Kernighan-Ritchieアロケータとの違い:チャンクが使い切られると、Kernighan-Ritchieアロケータはオペレーティング・システム・プリミティブを使って次のチャンクを割り当てる。 OSプリミティブを使って別のチャンクを確保する。より良い互換性を得るために、KRRegion は単に一杯になる(新しい割り当て要求があった場合、null を返す)。そのため さらにブロックを割り当てるかどうかの決定は、より上位のエンティティに委ねられる。例として AllocatorList KRRegionを使用した例を参照のこと。
• 割り当てられたブロックはサイズプレフィックスを保持しない。これは、D言語ではサイズ情報がクライアント・コードで では、割り当て解除時にクライアント・コードでサイズ情報を利用できるからである。

Examples:

KRRegionが必要な場合は、Region よりも汎用の deallocate アロケータが必要な場合、実際の割り当て解除トラフィックは比較的少ない。 比較的少ない。以下の例では、スタック・ストレージを使用する KRRegionスタックストレージを使う をGCアロケータのフロントとして使用している。

import std.experimental.allocator.building_blocks.fallback_allocator
    : fallbackAllocator;
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.typecons : Ternary;
// KRRegion fronting a general-purpose allocator
align(KRRegion!().alignment) ubyte[1024 * 128] buf;
auto alloc = fallbackAllocator(KRRegion!()(buf), GCAllocator.instance);
auto b = alloc.allocate(100);
writeln(b.length); // 100
writeln((() pure nothrow @safe @nogc => alloc.primary.owns(b))()); // Ternary.yes

Examples:

以下のコードは、1MB(またはそれ以上)のブロックからなるスケーラブルなアロケータを定義している。 ブロックで構成されるスケーラブル・アロケータを定義する。各ブロックは KRスタイルのヒープとして構成される。より多くのブロックが必要に応じて割り当てられ、解放される。

これはK&Rの本で紹介されているアロケータに最も近い例である。 つの大きな空きリストを検索するのではなく つの大きな空きリストを検索する代わりに、いくつかの短いリストをLRU順に検索するからである。また また、可能な場合は実際にオペレーティング・システムにメモリーを返す。

import std.algorithm.comparison : max;
import std.experimental.allocator.building_blocks.allocator_list
    : AllocatorList;
import std.experimental.allocator.mmap_allocator : MmapAllocator;
AllocatorList!(n => KRRegion!MmapAllocator(max(n * 16, 1024 * 1024))) alloc;

ParentAllocator parent;

ParentAllocator が状態を保持している場合、 parent型のパブリックメンバである。 KRRegion.そうでなければ parentのalias である。 ParentAllocator.instance.

this(ubyte[] b);

this(size_t n);

this(ParentAllocator parent, size_t n);

ParentAllocator がNullAllocator でない場合、KRRegion を作成する、 KRRegion のデストラクタは parent.deallocate.

Parameters:

ubyte[] b	アロケータをサポートするメモリのブロック。メモリは ワードより大きく、ワードアラインされていなければならない。
size_t n	容量が必要である。このコンストラクタは ParentAllocator がNullAllocator でない場合にのみ定義される。

void switchToFreeList();

フリー・リスト・モードを強制する。すでにフリー・リスト・モードになっている場合は何もしない。 そうでなければ、これまでに蓄積された空きリストをソートし、今後の割り当て戦略をKRスタイルに切り替える。 に切り替える。

enum auto alignment;

単語レベルのアライメントを行う。

void[] allocate(size_t n);

バイトを割り当てる。 nバイトを割り当てる。アロケーションは利用可能なブロックのリストを検索する。 バイト以上の空きブロックが見つかるまで nバイト以上の空きブロックが見つかるまで、利用可能なブロックのリストを検索する(最初の適合戦略)。 そのブロックは(大きければ)分割されて返される。

Parameters:

size_t n

割り当てるバイト数

Returns:

バイトのワードアラインド・バッファ。 nバイト、またはnull 。

nothrow @nogc bool deallocate(void[] b);

を割り当てる。 bこのアロケータで以前に割り当てられたと仮定される を解放する。を解放する。 ソート順を保持する。そのため のアドレスが高いブロックは、割り当て解除に時間がかかる。

Parameters:

void[] b

割り当てを解除するブロック

void[] allocateAll();

このアロケータで利用可能な全てのメモリを確保する。アロケータが空の場合 は利用可能なメモリ・ブロック全体を返す。そうでない場合は 断片化がない場合(たとえばallocate 断片化がない場合(たとえば、deallocate )、利用可能な唯一のメモリブロックを割り当てて返す。 利用可能なメモリ・ブロックを割り当てる。

この処理には、空きリストの先頭にある隣接した空きブロックの数に比例した時間がかかる。 に比例した時間がかかる。これらのブロックは allocateAllが成功しても、断片化によって失敗しても、これらのブロックは合体される。

Examples:

import std.experimental.allocator.gc_allocator : GCAllocator;
auto alloc = KRRegion!GCAllocator(1024 * 64);
const b1 = alloc.allocate(2048);
writeln(b1.length); // 2048
const b2 = alloc.allocateAll;
writeln(b2.length); // 1024 * 62

pure nothrow @nogc bool deallocateAll();

現在割り当てられているすべてのメモリを解放する。 にする。これはΟ(1) オペレーションである。

pure nothrow @nogc @trusted Ternary owns(void[] b);

の割り当てをアロケータが担当しているかどうかをチェックする。 b. 単純なΟ(1)範囲チェックを行う。 bはバッファでなければならない。 は、this で割り当てられたか、他の手段で取得されたバッファでなければならない。

static pure nothrow @nogc @safe size_t goodAllocSize(size_t n);

をアロケーションに適したサイズに調整する。 nをアロケーションに適したサイズ(2ワード以上、 ワード・アラインド)。

pure nothrow @nogc @safe Ternary empty();

Returns:

Ternary.yes アロケータが空の場合は を返す。 決して を返さない。Ternary.no Ternary.unknown