多数の小さなブロック (32-64b) を割り当てて割り当てを解除する、単一のスレッド化された組み込みアプリケーションがあります。キャッシュベースのアロケーターの完璧なシナリオ。そして、私はそれを書くことを試みることができましたが、おそらく時間の無駄であり、すでに最前線にあるいくつかのソリューションほど十分にテストおよび調整されていません.
では、このシナリオで使用できる最良のアロケーターは何でしょうか?
注: システムで Lua 仮想マシン (割り当ての 80% 以上の原因) を使用しているため、スタック割り当てを使用して割り当てのパフォーマンスを向上させるようにコードを簡単にリファクタリングすることはできません。
パーティーには少し遅れましたが、最近見つけてテストした組み込みシステム用の非常に効率的なメモリ アロケータを共有したいと思います: https://github.com/dimonomid/umm_malloc
これは、ARM7 で動作するように特別に設計されたメモリ管理ライブラリです。個人的には PIC32 デバイスで使用していますが、16 ビットおよび 8 ビット デバイスで動作するはずです (16 ビット PIC24 でテストする計画がありますが、私はまだテストしていません）
デフォルトのアロケータを使用した場合、断片化にひどく打ちのめされました。私のプロジェクトでは、数バイトから数百バイトまでさまざまなサイズのブロックが割り当てられることが多く、「メモリ不足」エラーに直面することもありました。私の PIC32 デバイスには合計 32K の RAM があり、8192 バイトがヒープに使用されています。特定の瞬間に 5K を超える空きメモリがありますが、フラグメンテーションのために、デフォルトのアロケータには、断片化されていない最大メモリ ブロックが約 700 バイトしかありません。これは残念なので、より効率的な解決策を探すことにしました。
私はすでにいくつかのアロケーターを認識していましたが、それらすべてにいくつかの制限があるか (ブロックサイズは 2 のべき乗である必要があり、2 からではなく、たとえば 128 バイトから開始するなど)、または単にバグがありました。以前は毎回、デフォルトのアロケータに戻さなければなりませんでした。
しかし、今回は幸運です。これを見つけました: http://hempeldesigngroup.com/embedded/stories/memorymanager/
このメモリ アロケータを試してみたところ、空きメモリが 5K の場合とまったく同じ状況で、3800 バイトを超えるブロックがありました。私には信じられないほど (700 バイトと比較して)、ハードテストを実行しました。デバイスは 30 時間以上も重く動作しました。メモリ リークはなく、すべて正常に動作します。また、FreeRTOS リポジトリでこのアロケータを見つけました: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041#、およびこれ事実は、umm_malloc の安定性の追加の証拠です。だから私は完全にumm_mallocに切り替えました。私はそれにとても満足しています。
少し変更する必要がありました。マクロ UMM_TEST_MAIN が定義されていない場合、構成に少しバグがあったため、github リポジトリを作成しました (リンクはこの投稿の上部にあります)。現在、ユーザー依存の構成は別のファイル umm_malloc_cfg.h に保存されています。
このアロケータに適用されているアルゴリズムについてはまだ深く理解していませんが、アルゴリズムについて非常に詳細に説明されているので、興味のある人は誰でもファイル umm_malloc.c の先頭を見ることができます。少なくとも、「ビニング」アプローチは、断片化の少ないことに大きな利益をもたらすはずです: http://g.oswego.edu/dl/html/malloc.html
マイクロコントローラ用の効率的なメモリ アロケータが必要な人は、少なくともこれを試してみるべきだと思います。
CI で取り組んだ過去のプロジェクトでは、組み込みシステムを含むさまざまなプラットフォームで実行されるライブラリ用に独自のメモリ管理ルーチンを実装する道をたどりました。ライブラリはまた、多数の小さなバッファを割り当てて解放しました。比較的うまく動作し、実装に大量のコードは必要ありませんでした。自分で何かを開発したい場合に備えて、その実装の背景を少し説明できます。
基本的な実装には、一定サイズのバッファを管理する一連のルーチンが含まれていました。ルーチンは、malloc() と free() のラッパーとして使用されました。これらのルーチンを使用して、頻繁に使用する構造体の割り当てを管理し、設定されたサイズの汎用バッファーも管理しました。管理される各タイプのバッファーを記述するために、構造が使用されました。特定のタイプのバッファが割り当てられると、メモリをブロック単位で malloc() します (空きバッファのリストが空の場合)。IE で 10 バイトのバッファを管理している場合、100 個のこれらのバッファ用のスペースを含む単一の malloc() を作成して、断片化と必要な基礎となる malloc の数を減らすことができます。
各バッファーの先頭には、フリー リスト内のバッファーをチェーンするために使用されるポインターがあります。100 個のバッファが割り当てられると、各バッファはフリー リスト内でチェーン化されます。バッファーが使用中の場合、ポインターは null に設定されます。また、バッファの「ブロック」のリストも保持していたので、実際に malloc された各バッファで free() を呼び出すことで簡単なクリーンアップを行うことができました。
動的なバッファー サイズを管理するために、各バッファーの先頭にバッファーのサイズを示す size_t 変数も追加しました。これは、バッファが解放されたときにバッファを戻すバッファブロックを識別するために使用されました。ポインター演算を行ってバッファー サイズを取得し、バッファーをフリー リストに入れる、malloc() と free() の代替ルーチンがありました。また、管理するバッファの大きさにも制限がありました。この制限より大きいバッファーは、単純に malloc されてユーザーに渡されました。管理する構造については、特定の構造の割り当てと解放のためのラッパー ルーチンを作成しました。
最終的には、ユーザーが未使用のメモリをクリーンアップするように要求したときに、ガベージ コレクションを含めるようにシステムを進化させました。私たちはシステム全体を管理していたので、システムのパフォーマンスを向上させるために時間をかけてさまざまな最適化を行うことができました。前述したとおり、それは非常にうまく機能しました。
メモリの断片化に問題があったため、最近このトピックについて調査を行いました。最終的に、GNU libc の実装にとどまり、必要に応じてアプリケーション レベルのメモリ プールを追加することにしました。より優れた断片化動作を持つアロケーターは他にもありましたが、それらが malloc をグローバルに置き換えることに満足していませんでした。GNU には、その背後にある長い歴史の利点があります。
あなたの場合、それは正当なようです。VM を修正できないと仮定すると、これらの小さな割り当ては非常に無駄になります。環境全体が何であるかはわかりませんが、小さなプール用に設計されたハンドラーに渡すことができるように、VM だけで malloc/realloc/free への呼び出しをラップすることを検討してください。
これを尋ねてからしばらく経ちましたが、私の最終的な解決策は、LoKi の SmallObjectAllocator を使用することでした。すべての OS 呼び出しを取り除き、組み込みデバイス用の Lua エンジンのパフォーマンスを改善しました。非常に素晴らしくシンプルで、約 5 分の作業で済みます。
バージョン 5.1以降、Luaでは、新しい状態を作成するときにカスタム アロケーターを設定できるようになりました。
私は、vxworks で「バイナリ バディ」システムを効果的に使用しました。基本的に、ブロックを半分にカットしてヒープを分割し、リクエストを保持する最小の 2 乗サイズのブロックを取得します。ブロックが解放されたら、ツリーを上ってパスを作成し、ブロックをマージして断片化を軽減できます。Google 検索で、必要な情報がすべて表示されるはずです。
私は、ヒープを最適化してメモリを再利用できるようにするための tinymem という C メモリ アロケータを作成しています。見てみな：
https://github.com/vitiral/tinymem
注: このプロジェクトは錆の実装に取り組むために中止されました:
https://github.com/vitiral/defrag-rs
また、umm_malloc については聞いたことがありませんでした。残念ながら、断片化を処理することはできないようですが、確かに便利そうです。私はそれをチェックアウトする必要があります。