malloc() と free() は不適切な API です

C で動的メモリを割り当てる必要がある場合は、00 を使用します。と 11 .API は非常に古く、jemalloc、tcmalloc、mimalloc などの別の実装に切り替えたいと思うかもしれませんが、ほとんどの場合、インターフェイスをコピーします。 26 であるため、それでも残念です。と 34 メモリ割り当てには不適切な API です。

その理由を話しましょう。

C 割り当て関数

43 および 52 非常にシンプルなインターフェースを持っています:66 サイズを取り、そのサイズ 75 の割り当てられたメモリブロックへのポインタを返します以前に割り当てられたポインターを取得して解放します。

void* malloc(size_t size);

void free(void* ptr);

それから 89 もあります、ゼロ化されたメモリを割り当てます。何らかの理由で、わずかに異なるインターフェースを持っています:

void* calloc(size_t num, size_t size);

論理的には、94 を割り当てます 108 のオブジェクトそれぞれ、つまり 119 バイトです。オーバーフローチェックも行います。なぜでしょうか。

最後に、129 があります。 :

void* realloc(void* ptr, size_t new_size);

メモリブロックを 131 に拡張または縮小しようとします。 .これは、メモリ内で物事をコピーする場合とコピーしない場合があり、新しい開始アドレス、または 142 を返します。そのままにしておいた場合は変更されません。特に、154 169 の観点から実装できます :

void* malloc(size_t size)
{
    return realloc(NULl, size);
}

簡単そうに見えますが、何が問題なのですか?

問題 1:位置合わせ

普通の 179 整列されたメモリにカスタムの整列を指定することはできません。基本的な整列を持つオブジェクトに適した整列されたメモリを返します。

ページ境界に位置合わせされた SIMD ベクトルまたは何かを割り当てたいですか?ややこしい:

constexpr auto page_size = 4096;

void* allocate_page_boundary(std::size_t size)
{
    // Allocate extra space to guarantee alignment.
    auto memory = std::malloc(page_size + size);

    // Align the starting address.
    auto address = reinterpret_cast<std::uintptr_t>(memory);
    auto misaligned = address & (page_size - 1);

    return static_cast<unsigned char*>(memory) + page_size - misaligned;
}

もちろん、結果のアドレスを 181 で解放することはできませんこれは、割り当てられたメモリブロック内のどこかを指している可能性があるためです。元のアドレスも覚えておく必要があります。

少なくとも C11 は 193 を追加しました、その後 C++17 の一部になりました:

void* aligned_alloc(size_t alignment, size_t size);

これは 202 では役に立ちませんまたは 217

問題 #2:メタデータストレージ

220 直接先に進んで OS にメモリを要求するわけではありません。それでは遅すぎます。代わりに、さまざまなサイズのメモリブロック用にさまざまなキャッシュがあります。

たとえば、プログラムはしばしば 8 バイト要素を割り当てるので、8 バイトブロックのリストを保持することは理にかなっています。8 バイトを要求すると、リストから 1 つを返すだけです:

void* malloc(size_t size)
{
    if (size == 8)
        return block_list_8_bytes.pop();

    …
}

次に、8 バイトのメモリブロックを解放すると、代わりにリストに追加されます:

void free(void* ptr)
{
    if (size_of_memory(ptr) == 8)
    {
        block_list_8_bytes.push(ptr);
        return;
    }

    …
}

もちろん、これには、アロケータがポインタを指定してメモリブロックのサイズを認識している必要があります。これを行う唯一の方法は、アロケータに関するメタデータをどこかに保存することです。これは、ポインタをサイズにマップするグローバルハッシュテーブル、または追加のメタデータである可能性があります。オーバーアラインメントの例で説明したように、アドレスの直前に格納します。いずれの場合も、8 バイトのメモリを要求しても、実際には 8 バイトのメモリが割り当てられるのではなく、追加のメタデータも割り当てられることを意味します。

ユーザーは通常、現在解放しようとしているメモリブロックの大きさを知っているため、これは特に無駄です!

template <typename T>
class dynamic_array
{
    T* ptr;
    std::size_t size;

public:
    explicit dynamic_array(T* ptr, std::size_t size)
    : ptr(static_cast<T*>(std::malloc(size * sizeof(T))))
    {}

    ~dynamic_array()
    {
        … // call destructors

        // I know that I'm freeing size * sizeof(T) bytes!
        std::free(ptr);
    }
};

234 の場合追加のパラメーターとしてメモリブロックのサイズを取得したため、実装ではそのためだけに追加のメタデータを追加する必要はありません。

問題 #3:スペースの浪費

248 の実装を検討してください .追加の要素を格納する容量がない場合、より大きなメモリを予約してすべてを移動する必要があります.償却された O(1) の複雑さを維持するために、新しいメモリを何らかの係数で増やします:

void push_back(const T& obj)
{
    if (size() == capacity())
    {
        auto new_capacity = std::max(2 * capacity(), 1);
        auto new_memory = std::malloc(new_capacity * sizeof(T));

        …
    }

    …
}

これは機能しますが、メモリを浪費する可能性があります。

251 の実装を想定します。最近解放されたメモリブロックのキャッシュを使用します。260 を割り当てようとするとブロック、少なくとも 278 であるブロックのキャッシュを検索します 1 つ (適合する最初のもの、または適合する最小のもの、または…) が見つかった場合は、それを返します。その場合、返されたメモリブロックには、284 バイト!

これは、たとえば 1 枚分の容量のメモリを要求することを意味します。 14 要素ですが、代わりに 16 要素の容量を持つメモリブロックを取得します。しかし、私たちはそれを知りません!ブロックを 14 要素のみのスペースがあるかのように扱い、15 番目の要素に対して別の不要な再割り当てをトリガーします。

296 ならいいですね割り当てられたメモリブロックの実際の大きさを返すことができるので、「無料で」取得した可能性のある余分なスペースを活用できます。

問題 #4:`306`

316 インプレースでメモリブロックを拡張しようとします。それが不可能な場合は、新しいブロックを割り当て、既存の内容をコピーします。これは、327 によって行われたかのように行われます。 .

この自動コピーには問題があります。

まず、ムーブコンストラクターを呼び出す可能性のある C++ オブジェクトでは使用できません。また、循環リンクリストを含むバッファーなどの自己参照ポインターを持つ C オブジェクトでは機能しません。

これは 334 として残念ですメモリブロックをインプレースで拡張するの機能は非常に便利で、他の方法では達成できません。 343 .

インターフェースの改善

それらの欠点を持たない新しいインターフェイスを提案させてください。それは 3 つの関数で構成されています 354 、 360 、および 372 .

382 395 の置き換えです .これの目標は、指定されたサイズとアラインメントにメモリブロックを割り当てることです。重要なのは、割り当てられたメモリへのポインタだけでなく、ユーザーが使用できる合計サイズも返すことです。

struct memory_block
{
    void* ptr;
    size_t size;
};

/// On success `result.ptr != NULL` and `result.size >= size`.
/// On failure, `result.ptr == NULL` and `result.size == 0`.
memory_block allocate(size_t size, size_t alignment);

これにより、問題 #1 と #3 が処理されます。

406 416 の置き換えです .425 かかります同様に、このブロックを要求するために使用されたアライメントに加えて:

void deallocate(memory_block block, size_t alignment);

このようにして、とにかく呼び出し元が持っているすべての情報をアロケーターに渡します。

最後に 430 443 の置き換えです .重要なのは、ブロックをその場で拡張しようとするだけで、それが不可能な場合は失敗することです.

/// If the block can be expanded in-place to `new_size`, returns true.
/// Otherwise, returns `false`.
bool try_expand(memory_block block, size_t new_size);

これにより、必要に応じて割り当てられたメモリをコピーする責任を呼び出し元に持たせることで、問題 #4 が解決されます。

C++ ソリューション

C++ の 451 と 468 、同じ問題を継承しています:

void* operator new(std::size_t size);
void operator delete(void* ptr);

// not pictured: dozens of other overloads

その名誉のために、それは改善を続けています.

C++17:アラインメント割り当て

C++17 は、475 を受け入れるオーバーロードを追加します、これにより、カスタムの配置を指定できます。

void* operator new(std::size_t size, std::align_val_t alignment);
void operator delete(void* ptr, std::align_val_t alignment);

C++17:サイズ化された割り当て解除

ユーザーは実際に 485 の独自の実装を定義できます /499 すべてのメモリ割り当てを制御します。これは、メモリを割り当てるためにコンパイラによって呼び出されます。C++17 以降、コンパイラは次のオーバーロードも呼び出そうとします:

void operator delete(void* ptr, std::size_t size);
void operator delete(void* ptr, std::size_t size, std::align_val_t alignment);

コンパイラは割り当てを解除するオブジェクトのサイズを認識しているため、その情報を関数に渡すことができます。カスタムアロケーターの実装を作成している場合は、メタデータについて心配する必要はありません。

もちろん、これは 505 を使用するデフォルトの実装には役立ちませんおよび 515 .

C++23:`528` のサイズフィードバック

C++23 は 530 に新しい機能を追加する P0401 を採用しました。 :

template<class Pointer>
struct allocation_result
{
    Pointer ptr;
    size_t count;
};

class allocator
{
public:
     allocation_result<T*> allocate_at_least(size_t n);
};

この関数は、少なくとも n 個のオブジェクトにメモリを割り当て、使用可能なメモリの実際のサイズを返します。これは、私の提案した 544 のように動作します。関数。

557 の変更を伴う言語側 P0901 によって提案されたように、まだ標準化プロセスにあり、できれば C++26 で提供される予定です。