マシン上で実行されているプロセスが、システムで利用可能な量を超えるメモリを割り当てようとすると、カーネルはメモリページとディスクとの間でスワップを開始します。これは、要求元の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 の状態にアクセスして、そのメンバーが読み込まれているかどうかを確認するたびに呼び出されます。読み込まれていない場合、Doxygenはそれを読み込み、最も最近使用されていないメンバーをキャッシュから削除します。
キャッシュ使用の影響
キャッシュを使用するとアプリケーションのパフォーマンスを向上させられますが、キャッシュは本当に大きな最適化効果をもたらすのでしょうか。それとも、追加される複雑さに見合わないマイクロ最適化にすぎないのでしょうか？
当社製品でClangをC/C++パーサーとして採用する前は、最初のバージョンのパーサーとしてDoxygenを使用しており、キャッシュサイズについて多くのテストを実施しました。キャッシュを無効化し、この変更版でいくつかのC++プロジェクトを解析したところ、解析時間が大幅に増加し、5分から25分になることもありました。大規模プロジェクトでは数時間かかり、システムパフォーマンスに大きな影響を与えました。
結論
大量のデータを扱う場合、キャッシュの使用はアプリケーションのパフォーマンスを向上させる強力な方法になり得ます。独自のアプリケーションでキャッシュをどのように実装するかを検討する際には、オープンソースプロジェクトがキャッシュをどのように実装しているかを調べることが非常に役立ちます。