このページの英語版を見る

std.experimental.allocator.building_blocks.bitmapped_block

ソース std/experimental/allocator/building_blocks/bitmapped_block.d

struct BitmappedBlock(size_t theBlockSize, uint theAlignment = platformAlignment, ParentAllocator = NullAllocator, Flag!"multiblock" f = Yes.multiblock);

BitmappedBlockは、1つの連続した領域からなる単純なヒープを実装している。 theBlockSizeで構成される単純なヒープを実装している。ブロックは割り当ての単位である。割り当ての単位である。ビットマップはブックキーピング・データとして機能する。ブロックごとに1ビットで、そのブロックが現在割り当てられているかどうかを示す。

NullAllocator (デフォルト)をParentAllocator (デフォルト)として渡すと、ユーザー・コードが外部からメモリ・ブロックの割り当てを管理することになる。が外部からメモリ・ブロックの割り当てを管理することを意味する。 BitmappedBlockこの場合、ubyte[] で事前に割り当てられたブロックを使って構築されなければならない。この場合、で構築されなければならず、サポートするストレージの寿命に関する責任はない。他のアロケータ型が渡された場合は、次のようになる、 BitmappedBlockはデストラクタを定義する。を定義する。これによって、AllocatorList 、 BitmappedBlockのようなバックエンドのアロケータとの組み合わせは、メモリ割り当てのためのシンプルでスケーラブルなソリューションになる。MmapAllocator のようなバックエンドのアロケータとの組み合わせは、メモリ割り当てのためのシンプルでスケーラブルなソリューションとなる。

ブックキーピング・データをペイロードから分離して保存することには利点がある。 (例えば、AffixAllocator を使ってメタデータを各アロケーションと一緒に保存するのとは対照的だ)。を使うのとは対照的である)。レイアウトがよりコンパクトになる(オーバーヘッドはブロックあたり1ビット)、アロケーション中に空きブロックを探すと、キャッシュのローカリティが向上する。また、割り当ての解除は、解除されるペイロードの周りのメモリに触れない(コールドであることが多い)。コールドであることが多い)。

割り当てリクエストは、ファースト・フィット・ベースで処理される。複雑さは直線的だが複雑さは線形であるが、コンパクトな簿記表現、シンプルで高速なビット単位ルーチンの使用、およびシンプルで高速なビット単位のルーチンを使用し、最初に利用可能なブロック位置をキャッシュするためである。をキャッシュするためである。この一般的な手法の既知の問題は断片化であるが、合体によって部分的に軽減される。というのも BitmappedBlock合体割り当てられたサイズを維持する必要がないため、メモリの解放は暗黙のうちに空きブロック同士を合体させる。される。また、blockSize のチューニングは、内部と外部のフラグメンテーションにかなりの影響を与える。また、チューニングは内部と外部のフラグメンテーションに大きな影響を与える。

最後のテンプレート・パラメータがNo.multiblock に設定されている場合、アロケータは最大でを必要とするアロケーションのみを提供する。 theBlockSizeを必要とするアロケーションのみを提供する。この BitmappedBlockはシングルブロック割り当てに特化したにはシングルブロック割り当てに特化した実装があり、より高いパフォーマンスを可能にしている、その代償として、一度に複数のブロックを割り当てることができない。

各ブロックのサイズはコンパイル時または実行時に選択できる。で選択できる。静的に既知のブロック・サイズは、実際には頻繁に使用され、パフォーマンスをわずかに向上させる。パフォーマンスが若干向上する。ブロック・サイズを静的に選択するには、ブロック・サイズをblockSize パラメータとして渡す。 BitmappedBlock!(4096).のようにパラメータとして渡す。サイズのパラメータを選ぶには BitmappedBlock!(chooseAtRuntime)を使いを使ってコンストラクタに渡す。

Parameters:

theBlockSize	ブロックの長さは、その倍数でなければならない。theAlignment
theAlignment	各ブロックのアラインメント
ParentAllocator	のアラインメントの倍数でなければならない。 `BitmappedBlock`がメモリを引き出す各ブロック・アロケータのアライメントの倍数でなければならない。 NullAllocator に設定した場合は、複数のブロックにまたがる割り当てをサポートするために、コンストラクタ経由でストレージを渡さなければならない。
f	Yes.multiblock に設定すると、複数のブロックにまたがる割り当てをサポートするために、ストレージはコンストラクタ経由で渡されなければならない。に設定すると、単一ブロック割り当てをサポートするために、コンストラクタでストレージを渡さなければならない。シングル・ブロック・アロケーションには制限があるが、。の方が高いパフォーマンスを提供する。No.multiblock No.multiblock

Examples:

// Create a block allocator on top of a 10KB stack region.
import std.experimental.allocator.building_blocks.region : InSituRegion;
import std.traits : hasMember;
InSituRegion!(10_240, 64) r;
auto a = BitmappedBlock!(64, 64)(cast(ubyte[])(r.allocateAll()));
static assert(hasMember!(InSituRegion!(10_240, 64), "allocateAll"));
const b = a.allocate(100);
writeln(b.length); // 100

Examples:

import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Flag, Yes;

enum blockSize = 64;
enum numBlocks = 10;

// The 'BitmappedBlock' is implicitly instantiated with Yes.multiblock
auto a = BitmappedBlock!(blockSize, 8, Mallocator, Yes.multiblock)(numBlocks * blockSize);

// Instantiated with Yes.multiblock, can allocate more than one block at a time
void[] buf = a.allocate(2 * blockSize);
writeln(buf.length); // 2 * blockSize
assert(a.deallocate(buf));

// Can also allocate less than one block
buf = a.allocate(blockSize / 2);
writeln(buf.length); // blockSize / 2

// Expands inside the same block
assert(a.expand(buf, blockSize / 2));
writeln(buf.length); // blockSize

// If Yes.multiblock, can expand past the size of a single block
assert(a.expand(buf, 3 * blockSize));
writeln(buf.length); // 4 * blockSize
assert(a.deallocate(buf));

Examples:

import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Flag, No;

enum blockSize = 64;
auto a = BitmappedBlock!(blockSize, 8, Mallocator, No.multiblock)(1024 * blockSize);

// Since instantiated with No.multiblock, can only allocate at most the block size
void[] buf = a.allocate(blockSize + 1);
assert(buf is null);

buf = a.allocate(blockSize);
writeln(buf.length); // blockSize
assert(a.deallocate(buf));

// This is also fine, because it's less than the block size
buf = a.allocate(blockSize / 2);
writeln(buf.length); // blockSize / 2

// Can expand the buffer until its length is at most 64
assert(a.expand(buf, blockSize / 2));
writeln(buf.length); // blockSize

// Cannot expand anymore
assert(!a.expand(buf, 1));
assert(a.deallocate(buf));

this(ubyte[] data); this(ubyte[] data, uint blockSize); this(size_t capacity); this(ParentAllocator parent, size_t capacity); this(size_t capacity, uint blockSize); this(ParentAllocator parent, size_t capacity, uint blockSize);

ブロック・アロケータを構築する。バイト単位で与えられる。

ParentAllocator が NullAllocator, を取るコンストラクタのみが定義され dataを取るコンストラクタのみが定義され、ユーザーは必要に応じて dataを解放する責任がある。
そうでない場合は、両方のコンストラクタが定義される。その data-ベースのコンストラクタは、親アロケータでメモリが確保されていることを前提とする。ベースのコンストラクタは capacity-ParentAllocator を使う。を使う。使用するコンストラクタにかかわらず、デストラクタはParentAllocator.deallocate を使ってメモリを解放する。

alias blockSize = theBlockSize;

もし blockSize == chooseAtRuntimeの場合、BitmappedBlock は読み書き可能なプロパティを提供する。 blockSize.アロケータを使用する前に設定しなければならない。そうでない場合(つまり、theBlockSize は正当な定数である)、 blockSizeは theBlockSize のエイリアスである。定数でも変数でも、の倍数でなければならない。 alignment assertの倍数でなければならない。と動的に編集される。

alias alignment = theAlignment;

提供されるアライメントは、パラメータを通じて静的にユーザー設定可能である。 theAlignment デフォルトはplatformAlignment である。

ParentAllocator parent;

親アロケータ。ParentAllocator 。を保持しているかどうかによって、これはメンバ変数または ParentAllocator.instance.

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

が要求されたときに実際に割り当てられたバイト数を返す。 nバイトが要求されたときに実際に割り当てられたバイトを返す。 n.roundUpToMultipleOf(blockSize).

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

に属する場合はTernary.yes を返す。 bがBitmappedBlock オブジェクトに属する、 Ternary.no そうでなければ決してTernary.unkown を返さない。 (このメソッドは、内部スライスを受け付けるという点で、多少寛容である)。

pure nothrow @nogc @trusted bool expand(ref void[] b, immutable size_t delta);

BitmappedBlock によって以前に割り当てられたバッファを拡張する。 No.multiblock でインスタンス化された場合、新しい長さがを超えると、拡張は失敗する。 theBlockSize でインスタンス化された場合、拡張は失敗する。

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

このアロケータで以前に割り当てられたブロックを解放する。

pure nothrow @nogc @trusted void[] allocate(const size_t s);

バイトのメモリを割り当て、それを返す。 snull バイトのメモリを確保し、それを返す。を返す。

適切なブロックサイズを選択するために、以下の情報が役に立つだろう。ブロック・サイズの選択に役立つかもしれない。実際の割り当ては、ブロック・サイズの倍数のサイズで行われる。 1ブロックを割り当てるのが最も速い。メタデータで見つける必要があるのは0ビットだけだからである。2ブロックから64ブロックの割り当ては、次に安い。というのも、メタデータのulong 。 64ブロックを超える割り当ては、メタデータを複数ワードで検索する必要がある。メタデータを検索する必要がある。

No.multiblock でインスタンス化された場合、ビットマップの最初のゼロビットを検索し、それを設定する。ビットを検索して設定する。

@trusted void[] allocateFresh(const size_t s);

sバイトのメモリを確保し、それを返す。メモリを確保できなかった場合はnull を返す。 allocateFreshはallocateと同じように動作する。は常に未使用の(新しい)メモリを返すという点だけが異なる。BitmappedBlock にはまだ空き領域があるかもしれないが、 allocateFreshにはまだ利用可能な領域があるかもしれないが、利用可能なブロックはすべて以前に割り当て解除されているため、nullを返す可能性がある。

void[] allocateAll();

BitmappedBlock オブジェクトが空の場合(アクティブな割り当てがない)、その中のすべてのメモリを割り当て、スライスを返す。スライスを返す。そうでない場合はnull (を返す(つまり、利用可能な最大のブロックを割り当てようとはしない)。

pure nothrow @nogc @safe Ternary empty();

このアロケータで現在割り当て中のメモリがない場合はTernary.yes を返し、そうでない場合はを返す。を返し、そうでなければTernary.no を返す。このメソッドは Ternary.unknown.

pure nothrow @nogc bool deallocateAll();

このアロケータによって割り当てられたすべてのメモリを強制的に解放する。さらに割り当てることができるようにする。ParentAllocator にはメモリを返さない。

@system bool alignedReallocate(ref void[] b, size_t newSize, uint a);

以前にalignedAllocate で割り当てられたブロックを再割り当てする。その場では "契約"は発生しない。

@system bool reallocate(ref void[] b, size_t newSize);

以前に割り当てられたブロックを再割り当てする。その場で縮小が発生する。

void[] alignedAllocate(size_t n, uint a);

指定されたアラインメントでブロックを割り当てる。 a.アラインメントは2のべき乗でなければならない。のべき乗でなければならない。 a <= alignmentの場合、"関数"はallocate に進む。そうでない場合は、オーバーオールを試み、その結果を適切なアライメントになるように調整する。を調整する。最悪の場合、スラックメモリは2ブロック程度となる。

struct SharedBitmappedBlock(size_t theBlockSize, uint theAlignment = platformAlignment, ParentAllocator = NullAllocator, Flag!"multiblock" f = Yes.multiblock);

スレッドセーフ・バージョンの BitmappedBlock. のセマンティクスは SharedBitmappedBlockのセマンティクスは、通常の BitmappedBlock.

Parameters:

theBlockSize	の倍数でなければならない。theAlignment
theAlignment	各ブロックのアラインメント
ParentAllocator	BitmappedBlock がメモリを引き出すアロケータ。 NullAllocator に設定された場合、複数のブロックにまたがる割り当てをサポートするために、ストレージはコンストラクタ経由で渡されなければならない。
f	Yes.multiblock に設定された場合、ストレージはコンストラクタ経由で渡されなければならない。単一ブロック割り当てをサポートする。シングル・ブロック・アロケーションには制限があるが、一般的に。の方が高いパフォーマンスを提供する。No.multiblock No.multiblock

Examples:

import std.experimental.allocator.mallocator : Mallocator;
import std.experimental.allocator.common : platformAlignment;
import std.typecons : Flag, Yes, No;

// Create 'numThreads' threads, each allocating in parallel a chunk of memory
static void testAlloc(Allocator)(ref Allocator a, size_t allocSize)
{
    import core.thread : ThreadGroup;
    import std.algorithm.sorting : sort;
    import core.internal.spinlock : SpinLock;

    SpinLock lock = SpinLock(SpinLock.Contention.brief);
    enum numThreads = 10;
    void[][numThreads] buf;
    size_t count = 0;

    // Each threads allocates 'allocSize'
    void fun()
    {
        void[] b = a.allocate(allocSize);
        writeln(b.length); // allocSize

        lock.lock();
        scope(exit) lock.unlock();

        buf[count] = b;
        count++;
    }

    auto tg = new ThreadGroup;
    foreach (i; 0 .. numThreads)
    {
        tg.create(&fun);
    }
    tg.joinAll();

    // Sorting the allocations made by each thread, we expect the buffers to be
    // adjacent inside the SharedBitmappedBlock
    sort!((a, b) => a.ptr < b.ptr)(buf[0 .. numThreads]);
    foreach (i; 0 .. numThreads - 1)
    {
        assert(buf[i].ptr + a.goodAllocSize(buf[i].length) <= buf[i + 1].ptr);
    }

    // Deallocate everything
    foreach (i; 0 .. numThreads)
    {
        assert(a.deallocate(buf[i]));
    }
}

enum blockSize = 64;
auto alloc1 = SharedBitmappedBlock!(blockSize, platformAlignment, Mallocator, Yes.multiblock)(1024 * 1024);
auto alloc2 = SharedBitmappedBlock!(blockSize, platformAlignment, Mallocator, No.multiblock)(1024 * 1024);
testAlloc(alloc1, 2 * blockSize);
testAlloc(alloc2, blockSize);

ブロック・アロケータを構築する。バイト単位で与えられる。

ParentAllocator が NullAllocator, を取るコンストラクタのみが定義され dataを取るコンストラクタのみが定義され、ユーザーは必要に応じて dataを解放する責任がある。
そうでない場合は、両方のコンストラクタが定義される。その data-ベースのコンストラクタは、親アロケータでメモリが確保されていることを前提とする。ベースのコンストラクタは capacity-ParentAllocator を使う。を使う。使用するコンストラクタにかかわらず、デストラクタはParentAllocator.deallocate を使ってメモリを解放する。

alias blockSize = theBlockSize;

もし blockSize == chooseAtRuntimeの場合、SharedBitmappedBlock は読み書き可能なプロパティを提供する。 blockSize.アロケータを使用する前に設定しなければならない。そうでない場合(つまり、theBlockSize は正当な定数である)、 blockSizeは theBlockSize のエイリアスである。定数でも変数でも、の倍数でなければならない。 alignment assertの倍数でなければならない。と動的に編集される。

alias alignment = theAlignment;

提供されるアライメントは、パラメータを通じて静的にユーザー設定可能である。 theAlignment デフォルトはplatformAlignment である。

ParentAllocator parent;

親アロケータ。ParentAllocator 。を保持しているかどうかによって、これはメンバ変数または ParentAllocator.instance.

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

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

に属する場合はTernary.yes を返す。 bがSharedBitmappedBlock オブジェクトに属する、 Ternary.no そうでなければ決してTernary.unkown を返さない。 (このメソッドは、内部スライスを受け付けるという点で、多少寛容である)。

bool expand(ref void[] b, immutable size_t delta);

SharedBitmappedBlock によって割り当てられたバッファを拡張する。新しい長さがブロックサイズを超える場合、拡張は失敗する。

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

与えられたバッファを解放する。 b対応するビットをアトミックに0 にセットすることで、与えられたバッファを解放する。 bは有効でなければならず、隣接する複数のblocks を含むことはできない。

nothrow @nogc @trusted void[] allocate(const size_t s);

バイトのメモリを確保し、それを返す。 snull バイトのメモリを確保し、それを返す。を返す。

SharedBitmappedBlock は、与えられたブロックサイズ以上を割り当てることはできない。割り当ては、ビットマップの最初の未設定ビットを検索し、それをアトミックに設定することで行われる、アトミックに設定する。稀にメモリが圧迫されるシナリオでは、割り当てに失敗する可能性がある。

@trusted void[] allocateFresh(const size_t s);

sバイトのメモリを割り当て、それを返す。メモリを割り当てられなかった場合はnull を返す。 allocateFreshはallocateと同じように動作する。は常に未使用の(新しい)メモリを返すという点だけが異なる。SharedBitmappedBlock にはまだ空き領域があるかもしれないが、 allocateFreshにはまだ利用可能な領域があるかもしれないが、利用可能なブロックはすべて以前に割り当て解除されているため、nullを返す可能性がある。

void[] allocateAll();

SharedBitmappedBlock オブジェクトが空の場合(アクティブな割り当てがない)、その中のすべてのメモリを割り当て、スライスを返す。スライスを返す。そうでない場合はnull (を返す(つまり、利用可能な最大のブロックを割り当てようとはしない)。

nothrow @nogc @safe Ternary empty();

このアロケータで割り当て中のメモリがない場合はTernary.yes を返し、そうでない場合はを返す。を返し、そうでなければTernary.no を返す。このメソッドは Ternary.unknown.

nothrow @nogc bool deallocateAll();

@system bool alignedReallocate(ref void[] b, size_t newSize, uint a);

以前にalignedAllocate で割り当てられたブロックを再割り当てする。その場では "契約"は発生しない。

@system bool reallocate(ref void[] b, size_t newSize);

以前に割り当てられたブロックを再割り当てする。その場で縮小が発生する。

void[] alignedAllocate(size_t n, uint a);

struct BitmappedBlockWithInternalPointers(size_t theBlockSize, uint theAlignment = platformAlignment, ParentAllocator = NullAllocator);

resolveInternalPointer をサポートするための追加構造を持つBitmappedBlock 。そのために BitmappedBlockWithInternalPointersを追加する。ビットマップ(1ブロックにつき1ビット)を追加する。ビットマップ自体は通常の割り当てと一緒に割り当てられる。

resolveInternalPointer の時間複雑度はΟ(k)である。k は内部ポインタが検索されるオブジェクトのサイズである。

this(ubyte[] data); this(size_t capacity); this(ParentAllocator parent, size_t capacity);: コンストラクタは、希望する容量または事前に割り当てられたバッファを受け付ける。 BitmappedBlock のセマンティクスに似ている。
alias alignment = theAlignment; pure nothrow @nogc @safe size_t goodAllocSize(size_t n); void[] allocate(size_t bytes); void[] allocateAll(); bool expand(ref void[] b, size_t bytes); bool deallocate(void[] b); nothrow @nogc @safe Ternary resolveInternalPointer(const void* p, ref void[] result); Ternary empty();: アロケータ・プリミティブ。

DEEPL APIにより翻訳、ところどころ修正。
このページの最新版(英語)
このページの原文(英語)
翻訳時のdmdのバージョン: 2.108.0
ドキュメントのdmdのバージョン: 2.109.1
翻訳日付 :2024-04-15 11:17:01+09:00
HTML生成日時: 2025-01-09 08:11:53+09:00
編集者: dokutoku

言語リファレンス

std.experimental.allocator.building_blocks.bitmapped_block