マシン上で実行されているプロセスが、システムで利用可能な量を超えるメモリを割り当てようとすると、カーネルはメモリページをディスクとの間でスワップし始めます。これは、要求元のメモリ割り当て要件を満たすために十分な物理メモリを確保するために行われます。
スワッピングの過剰な使用は スラッシング と呼ばれ、システム全体のパフォーマンスを低下させるため望ましくありません。主な理由は、ハードドライブがRAMよりはるかに遅いためです。
アプリケーションが大量のデータを処理する必要がある場合、スラッシングにさらされ、劇的に低速化する可能性があります。考えられる解決策は2つあります。アプリケーションを最適化してメモリをより効率的に使用するか、システムに物理RAMを追加するかです。
それでは、 Doxygen がメモリ使用量を最適化し、スラッシングを回避するために、どちらの解決策を採用しているのかを見てみましょう。
Doxygenは、注釈付きC++ソースからドキュメントを生成するための事実上の標準ツールですが、C、Objective-C、C#、PHP、Java、Pythonなど、ほかの多くの人気プログラミング言語もサポートしています。プロジェクトの開発と保守に多大な尽力をしてきた Dimitri van Heesch 氏に深く感謝します。
Doxygenはソースファイルを入力として受け取り、必要なデータを抽出するために解析し、その結果を DirDef、FileDef、NamespaceDef、ClassDef、MemberDef クラスのインスタンスに格納します。これらはすべて Definition クラスを継承しています。
これらのクラスのインスタンスは、その後ドキュメント生成に使用されます。最もメモリを消費するデータはメソッドと変数に関する情報で、MemberDef クラスによって表されます。処理対象プロジェクト内のメソッドと変数の数によっては、これらのインスタンスのサイズが1GBを超える可能性があります。
一部のプロジェクトでは、これらのインスタンスをすべてメモリに保持するとシステムパフォーマンスに影響し、ドキュメント生成に何時間もかかる可能性があります。
Doxygenはどのようにメモリを最適化しているのか？
Doxygenはキャッシュベースの解決策を使用しています。 キャッシュ を使うことは、メモリ使用量を最適化する一般的な方法です。その考え方は、メモリ内に保持する必要があるデータをキャッシュに保存することです。このキャッシュには多数のスロットがあり、各スロットが特定のデータを保持します。キャッシュがあるサイズを超えると、一部のスロットが解放されます。解放されたデータはディスクへ移動され、再び必要になったときにメモリへ読み戻されます。
Doxygenの場合、アルゴリズムは非常にシンプルです。
- 65,535個のスロットを持つキャッシュを定義する。
- MemberDef インスタンスを作成する必要がある場合、Doxygenは利用可能なキャッシュスロットがあるかを確認します。あればインスタンスはメモリ内に作成されます。なければディスク上のデータファイルに保存され、そのデータがデータファイル内のどこに保存されているかを記録するためにインデックスファイルが更新されます。
- Doxygenが MemberDef インスタンスへアクセスする必要がある場合、そのインスタンスがキャッシュ内にあるかを確認します。存在しない場合、Doxygenはインデックスファイルを使ってデータの保存場所を特定し、データファイル内のその位置へシークして、ディスクから読み込みます。
キャッシュのパフォーマンスは次の要素に依存します。
- コンテナ：キュー、配列、リスト、あるいはカスタムコンテナが考えられます。コンテナの選択はキャッシュのパフォーマンスに影響する可能性があります。
- キャッシュの最大サイズ。
- キャッシュからエントリを削除するために使われるアルゴリズム。キャッシュが最大サイズに達したら、どのエントリを解放するかを決める必要があります。たとえば、次の方法があります。
- 最初に読み込まれたスロットを解放する。
- 最後に読み込まれたスロットを解放する。
- 最も使用頻度の低いスロットを解放する。
1. コンテナ
Doxygenは ObjCache クラスを定義しています。これは CacheNode オブジェクトの連結リストであり、キャッシュへのインスタンスの追加と削除を担当します。
Doxygenがキャッシュをどう宣言しているかを次に示します。
Doxygen::symbolCache =new ObjCache(16+cacheSize);// 16 -> room for 65536 elements, 2. キャッシュサイズ
Doxygenはキャッシュの最大サイズを設定ファイルから取得します。
int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");このパラメータを設定可能にすることは有用です。物理メモリを多く搭載したマシンでは、キャッシュサイズを増やしてパフォーマンスを高められます。ただし、新しいDoxygenリリースでは、このパラメータは設定ファイルから削除され、既定値が使用されています。
3. キャッシュからエントリを解放するアルゴリズム
キャッシュが上限に達したときにキャッシュエントリを解放する、Doxygenソースコードのスニペットを次に示します。
コメントが非常に充実している
makeResidentメソッドのコードで指定されているように、キャッシュがいっぱいの場合、最も最近使われていないアイテムが削除されます。
このメソッドはほぼすべての
MemberDefメソッドから呼び出されます。
MemberDefの状態へアクセスする必要があるたびに呼び出されます。このメンバーが読み込まれているかを確認し、必要に応じて読み込み、最も最近使われていないメンバーをキャッシュから削除します。
キャッシュを使う利点
キャッシュを使うとアプリケーションのパフォーマンスを改善できますが、それは大きな利益をもたらすのでしょうか。それとも、追加される複雑さに見合わない単なるマイクロ最適化なのでしょうか。
私たちの製品でC/C++パーサーとしてClangを使うようになる前は、最初のバージョンでDoxygenをパーサーとして使っていました。キャッシュサイズについて多くのテストを実施しました。キャッシュを無効化し、この変更版でいくつかのC++プロジェクトを解析すると、解析時間が劇的に増加し、5分から25分になることもありました。大規模プロジェクトでは処理に数時間かかり、システムパフォーマンスに大きく影響する可能性があります。
まとめ
大量のデータを扱う場合、キャッシュを使うことでアプリケーションのパフォーマンスを大幅に改善できます。オープンソースプロジェクトがキャッシュをどう実装しているかを調べることは、自社アプリケーション用にキャッシュを設計する際に非常に役立ちます。