2

C 構造体などの固定長データ型があるとします。

struct T
{
    ...;
}

T を割り当てる 1 つの方法は次のとおりです。

T* create_t() { return (T*) malloc(sizeof(T)); }

および割り当て解除:

void destroy_t(T* t) { free(t); }

内部的には、malloc はさまざまなサイズのブロックをさまざまな方法で処理するメモリ割り当てアルゴリズムを使用します。

create_t と destroy_t を頻繁に呼び出し、非常に多くの T アイテムを一度に (疑似ランダムな順序で) 割り当てるプログラムを書いているとします。

必要なメモリが固定サイズの要素であることを考えると、malloc の一般的な実装よりも優れたカスタム メモリ割り当てスキームを作成することは可能ですか。

たとえば、サイズ T の要素を持つ巨大な配列を事前に割り当ててから使用することもできますが、どの要素が割り当てられ、どの要素が割り当てられていないかを追跡する最良の方法は何ですか?

同じサイズの膨大な数の割り当てで呼び出されたときに、Linux の malloc が最終的に使用するアルゴリズムは何ですか?

このカスタム メソッドのパフォーマンスは、一般的な malloc と比べてどの程度でしょうか?

4

4 に答える 4

3

#1 に関しては — 他の人が処理したことはありますが、要するに、glibc はかなり良い仕事をしており、他の malloc はさまざまな状況下でよりうまく機能する可能性があります。

ただし、2 番目の質問については、カスタムのパフォーマンスはどうですか?

• 一般に、アプリケーション独自の使用パターンとニーズを認識しているフリー リスト アロケーターの低レベル実装は、GNU libc が提供するような一般的なケースのアルゴリズムよりもパフォーマンスが優れている可能性があります。

• しかし、あなたは物事を書くことによってそれを証明しなければなりません。

Custom malloc for many small, fixed size blocks に関連する回答がいくつかありますか? 、 ところで。

また、さまざまなファイルシステム ドライバーでのディスク セクターの使用状況の表現を参照することもできます。これらのドライバーは、同じことを効果的に解決します — 固定サイズのブロック/セクターは、さまざまな負荷の下で疑似ランダムな間隔で割り当てられます — 一方、ほとんどの malloc は一般的であることに集中します-目的。

于 2012-09-28T22:21:15.130 に答える
2

まず、 のいくつかの実装を持つことができますmalloc。たとえば、Glibc malloc (説明はこちら) はhere ですが、musl libc malloc はhereです。また、 C 動的メモリ実装の多様性はよく知られています。

また、実装が次のように単純であることにも注意してください。

void *malloc (size_t sz)
{
   errno = ENNOMEM;
   return 0;
}

おそらく、malloc の標準仕様(Posix や C99 など) の文字には準拠していますが、その精神には準拠していません。

実際には、 mmap(2)や場合によってはsbrk(2)などのシステムコールを介してLinux カーネルにいくつかのメモリ チャンクmallocを要求することによって実装されます。これらはすべて仮想メモリとアドレス空間に関連しています。ASLRのため、プログラムの実行ごとに の結果が異なる場合があります。同じサイズの多くの割り当てを処理できますが、非常に長時間実行されているプログラムではメモリの断片化が発生する可能性があります。munmap(2)mallocmalloc

glib メモリ スライスのようなスライス アロケータなどを使用することもできますが、ほとんど役に立ちません。また、 Boehm の保守的なガベージ コレクタを使用することもできます(たとえば、データを明示的に指定する代わりに使用しGC_mallocてください)。mallocfree

実際には、Linux ではmalloc非常にうまく機能します。気にする必要はないと思います。もちろん、メモリ割り当ての低レベル操作を最小限に抑えるように設計されていますmmap(これは高価です。適切な実装では、メモリのプールを適切に管理し、カーネルから要求する前に -d メモリmallocの再利用を試みます)。freeマルチスレッドなどに関連する問題もあります。

アプリケーションのコスト削減に悩む前に、mallocそれを測定する必要があります ( valgrindmallocは、関連するバグのデバッグにも役立ちます)。多くの場合、コストはmallocアプリケーションではそれほど重要ではありません。本当に必要な場合は、自分のメモリ アリーナを管理できますが、気にする必要があるかどうかはわかりません。(最適化する前に最初に測定します)。今日のマシンでは、キャッシュの考慮事項もコードの実際のパフォーマンスに大きく影響します。

于 2012-09-28T22:07:02.350 に答える
2

私の知る限り、使用されているメモリ管理は一種の「バケット」管理です。

malloc空きメモリ セグメントをバケットに保持し、呼び出されると、最適なブロックの 1 つを呼び出し元に渡そうとします。

しかし、libc のソースをダウンロードして、自分の目で確かめてみてください。

また、メモリ管理の作成は非常に難しく、現在使用されているアルゴリズムには多くの労力が費やされています。私は、これらすべての人がやったよりも良いものを思いつくのは（特に一人の人間として）非常に難しいと信じています.

于 2012-09-28T21:54:29.837 に答える
0

Q: 必要なメモリが固定サイズの要素であることを考えると、malloc の一般的な実装よりも優れたカスタム メモリ割り当てスキームを作成することは可能ですか?

A: たぶん。それはおそらく重要な仕事でしょう。

特定の OS では、"malloc()" の実装が異なる可能性があります。(たとえば) Linux の標準は Gnu Libc です。ここでソースを見つけることができます：

「お役に立てば幸いです！

于 2012-09-28T22:03:25.927 に答える