ゲーム エンジンや組み込みアプリケーションなどのパフォーマンスが重要なアプリケーションで、どのメモリ割り当てアルゴリズムがより良い結果をもたらすかを判断するために、この質問をします。結果は実際には、断片化されたメモリの割合とメモリ要求の時間決定論に依存します。
教科書にはいくつかのアルゴリズムがあります (例: Buddy メモリ割り当て) が、TLSF のようなものもあります。したがって、利用可能なメモリ割り当てアルゴリズムに関して、どれが最速で断片化が少ないか. ところで、ガベージコレクターは含まれるべきではありません。
また、この質問はプロファイリングに関するものではなく、特定の要件に最適なアルゴリズムを見つけることを目的としていることにも注意してください。
それはすべてアプリケーションに依存します。たとえば、定義された瞬間に特定の要求に関連するすべてのメモリをクリアできるサーバー アプリケーションは、ビデオ ゲームとは異なるメモリ アクセス パターンを持ちます。
パフォーマンスと断片化に常に最適なメモリ割り当てアルゴリズムが 1 つあるとしたら、実装mallocしている人々はnew常にそのアルゴリズムを選択するのではないでしょうか?
今日では、通常、オペレーティング システムとランタイム ライブラリを作成した人々は脳死状態ではなかったと想定するのが最善です。また、異常なメモリ アクセス パターンがない限り、それらを打ち負かそうとしないでください。
代わりに、行う割り当て (または再割り当て) の数を減らすようにしてください。たとえば、私は a をよく使用しますがstd::vector、要素数が事前にわかっていれば、それを一度に予約できます。これは、 を何度も呼び出して「自然に」成長させるよりもはるかに効率的ですpush_back()。
new「オブジェクトを与える」という意味の言語から来た多くの人々は、正当な理由もなく物事を割り当てます。ヒープに置く必要がない場合は、 を呼び出さないでくださいnew。
断片化に関しては、まだ依存しています。残念ながら、今はリンクを見つけることができませんが、メモリの断片化に悩まされていた C++ サーバー アプリケーションに取り組んでいた Microsoft の誰かからのブログ投稿を覚えています。チームは、2 つのリージョンからメモリを割り当てることで問題を解決しました。すべてのリクエストのメモリは、リージョン A がいっぱいになるまでリージョン A から取得されます (リクエストは通常どおりメモリを解放します)。領域 A がいっぱいになると、すべてのメモリが領域 B から割り当てられます。領域 B がいっぱいになるまでに、領域 A は再び完全に空になります。これにより、断片化の問題が解決されました。
それはあなたの問題を解決しますか？何も思いつきません。複数の独立したリクエストに対応するプロジェクトに取り組んでいますか? あなたはゲームに取り組んでいますか？
決定論に関しては：それはまだ依存しています。締め切りはいつですか？締め切りに間に合わなかった場合はどうなりますか (宇宙飛行士が宇宙で迷子になった? 再生中の音楽がゴミのように聞こえ始めた?)? リアルタイム アロケータがありますが、覚えておいてください。「リアルタイム」とは、「締め切りに間に合うことを約束する」ことを意味し、必ずしも「速い」とは限りません。
Facebook が jemalloc の断片化を高速化および削減するために行ったさまざまなことについて説明している投稿に出くわしました。その議論は面白いと思うかもしれません。
バリシュ:
あなたの質問は非常に一般的ですが、私の答え/ガイダンスは次のとおりです。
ゲーム エンジンについてはわかりませんが、組み込みおよびリアルタイム アプリケーションの場合、割り当てアルゴリズムの一般的な目標は次のとおりです。
1- 限られた実行時間: 最悪の場合の割り当て時間を事前に知っておく必要があるため、それに応じてリアルタイム タスクを計画できます。
2- 高速実行: 明らかに、高速であるほど良い
3- 常に割り当てる: 特にリアルタイムのセキュリティ クリティカルなアプリケーションの場合、すべての要求を満たす必要があります。メモリ空間を要求してヌル ポインタを取得した場合: トラブル!
4- 断片化を減らす: 使用するアルゴリズムにもよりますが、一般的に、キャッシュ効果などのさまざまな理由により、断片化の少ない割り当ての方がパフォーマンスが向上します。
ほとんどの重要なシステムでは、最初から動的にメモリを割り当てることはできません。要件を分析して最大メモリ使用量を決定し、アプリケーションが起動したらすぐに大量のメモリを割り当てます。できない場合、アプリケーションは起動さえしません。起動した場合、実行中に新しいメモリ ブロックは割り当てられません。
速度が問題になる場合は、同様のアプローチに従うことをお勧めします。メモリを管理するメモリ プールを実装できます。プールは、アプリケーションの開始時に「十分な」メモリ ブロックを初期化し、このブロックからメモリ要求を処理できます。より多くのメモリが必要な場合、プールは (より多くのメモリ要求を見越して) 別の (おそらく大規模な) 割り当てを行うことができ、アプリケーションはこの新しく割り当てられたメモリの使用を開始できます。さまざまなメモリ プール スキームもあり、これらのプールを管理することは別の全体的なトピックです。
いくつかの例について: VxWorks RTOS は、アルゴリズムがリンクされたリストを分析して十分な大きさの空きブロックを見つける最初適合の割り当てアルゴリズムを採用していました。VxWorks 6 では、ベスト フィット アルゴリズムを使用しています。このアルゴリズムでは、空き領域がツリーに保持され、割り当てがツリーを横断して十分な大きさの空きブロックを探します。Zoltan Laszlo によるというタイトルのホワイト ペーパーがありMemory Allocation in VxWorks 6.0、Google で検索すると、詳細が記載されています。
速度/断片化に関する質問に戻ります。実際には、アプリケーションによって異なります。考慮すべき事項は次のとおりです。
多くの非常に小さな割り当てを行う予定ですか、それとも比較的大きな割り当てを行う予定ですか?
割り当てはバーストで行われますか、それともアプリケーション全体に均等に分散されますか?
割り当ての有効期間は?
独自のアロケーターを実装しようとしているためにこの質問をしている場合は、おそらく、基礎となる割り当て/割り当て解除アルゴリズムを変更できるように設計する必要があります。アプリケーションでは、さまざまなアロケーターを試してみたいと思うでしょう。あなたの要件を知らずに何かを推奨する場合は、全体的な特性が優れているため、TLSF から始めます。
他の人がすでに書いたように、可能なアプリケーションごとに「最適なアルゴリズム」はありません。考えられるどのアルゴリズムでも、断片化を引き起こす割り当てシーケンスを見つけることができることはすでに証明されています。
以下に、私のゲーム開発経験からいくつかのヒントを書きます。
ゲーム開発分野での一般的な慣行は、疫病のようなメモリ割り当てを回避することで、動的メモリ割り当てのパフォーマンスの問題を解決することでした (そして、ある程度は今もそうです)。代わりにスタックベースのメモリを使用することは非常に頻繁に可能です - 動的配列の場合でも、99% のケースをカバーする見積もりが得られることが多く、この境界を超えた場合にのみ割り当てる必要があります。別の一般的に使用されるアプローチは「事前割り当て」です。一部の関数または一部のオブジェクトに必要なメモリ量を見積もり、事前に割り当てる一種の小さく単純な「ローカル ヒープ」を作成し、このヒープからのみ個々の割り当てを実行します。
もう 1 つのオプションは、いくつかのメモリ割り当てライブラリを使用することです。これらは通常、特定の要件に合わせてその分野の専門家によって作成されます。同様の要件がある場合は、要件に適合する可能性があります。
「デフォルト」の OS/CRT アロケータのパフォーマンスが悪い特定のケースが 1 つあります。それはマルチスレッドです。Windows をターゲットにしている場合は、Microsoft が提供する OS と CRT アロケータ (その他の優れた Low Fragmentation Heap を含む) の両方が現在ブロックしていることに注意してください。重要なスレッド化を実行したい場合は、割り当てを可能な限り減らすか、いくつかの代替手段を使用する必要があります。マルチスレッドはメモリ割り当てを高速化できますか?を参照してください。
ベストプラクティスは、時間内に処理を完了するために使用できるものは何でも使用することです (この場合、デフォルトのアロケーター)。全体が非常に複雑な場合は、全体の一部をエミュレートするテストとサンプルを作成します。次に、パフォーマンス テストとベンチマークを実行してボトルネックを見つけます (おそらく、メモリ割り当てとは関係ありません :)。この時点から、何がコードを正確に遅くし、その理由がわかるでしょう。このような正確な知識に基づいてのみ、何かを最適化し、あるアルゴリズムを別のアルゴリズムよりも選択することができます。テストを行わないと、最適化によってアプリがどれだけ高速化されるかを測定することさえできないため、時間の無駄になります (実際、このような「時期尚早な」最適化は実際に速度を低下させる可能性があります)。
メモリの割り当ては非常に複雑で、実際には多くの要因に依存します。たとえば、このようなアロケータはシンプルで非常に高速ですが、限られた数の状況でしか使用できません。
char pool[MAX_MEMORY_REQUIRED_TO_RENDER_FRAME];
char *poolHead = pool;
void *alloc(size_t sz) { char *p = poolHead; poolHead += sz; return p; }
void free() { poolHead = pool; }
したがって、「これまでで最高のアルゴリズム」はありません。