マシン上で実行されているプロセスが、システムで利用可能な量を超えるメモリを割り当てようとすると、カーネルはメモリページをディスクとの間でスワップし始めます。これは、要求元のRAM割り当て要件を満たすために十分な物理メモリを確保するために行われます。
スワッピングの過剰な使用は スラッシング と呼ばれ、システム全体のパフォーマンスを低下させるため望ましくありません。主な理由は、ハードドライブが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分になることもありました。大規模プロジェクトでは数時間かかり、システムパフォーマンスに大きく影響する可能性があります。
まとめ
大量のデータを扱う場合、キャッシュを使うことはアプリケーションのパフォーマンスを高める強力な方法です。オープンソースプロジェクトがキャッシュをどう実装しているかを調べることは、自社アプリケーション用に設計する際に非常に役立ちます。