(57)【要約】【課題】ガベージコレクションのようなメモリ管理を強化してデータ局所性を増加するための方法とシステムとを提供すること。【解決手段】Ｃ＃のような現在のガベージコレクションをされた言語で書かれたアプリケーションは、大きい動的なワーキングセットと貧弱なデータ局所性を有する傾向があり、したがってメモリ階層間のデータ移動の管理に過剰の時間を消費すると思われる。その代わりに、オーバーヘッドの低い動的な技術は、アプリケーションのデータ局所性を改善する。この技術は、プログラムが動作している間にオブジェクトを監視し、最近アクセスされたオブジェクトをヒープ上の同一ページ（単数または複数の）に配置する。ページ密度の増加を提供することは、ＤＬＴＢおよび／またはデータキャッシュミスを減少するための効果的な方法である。【選択図】図１
2006092532.tif 000002
【特許請求の範囲】
【請求項１】
最近アクセスされたオブジェクトを判定するため、実行されているプログラムを監視するステップと、
少なくとも１つのビットを操作してオブジェクトアクセスを示すステップと、
プログラム挙動インジケータを監視するステップと、
プログラム挙動インジケータ監視に基づいて最適化を呼出すステップと、
最適化を実行することであって、
前記最適化の実行は、アクセスされたオブジェクトをメモリ内でクラスタ化するステップ、および
それぞれのアクセスされたオブジェクトに関して操作された少なくとも１つのビット
をリセットすることを備える最適化を実行するステップと
を備えたことを特徴とするコンピュータ化された方法。
【請求項２】
前記少なくとも１つのビットは複数ビットのカウンタであり、および前記操作は、複数ビットのカウンタをインクリメントすることを特徴とする請求項１に記載の方法。
【請求項３】
アクセスされ、クラスタ化されたオブジェクトは、ジェネレーショナルガベージコレクションされたヒープの新しい方の端に配置されることを特徴とする請求項１に記載の方法。
【請求項４】
仮想マシンにより行われることを特徴とする請求項１に記載の方法。
【請求項５】
前記少なくとも１つのビットは、アクセスされたオブジェクトのヘッダに配置されることを特徴とする請求項１に記載の方法。
【請求項６】
前記少なくとも１つのビットは、アクセスされたオブジェクトの外側に配置されることを特徴とする請求項１に記載の方法。
【請求項７】
アクセスされたオブジェクトは、第１のアクセスされたオブジェクトが第２のアクセスされたオブジェクトへのポインタを含むときは、第１および第２のオブジェクトがクラスタ内で一緒にグループ化されるような順序でアセンブルされることを特徴とする請求項１に記載の方法。
【請求項８】
前記アクセスされ、クラスタ化されたオブジェクトは、ヒープメモリの１つまたは複数のページを含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記アクセスされ、クラスタ化されたオブジェクトは、ヒープメモリの複数の隣接ページを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記クラスタ化されたオブジェクトは、ヒープの隣接しない領域に配置されるアクセスされるオブジェクトの別個の複数のクラスタを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
プログラム挙動インジケータは、パフォーマンスカウンタであることを特徴とする請求項１に記載の方法。
【請求項１２】
プログラム挙動インジケータは、Ｎ番目のメモリ圧力ガベージコレクションであることを特徴とする請求項１に記載の方法。
【請求項１３】
プログラム挙動インジケータは、割り当て率であることを特徴とする請求項１に記載の方法。
【請求項１４】
プログラム挙動インジケータは、オブジェクト参照カウンタであることを特徴とする請求項１に記載の方法。
【請求項１５】
プログラム挙動インジケータは、複数の挙動インジケータを組み合わせたものであることを特徴とする請求項１に記載の方法。
【請求項１６】
前記方法は、２つ以上のプログラム挙動インジケータを監視することを特徴とする請求項１に記載の方法。
【請求項１７】
監視されるプログラムを実行するメモリおよび中央処理装置と、
プログラムを実装してプログラム実行中のオブジェクトアクセスを記録するインストゥルメンテーションモジュールと、
プログラム挙動を監視するため、かつ監視されるプログラム挙動に対する最適化応答を呼び出すための最適化モジュールであって、前記最適化が、最近アクセスされ、記録されたオブジェクトをメモリ内でクラスタ化する最適化モジュールと
を有する監視されるプログラムを監視して最適化するための最適化モジュールと
を備えたことを特徴とするコンピュータシステム。
【請求項１８】
前記監視されるプログラム挙動は、ＤＴＬＢキャッシュのミス率であることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項１９】
前記監視されるプログラム挙動は、Ｌ２キャッシュのミス率であることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２０】
前記監視されるプログラム挙動は、割り当て率であることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２１】
前記最適化モジュールは、コピージェネレーショナルガベージコレクションモジュールの一部であることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２２】
前記インストゥルメンテーションモジュールは、ＪＩＴコンパイラを含むことを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２３】
記録されるオブジェクトアクセスは、アクセスされるオブジェクトに対応するビットを設定することからなることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２４】
前記最適化モジュールは、ヒープ上のオブジェクトをトラバースすること、およびオブジェクト内のビット設定を介して、どのオブジェクトが最近アクセスされたかを識別することをさらに備えたことを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２５】
最近アクセスされたオブジェクトは、最近アクセスされた別のオブジェクトを指し示し、その別のオブジェクトの近くに配置されることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２６】
前記最適化は、最近アクセスされ、記録され、クラスタ化されたオブジェクトは、単一ヒープページが保持するより多くのメモリを占有しているので、過剰の最近アクセスされたオブジェクトは、二番目のヒープページのクラスタに流れ込むことを判定することを含むことを特徴とする請求項１７に記載のコンピュータシステム。
【請求項２７】
前記実装されたプログラムは、オブジェクトアクセスを、ヒープアドレスに対応するビットベクトルに記録することを特徴とする請求項２６に記載のコンピュータシステム。
【請求項２８】
コンピュータ実行可能命令を有するコンピュータ読取可能媒体であって、
前記コンピュータ実行可能命令は、アプリケーションを実装して、オブジェクトアクセスを記録するための命令と、
アプリケーションの挙動を監視するための命令と、
アプリケーションの監視された挙動に基づいて、ヒープ最適化を呼出すための命令と、
最近アクセスされたオブジェクトをヒープ上で互いに近接してコピーするための命令とを有するヒープ最適化と
を備えたことを特徴とするコンピュータ読取可能媒体。
【請求項２９】
オブジェクトを実装して、ヒープ最適化の間にアクセスされた回数をカウントするための命令をさらに備えたことを特徴とする請求項２８に記載のコンピュータ読取可能媒体。
【請求項３０】
オブジェクトを実装して、オブジェクト内のデータフィールドがアクセスされたとき、そのヘッダ内にビットを設定するための命令をさらに備えたことを特徴とする請求項２８に記載のコンピュータ読取可能媒体。
【請求項３１】
システムは、アプリケーションの中間言語表現を採用して、それを特定のアーキテクチャのために機械コードにコンパイルする構成のジャストインタイムコンパイラであって、前記ジャストインタイムコンパイラが、実装されるコードを生成し、前記実装されたコードが、最近アクセスされたオブジェクトをマークするように構成されるジャストインタイムコンパイラと
前記システムは、アプリケーションを実行している間に、メトリックを収集するように構成される監視コードであって、前記監視コードが、マークされたオブジェクトを監視し、最近アクセスされた時にマークされたオブジェクトを、ヒープの残りの部分と別個のページに収集する局所性のためのガベージコレクションをトリガする構成である監視コードと
を備えたことを特徴とするアプリケーションのためのデータ局所性を改善するシステム。
【請求項３２】
局所性のための前記ガベージコレクションは、スペース再要求のためトリガされる普通のガベージコレクションとは無関係にトリガされることを特徴とする請求項３１に記載のシステム。
【請求項３３】
前記実装されるコードは、オブジェクトに埋込まれているオブジェクト参照カウンタを更新することにより、オブジェクトをマークする構成となっていることを特徴とする請求項３１に記載のシステム。
【請求項３４】
前記実装されるコードは、オブジェクトと離れたテーブルに格納されているオブジェクト参照カウンタを更新することにより、オブジェクトをマークする構成となっていることを特徴とする請求項３１に記載のシステム。
【請求項３５】
前記ジャストインタイムコンパイラは、ヒープデータにアクセスする重要な命令を有する方法内に、リードバリアのプロファイリングを生成することを特徴とする請求項３２に記載のシステム。
【請求項３６】
前記ジャストインタイムコンパイラは、２つのバージョンの方法を生成し、前記第１バージョンの方法と第２バージョンの方法が、別個のコードヒープに配置されることを特徴とする請求項３１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野は、一般的にメモリを管理してデータアクセスの効率を向上させることに関し、より詳細には、自動的に管理されるヒープの上でデータ局所性を改善するため、最近アクセスしたオブジェクトを監視して再配置することに関する。
【背景技術】
【０００２】
プロセッサ速度とメモリとの間の格差が増大しつつあることは周知である。多数のアプリケーションは、ガベージコレクションのようなメモリ管理技術を実行する環境の中で実行する言語で書かれている。これらの言語には、Ｃ＃およびＪａｖａ（登録商標）が含まれるが、これらには限らない。これらの言語で書かれるアプリケーションは、小さなデータ局所性を有する大型動的作業用メモリページ群を有する傾向がある。データ局所性が小さいと、アプリケーションの実行が不完全になり、プロセッサ速度の増加につれ、うまくスケーリングしないだろう。
【０００３】
【非特許文献１】Chilimbi他著「ジェネレーショナルガベージコレクションを用いるキャッシュ重視のデータ配置の実施(Using Generational Garbage Collection to Implement Cache Conscious Data Placement)」１９９８年（Chilimbi）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
さらに大型のマルチレベルキャッシュは、ある程度メモリ待ち時間を隠すのに役立つ。しかしながら、キャッシュメモリには高価であり、オンチップキャッシュ（例えば、Ｌ１キャッシュ、ＩＴＬＢキャッシュおよびＤＴＬＢキャッシュ）は、この費用のため、最新のアプリケーションの仕事量と同じ割合で成長するとは思われない。さらに、ハードウエアにおけるプリフェッチ技術は、メモリ待ち時間を減少することもできるが、シリアル依存性（例えば、ポインタ間接法）がプリフェッチアドレスの適時な出現を妨げるとき、変則的なデータアクセスのためのプリフェッチは困難である。
【０００５】
その結果、ソフトウエア技術を利用するアプリケーションのデータ局所性を改善することに関心が持たれている。静的および動的双方の技術が研究され最近の文献に報告されている。静的技術は、ＡＯＴ（ａｈｅａｄ−ｏｆ−ｔｉｍｅ）プログラム解析に依存し、典型的にはプロファイルデータを利用して参照の局所性に基づいてオブジェクトを同一の場所に配置するか、またはプリフェッチ命令をコンパイル時に挿入してメモリの待ち時間を隠す。この方法の主要な利点は、ランタイムのオーバーヘッドがないことである。しかしながら、静的な方法の通常の制限（例えば、ダイナミックにロードされるアセンブリおよびクラスの取扱の困難、ジャストインタイムコンパイラのためのプログラム全体の解析のコスト、およびプログラムのフェーズ変更取扱の困難）を受けてもよい。ガベージコレクション（ＧＣ）ベースのシステムの幾つかは、コピー機構を採用して、割り当てオブジェクトが最近アクセスされたか否かに係わらず実行時に再編した。しかしながら、ＧＣは、主にメモリの再利用（ｒｅｃｌａｉｍｉｎｇ）に使用されて来たので、良い空間的局所性は、空間の再利用を主目的とするヒープの圧縮または再編成の副作用として、受身で達成されて来た。
【０００６】
その他の、ＧＣに基づく方法もまた、インストゥルメンテーションを利用してプロファイル情報を実行時に収集するが、これら技術のプロファイリングコストは、非常に重い。
【課題を解決するための手段】
【０００７】
本明細書に記載する技術は、ガベージコレクションのようなメモリ管理を強化してデータ局所性を増加するための方法とシステムとを提供する。上述したような問題は、少なくとも部分的に、ここに開示するシステムと方法とにより対処する。一例において、オーバーヘッドの低い技術がヒープアクセス情報を収集し、次いでそれを利用してヒープの再編成を誘導し、ガベージコレクション（ＧＣ）に基づくシステムにおけるアプリケーションのためにより良いデータアクセス局所性を達成する。プロファイリングおよびヒープ再編成は、ページ密度の改善に重点をおいて、ページ欠陥とキャッシュミスの双方を低減するのに安価だが効率の良い実用的な実装を作成する。
【０００８】
一例では、ＧＣを主として且つ積極的に用いるが、それはメモリ局所性改善のためであって、以前のように単に受身でフリーメモリ空間を再利用する機構として用いるのではない。このような一例において、局所性のためのＧＣは、一定のプログラム挙動または性能の検出に際し、新たな割り当てのための空間がまだあり、したがってさもなければ空間のためのＧＣがトリガされないであろう時であっても、呼出され、またはトリガされる。このような一例において、局所性のためのＧＣをトリガすることにより、ガベージコレクションの回数を十分に（例えば、さもなければ解放されるメモリ空間を収集するために必要なコレクション回数を５０％超えて）増やすことができ、それでも局所性の改善のため全体ではスピードアップとなる。
【０００９】
一例において、この方法は、マイクロソフトの.ＮＥＴ Ｆｒａｍｅｗｏｒｋの共通言語ランタイム（ＣＬＲ）を用いて実装される。ＣＬＲは、ジャストインタイム（ＪＩＴ）コンパイラを用いて、ＭＳＩＬ（マイクロソフト中間言語）バイナリをネイティブコードに変換し、ジェネレーショナルガベージコレクタを採用してヒープを管理する。ガベージコレクションを経由してデータ局所性を改善するための方法の一例は、Ｃ＃を用いて書かれた幾つかの例示的アプリケーションにおいて評価される。しかしながら、本方法は、ＧＣに基づくシステムをコピーすることを目標にして任意の言語で書かれたアプリケーションに適用することができる。しかしながらガベージコレクションは、記載した技術に必須でない。
【００１０】
別の例における方法は、ヒープにおいてアクセスされるオブジェクトを監視する。このような一例においては、１つまたは複数のビットを設定（またはカウント）して、オブジェクトがアクセスされたことを表す。１つまたは複数のビットは、オブジェクト自体の中または近く、あるいはメモリの中の何処かにあってよい。別の例においては、アクセスの全てはカウントしない。その代わり、本方法は、サンプリング周期でアクセスされるオブジェクトを周期的に監視する。このような一例において、本方法はまた、ヒープの再編成をいつ行うべきかを判定するためにプログラム挙動をも監視する。監視されるプログラム挙動が指示するとき、本方法はヒープを再編成する。一例において、再編成は、最近アクセスされたオブジェクトをヒープの同一領域にクラスタ化する。別の例において、再編成は、サンプリング期間中に最近アクセスされたオブジェクトをヒープの同一領域にクラスタ化する。一例において、最近アクセスされたオブジェクトのクラスタは、ヒープの１つまたは複数のページに置かれる。別の例において、本方法は、オブジェクトがアクセスされたことを示すビットをクリアして、オブジェクトアクセスおよびプログラム挙動の監視に戻る。
【発明を実施するための最良の形態】
【００１１】
追加の特徴および利点は、添付図面を参照して進行する以下の詳細な記述から明らかになるであろう。
【００１２】
（データ局所性最適化の例示的な方法）
図１は、ヒープのデータ局所性を最適化するための例示的方法に関するフローチャートである。図示すように、方法１００は、アクセスされるオブジェクトを監視し、最適化メトリックを監視し、およびアクセスされたオブジェクトを（単数または複数の）ヒープページにおいて再編成する。
【００１３】
ステップ１０２において、本方法はヒープ上のアクセスされたオブジェクトを監視する。例えば、ＪＩＴコンパイラは、ヒープの中のデータオブジェクトを読取り、または書込む操作を実装する。アクセスされたオブジェクトを示すレコードが保持される。一例において、レコードは、オブジェクト自体の中にあるビットであって、そのオブジェクトが最近アクセスされたことを示すように設定する。別の例においては、レコードは別個のビットベクトル内にあるビットである。さらに別の例においては、プロセッサが機構または命令を備え、それが最近アクセスされたオブジェクト全てのアドレスを記録する（例えば、現在キャッシュにあるアドレス全てを記録する）か、またはページフォールトをもたらしたアドレスを記録する。
【００１４】
一方では、ステップ１０４において、本方法は、データ局所性のための最適化を行う時期を判定するため、メトリックを監視する。例えば、パフォーマンスメトリックを、オブジェクト割り当て率、ＤＴＬＢミス率、キャッシュミス率、パフォーマンスカウンタ、オブジェクト参照カウンタ、またはタイマとすることができる。監視されたメトリックが、局所性のためヒープを再編成する時期であることを示すとき、本方法はステップ１０６を実行する。
【００１５】
ステップ１０６において、この方法は先ず、最近アクセスされたオブジェクトを識別し、次いでそれらをヒープの中の隣接するページに集積する。例えば、実装したコードが、アクセスされたオブジェクトの中またはアクセスされたオブジェクトのビットテーブル内に、ビットを設定する。例えば、実装されたコードが、アクセスされたオブジェクトまたはアクセスされたオブジェクトのビットテーブル内に（単数または複数の）ビットを設定すると、これらのオブジェクトは、ヒープにおいて一緒にクラスタ化される。別の例においては、プロセッサの提供する操作が、ヒープの上のアクセスされたオブジェクトアドレスを通告する。別の例において、プロセッサの提供する操作は、ＤＴＬＢミスをもたらしたアドレス要求を指し示す。一例において、アクセスされたオブジェクトに対応するアクセスビットまたはカウンタは、そのときリセットされる。別の例においては、アクセスビットまたはカウンタは、直ちにリセットされないで、時間を掛けてゆっくりとリセットされる。
【００１６】
ステップ１０８において、本方法は、データ局所性のためにヒープが最適化されると、ステップ１０２およびステップ１０４に戻る。
【００１７】
（データ局所性最適化の例示的なシステム）
図２に、ヒープのデータ局所性を最適化するための例示的なシステムのブロック図を示す。
【００１８】
コンピュータシステム２００は、１つまたは複数のプロセッサ２０２、オンチップキャッシュ２０４、データ局所性のために監視され、および最適化される（単数または複数の）動作プログラム２０８、データ局所性改善のためのプログラムを監視するためのモジュール２０６、動作プログラム２０８のための作業用データページ（例えば、ページ、セグメントなど）のヒープ２１６を備えたランダムアクセスメモリ（ＲＡＭ）２１０、オフチップキャッシュ２１２、ディスクドライブまたはその他のバイナリ記憶装置２１４、およびネットワーク接続２１８を含む。プロセッサは、命令、データ、および／または状態を含むプログラム２０８、２０６、２２０を実行する。監視されるプログラム２０８の実行する際、プログラムのデータページがストレージ２１４、およびまたはネットワーク２１８から必要に応じてヒープ２１６に呼び戻される。
【００１９】
一例において、監視されるプログラム２０８は、中間言語（ＩＬ）コードであって、これは、実行の前にさらにネイティブコードにコンパイルされる。このような場合に、コンパイラ２０６は、プログラムをコンパイルし、且つ実装する。別の例においては、プログラムが既にネイティブなバイナリ形式になっているので、インストゥルメンテーション２０６はネイティブバイナリコードにおいて実行される。別の例において、インストゥルメンテーション２０６は、実行中にアクセスされたオブジェクトまたはアドレスを識別するために、プロセッサによりサポートされる命令を追加する。
【００２０】
プログラム２０８は、プログラム２０８の実行中にアクセスされたオブジェクトをヒープ２１６内に記録することができるように実装される。プログラムはまた、メトリックを監視して最適化モジュール２２０をトリガすることができるようにも実装される。最適化をトリガするためには、ＴＬＢ、ＤＴＬＢまたはキャッシュミスのような、各種のメトリックを使用してもよい。最適化をトリガするための別の可能なメトリックは、以下に論じる別のものと並んで、メモリ割り当て率、オブジェクト参照カウンタである。実装されたプログラムが実行され、最適化がトリガされると、最適化モジュール２２０が、ヒープ２１６の少なくとも１つのメモリページ（またはセグメント）を再編成する。例えば、最適化は、アクセスされたオブジェクト（例えば、ホットオブジェクト）全てをヒープ上の単一ページ（またはページ群）に配置する。ヒープにおけるホットオブジェクトのこのページ（またはページ群）は、ホットページと呼ばれる。
【００２１】
このように、本システムはプログラムを実装して、実行中にアクセスされたオブジェクトを監視（プログラム監視）し、ヒープ２２０最適化をトリガする性能インジケータに関するプログラムを監視（性能監視）し、および増加したデータ局所性によりプログラム性能を向上させるため、アクセスされたオブジェクトをメモリの中で（例えば、ヒープの上で互いに近いオブジェクトを、単一ページ、隣接する（単数または複数の）ページなどにおいて１つまたは複数にグループ化する）クラスタに再編成する（データ局所性最適化）。加えて、データが局所性に関して最適化されると、システムは最適化されたプログラムの監視を開始する。したがって、システムは動的でかつ進行中である。
【００２２】
（例示的メモリ構成）
図３に、変動するアクセス速度を有する複数レベルを経由するメモリ管理のための例示的なシステムのブロック図を示す。
【００２３】
最新のコンピュータ３００は、中央処理装置３０２（ＣＰＵ）を含み、これはプロセッサ３０４および各種レベルのメモリを含む。この各種レベルのメモリは、オンチップキャッシュ３０６、３０８、３１０、オフチップキャッシュ３１２、３１４、ランダムアクセスメモリ（ＲＡＭ）３１６、ディスクストレージ３１８および多数のその他のメモリの形式を含むが、これには限定されない。コンピュータは、予め実行可能なファイルに処理されているプログラムを実行する。プロセッサは命令をメモリから取出し、その命令を復号化し、復号化した命令を実行して各種の機能を実行する。性能と速度を改善するには、コンピュータは、各種レベルのメモリを利用して、次の命令またはデータを必要に応じて入手することができる尤度を増加させる。例えば、データまたは命令（すなはち、リソース）が必要になる度毎にＲＡＭの中を見る代わりに、プロセッサは点検してリソースがキャッシュの中にあるか否かを調べる。必要なリソースをキャッシュから獲得することは、それをＲＡＭまたはディスクから獲得するより迅速である。なぜなら、より少ないクロックサイクルで達成することができるからである。コンピュータはしばしば命令用とデータ用に別個のキャッシュを設ける設計となっている。記述する方法とシステムは、リソース取出に必要な時間を減少させることによりコンピューティング性能を改善する。
【００２４】
ＣＰＵ性能は、メモリ性能より遙かに速く向上している。これにより、プロセッサ速度が高速化した程には、プログラムが高速に動作しない状態が生じた。１つの解決策は、チップにより近く、より大きなキャッシュメモリを構築することであったが、この解決策は、キャッシュメモリが高価になるので困難である。そこで、処理の相対速度は、命令の復号化および実行の速度よりも、メモリの速度により判定されて来た。このことは、プロセッサはメモリからデータまたは命令が到着するのを待っているため、例えば、Ｐｅｎｔｉａｍ（登録商標）ＩＶは３倍乃至４倍速いが、アプリケーションは３倍の速さでは動作しないことから明らかである。時間は、ＴＬＢ（ｔｒａｎｓｌａｔｉｏｎ  ｌｏｏｋ−ａｓｉｄｅ  ｂｕｆｆｅｒ）３０６、３０８がおこなう仮想アドレスをメモリの中の物理アドレスに変換することに消費される。メモリシステムは、命令用のＴＬＢ（ＩＴＬＢ）３０６、およびデータ用のＴＬＢ（ＤＴＬＢ）３０８を有する。プログラムは、ＲＡＭの中の有効な空間より大きな仮想アドレス空間を持つことができるので、プログラム実行状態の一部（例えば、コード／データページ）は、必要に応じてＲＡＭ３１６とストレージ３１８との間で伝送される。
【００２５】
ＴＬＢは、仮想アドレス空間の中で現在利用できるものを、それが物理メモリの中で位置するところに変換するのに使用される。ＴＬＢキャッシュは、高価なハードウエアなので、設計者はそのサイズを小さく保つことを好む。ＴＬＢは、より大きなプログラム状態のどの部分がメモリ３１６内にあるかのマップである。プログラム実行が、ＴＬＢキャッシュによって判定されるようにＲＡＭ３１６内に無いアドレスを要求するときは、ページフォールトに遭遇する。そのアドレスを含むページがメモリ内に存在するときは、そのページフォールトをソフトページフォールトと呼び、そのアドレスに関するＴＬＢエントリを更新するには数百サイクルを要する。そのアドレスを含むページがメモリ内に存在しないときは、それをストレージからメモリに運び込まなければならない。この場合、このページフォールトをハードページフォールトと呼び、そのページをディスクから運び込むには、何百万もの命令を要する。プロセッサが、ＴＬＢとキャッシュ３１０、３１２、３１４双方において既に利用可能なアドレスを要求するときは、変換は極めて速い。したがって、メモリ管理は、数ある中でもとりわけ、利用可能なページ（ブロック、セグメントなど）の管理、およびプロセッサが、必要なリソースを最も少ないクロックサイクル数で利用できる尤度を増加させる方法を含む。
【００２６】
単に時間の違いの相対的な比較のため、各種キャッシュとメモリの速度の例を見ると興味深い。プロセッサの要求するリソースをレベル１キャッシュ（Ｌ１）で利用可能なとき、リソースを１−３クロックサイクルで獲得することができる。プロセッサの要求するリソースをＬ２キャッシュで利用可能なとき、リソースを１０−５０クロックサイクルで獲得することができる。Ｌ３キャッシュの中のリソースは、２０−１００クロックサイクルで獲得することができ、メモリの中のリソースは、約５００クロックサイクルで獲得することができ、ストレージの中のリソースは獲得するのに著しく長く掛かる。リソースは、必要に応じてページ（例えば、４Ｋバイト）内のストレージからメモリ内に運び込まれ、ブロックのような小さいサイズは必要に応じてキャッシュ内に運び込まれる（例えば、６４−１２８バイト）。ここでも、これらの例は、現在および将来、実質的および相対的な相違が変動するものであるとして議論を規制または制限するものではなく、これらは単に、議論に文脈を与えることを目的とするのみである。
【００２７】
このように、このシステムはプログラムを実装して、実行の間にアクセスされたオブジェクトを監視（プログラム監視）し、ヒープ３２０最適化をトリガする性能インジケータに関してプログラムを監視（性能監視）し、および改善されたデータ局所性によりプログラム性能を向上させるため、アクセスされたオブジェクトをメモリの中で（単数または複数の）ページ３２２上に再編成する（データ局所性最適化）。加えて、データが局所性に関して最適化されると、システムは最適化されたプログラムの監視を開始する。したがって、システムは動的でかつ進行中である。
【００２８】
（例示的コンパイル）
図４は、実行可能コード作成に関する例示的な方法４００の図である。一例において、ソースコード４０２がコンパイラ４０４でコンパイルされ、実行可能な形式４０６（例えば、Ｘ８６）に分散され、必要に応じてメモリに運び込まれる。例えば、あるコードバイナリは、任意の互換性のある環境において動作することができる。このような一例において、互換性バイナリコードは、任意のＸ８６環境において実行することできるＰＥ（ｐｏｒｔａｂｌｅ  ｅｘｅｃｕｔａｂｌｅ）ファイルである。このモデルは、ＣおよびＣ＋＋のような高級プログラム言語で書かれたプログラムに見られる。
【００２９】
別の例において、ソースコード４０２は、中間レベルコード４０８（例えば、ＭＳＩＬ、Ｊａｖａ（登録商標）など）にコンパイラ４０４でコンパイルされ、それをさらに、それを実行するプロセッサ（例えば、x８６、ｘ６４など）のためＮＥ（ｎａｔｉｖｅ  ｅｘｅｃｕｔａｂｌｅ）ファイル４１２にコンパイラ４１０でコンパイルすることができる。このような一例においては、ジャストインタイム（ＪＩＴ）コンパイラが、実行のため必要なとき（例えば、ストレージ、ネットワークなどからメモリに運び込まれたとき）、中間コードをネイティブコードに変換する。
【００３０】
ガベージコレクションを含むメモリ管理は、図４で検討するものを含む多くのコンピューティング環境において採用されており、単一コンピューティング環境は、任意のこれらコンパイル方法を採用することができる。例えば、既存のバイナリが実装されて４１４実行中にどのオブジェクトがアクセスされたかを記録することができ、同様にＪＩＴのコンパイルの間に実装する４１６こともできる。面白いことに、ここに記述する局所性最適化は、ＪＩＴコンパイルにおいて特に有用である傾向がある。なぜなら、しばしばこれらの言語は、プログラムが参照しなくなったオブジェクトをクリーンアップするのに、メモリ管理に一層大きく依存するからである（例えば、到達可能性解析、参照カウンタなど）。
【００３１】
高級言語には、そのプログラムが必要とすると思われるメモリを、プログラマが割り当てることおよび割り当て解除を必要とするものがある。別の言語またはランタイムでは、プログラマは、ガベージコレクションに依存して割り当て解除をおこなうことができる。ガベージコレクションは、未だ使用中のオブジェクトをヒープにおいて識別すること、および参照されなくなったあらゆるオブジェクトを廃棄することを含む。
【００３２】
従来、ガベージコレクタは、新規の割り当て要求にかなう十分な空間が無いとき呼出され、参照されなくなったと判定されたオブジェクトが占有する空間を解放して新しいオブジェクトが利用することができるようにした。このように、ＧＣは主として、必要に応じてメモリを再利用するための方法と考えられていた。例えば、プログラムが、現在利用可能であるメモリより多くのメモリを必要とするとき、ヒープをトラバースして、ヒープ上で到達可能なメモリを見出す。到達可能メモリはページ上にパックされ、解放された空間は、プロセッサの要求するリソースとして利用することができるようにされた。このように、ＧＣは、新規割り当て要求が満足されないときにのみトリガされた。
【００３３】
現在の技術において、ＧＣは、データの局所性を改善し、それにより性能を改善する方法と考えられている。このような一例において、ＧＣは、主として性能にかんする局所性の改善を行い、副次的に必要に応じてメモリの解放を行うと考えられている。ＧＣは、ホットオブジェクトを追跡することおよびアクセスされたオブジェクトをいっしょに配置することのオーバーヘッドにも拘わらず、多くの場合、結果として性能改善となる。一例において、ＧＣが、単に空間を再利用するためにのみ行われていた場合より、５０％以上多く、実行に時間がかかるにもかかわらず、ネット性能は依然として良かった。ホットオブジェクトが（単数または複数の）ページ上にパックされるので、キャッシュに移動されるパックされたホットページの部分もプロセッサが必要とする可能性が増加する。したがって、オブジェクトをページまたはページ群にパックすることは、ヒープにおいてだけでなく、そのページの一部が配置されるキャッシュにおいても空間的局所性を増加させる。ページをホットオブジェクトでパックすることの副次効果は、キャッシュの利用度の増加である。
【００３４】
興味深いことに、アクセスされたオブジェクトそれぞれに対する１ビットの設定は、アクセスされたオブジェクトの追跡に十分である。しかしながら、オブジェクト毎に数個のビットを使用してタッチをカウントすることにより、どのオブジェクトが最も頻繁にタッチされるかを知ることができる。これにより、オブジェクトが（複数または単数の）ページ上でパックされる場所についてより詳しく知ることができる。
【００３５】
（例示的な局所性）
アプリケーションが、メモリにアクセスする際に時間的局所性を示す、即ち、最近アクセスされたオブジェクトは、近い将来、再度アクセスされるであろうことは公知である。更に、アプリケーションが、最近アクセスしたオブジェクトに近いオブジェクトにアクセスするときは、良好な空間的局所性を有すると言われる。空間的局所性が小さいと、オブジェクトアクセスがメモリ全体に広がる結果、ＴＬＢ／キャッシュおよびＲＡＭの利用度が低くなり、実行性能を低下させる。どのオブジェクトがごく最近にタッチされたかを監視し、最適化方法を呼出してこれらホットオブジェクトを一緒に配置することにより、空間的局所性が、後の実行段階で改善されると考えられる。ホットオブジェクト群が、プログラムが稼動している間に変化することを考慮すると、監視を継続して連続的または周期的に最適化することが重要である。
【００３６】
ガベージコレクション中に、またはガベージコレクションからこのメモリ最適化技術を呼出す必要は無い。一実施形態では、局所性最適化コレクションはガベージコレクションとは別個に作動する。このような一例において、メモリ圧力は既存ガベージコレクションにメモリ解放をさせるが、局所性最適化はここに記載するように必要な時は何時でも呼出される。
【００３７】
別の例では、ガベージコレクションの付加的最適化として局所性最適化方法が提供される。これは、ヒープを管理している既存の方法およびデータ構造体を使用して局所性最適化を支援することが出来るので好都合である。例えば、ガベージコレクションの間にライブオブジェクトが識別される一方で、ライブでホットなオブジェクトも同様に認識されて（単数または複数の）ホットページにパックされる。
【００３８】
図５に、メモリ内のページ全体に広がる例示オブジェクトを示す。この例において、各グリッド５０２はヒープ５００上のページを意味し、グリッドの中のオブジェクトはライブオブジェクト５０４または廃棄された（例えば、解放されるかまたはもはや参照されない）オブジェクト５０６を意味する。ヒープは、典型的にＲＡＭの一部分を占有する。任意の所定の時点で、ヒープの部分は、利用可能なキャッシュの大きさに基づいて、より速いキャッシュメモリ内で利用することが出来る。ＴＬＢは、仮想アドレス空間を物理アドレスにマップして、仮想アドレス空間のどの部分を、迅速にＲＡＭの中の物理空間に変換することが出来るかを示す。
【００３９】
時間が経過すると、アクティブなオブジェクトはヒープ全体に広がり、さらに悪いことに、ライブオブジェクトの間にデッドオブジェクトが入って、メモリはさらに寸断される。これは小さいデータ局所性を生じる。この小さいデータ局所性の副次効果の１つとして、プロセッサの必要に応じてメモリブロックをキャッシュの内外に移動させること、およびＤＴＬＢエントリに存在しないアドレスがアクセスされたときＤＴＬＢを更新することに要する時間が長くなる。
【００４０】
最終的には、ヒープがオブジェクトで満たされ、一層のオブジェクト割り当てが要求されるとき、メモリ圧力に基づいてガベージコレクションがトリガされる。
【００４１】
一例において、この小さいデータ局所性を克服するため、アクセスされるオブジェクトそれぞれに１ビットが設定される（５０８）。局所性最適化がトリガされると、設定されたビットを有するこれらのオブジェクトは、メモリ内の隣接ページの単一セット上に集められる。別の例においては、オブジェクトの外のホットビットテーブルが、どのオブジェクトがアクセスされたかを示す。どちらの場合も、このホットビットデータは、どのオブジェクトをホットページ上に配置するべきかを示す。
【００４２】
（ガベージコレクションにより支援される例示的な局所性最適化）
図６は、例示的なジェネレーショナルガベージコレクション方法およびシステムの図である。ヒープ６００は、論理的にジェネレーション（例えば、Ｇ０、Ｇ１、およびＧ２）に分割されている。ジェネレーションは、論理的にヒープの一部として考えられ、ヒープの分割には三つのジェネレーションを使用することが多い。例えば、フリースペースと並んでごく最近に割り当ててられたオブジェクトの最も新しいジェネレーション６０２、オブジェクトの古いジェネレーション６０４、および最も古いジェネレーション６０６がある。典型的に、これらのオブジェクトは、最初の割り当てからの時間の観点から考えられ、最も新しいオブジェクトおよび利用可能なフリースペースは、論理的に第１ジェネレーション６０２にあると考えられる。ヒープの論理ビューは、フリースペースの始まる場所の指示と共にジェネレーションバウンダリを示すデータ構造体６０８に格納されている。
【００４３】
新規割り当てのためにフリースペースが減少するにつれ、メモリ圧力（例えば、実際のまたは予期される、メモリ空間需要の増大）に基づいてガベージコレクションがトリガされる。例えば、オブジェクト割り当てが要求され、利用可能なメモリが小さ過ぎる、または、利用可能なメモリが、好ましい若しくは望ましい閾値以下に落ちているときである。
【００４４】
メモリ圧力によるガベージコレクションの間にライブオブジェクトが識別され、ヒープからガベージ（例えば、もはや到達不能のオブジェクト、もはや参照されないオブジェクトなど）が集められて削除され、解放されたメモリが論理的に最も新しいジェネレーションに移って、ジェネレーションのサイズが調節される。
【００４５】
例えば、第１ジェネレーション６０２は、数回ガベージコレクションを行われる場合がある。新しいジェネレーションのメモリ収集がもはや空きメモリの望ましい閾値を生まなくなったとき、古いジェネレーション６０４のガベージコレクションを行うことが出来る。例えば、トリガされた第１ジェネレーションのガベージコレクションが十分な空きメモリを生まなくなったとき、それが第２ジェネレーションのガベージコレクションをトリガする。第三ジェネレーションのガベージコレクションの前に、第２ジェネレーションのガベージコレクションが数回生成する場合がある。第１および第２ジェネレーションのガベージコレクションが十分な空きメモリを収集しなくなると、第３ジェネレーションのガベージコレクションがトリガされる。時間が経つにつれ、デッドオブジェクトが削除されてライブオブジェクトが圧縮される。
【００４６】
ガベージコレクションには、デッドオブジェクトがフリーリストに入れられる「マーク＆スイープ」、およびライブオブジェクトがヒープにまとめて圧縮される「マーク＆コンパクト」のような、各種の方法がある。当業者がこの明細書を読むと、これらガベージコレクション方法のいずれをも採用しまたは充実させて（その方法を変形したもの、組み合せたもの、および改良したものを含む）、ここに記載する局所性最適化をサポートすることが出来る。
【００４７】
これら既存のガベージコレクション技術（例えば、ジェネレーショナルガベージコレクション）の副次的効果の１つは、データ局所性を幾分か改善することである。例えば、データオブジェクトを単にヒープから削除することにより（どのジェネレーションから削除するかに関わりなく）、ページの空間的局所性が良くなる尤度が増す。例証目的でのみ、ジェネレーショナルコピーガベージコレクションについての検討をすすめる。
【００４８】
ジェネレーショナルコピーガベージコレクションのネット効果は、オブジェクトがヒープ上にほぼ割り当ての順序で、更に論理分割を伴ってジェネレーションでグループ分けされ、時間を追って各種方法を使って調節できることである。デッドオブジェクトは削除され、それに続くライブオブジェクトが前に移動する。こうして、割り当ての順序が維持される。これは、割り当ての順序は最良の局所性を提供するという理論に基づいているが、その理論は必ずしも真ではない。
【００４９】
例えば、Chilimbi他著の非特許文献１は、プログラム効率を向上させるため、キャッシュの扱いが容易な方法でデータを配置することに焦点を合わせている。例えば、Chilimbiは、オブジェクト配列順序を監視して、オブジェクトをアセンブルする順序を判定した。この考えでは、オブジェクトがアクセスされた順序を監視し、その順序に従って並べ直す必要があった。実行時に、この情報を全て取得し、分析するオーバーヘッドは、法外な費用となることがあった。
【００５０】
代わりに、記載する最適化は、最適化と最適化との間すなわち１間隔に、タッチされたオブジェクトを監視し、最適化がトリガされる時これらのオブジェクトを、ヒープの上の（単数または複数の）ホットページにパックする。興味深いことに、キャッシュ利用改善のため直接プロファイリングデータ収集を行わないにもかかわらず、ここに記載する方法でヒープの同一の（単数または複数の）ページ上にホットオブジェクトを配置すると、副次効果としてキャッシュがより適切に利用される。
【００５１】
したがって、コピージェネレーショナルガベージコレクタは、ここに記載する最適化に適合する興味のある環境であった。このガベージコレクタはオブジェクトをトラバースしてライブオブジェクトを全て識別し、その割り当て順序に基づいて識別したオブジェクトを圧縮する。圧縮されたオブジェクトを利用してホットオブジェクトを識別し、そのホットオブジェクトを任意の順序でパックすることができる。したがって、これらの最適化は、ジェネレーショナルガベージコレクションの制限を受けず、容易にサポートされる。
【００５２】
（例示的な低オーバーヘッドプロファイリング）
一例においては、ＪＩＴコンパイラを変更してヒープにアクセスする機能を実装する。実装されたコードは、ヒープの上のオブジェクトがタッチされた時期を監視する。一例においては、各オブジェクト内にメモリ領域を導入して（例えば、追加して）そのオブジェクトへのタッチの有無を示す。別の例においては、それぞれのオブジェクトの中のメモリの既知の未使用領域（例えば、単数または複数のビット）にマークして、そのオブジェクトがタッチされたことを示す。例えば、オブジェクトヘッダには利用可能なスペースがあり、これを様々な目的に使用することが出来る。ビットが設定されるか、または複数のビットを使用するときはタッチがカウントされると、最適化と最適化の間すなわち１間隔にタッチされたオブジェクトは（単数または複数の）ホットページにパックされる。この方法は、オーバーヘッドが低いことが多い。さらに、タッチされたオブジェクトが（単数または複数の）ページにパックされるときに、タッチされた（単数または複数の）ビット（またはビットカウンタ）はクリアされ、次のホットオブジェクト収集のためにタッチの有無を記録する（すなわち再びゼロからタッチをカウントする）状態になる。しかしながら、ホットオブジェクト表示ビットをヘッダ内に配置する必要はない。この（単数または複数の）ビットは、オブジェクトの中の任意の場所または別の場所に配置することが出来る。ここには、順序情報を記録する必要が無いことに注意されたい。
【００５３】
例えば、ホットオブジェクトビットテーブルは、各オブジェクトを１ビットで示す。これは多くのメモリを必要とするが、ホットオブジェクトを識別した後、ビットを容易にクリアすることが出来るので、この方が望ましい場合が多い。
【００５４】
別の例においては、ヒープの小型版であるビットベクトルが作成される。このような一例においては、ビットベクトルの中のビットは、ヒープの中のアドレスすなわち領域に対応し、ベクトル内に１ビットが設定されて、ヒープのアドレスすなわち領域の１つがアクセスされたことを示す。このビットベクトルは、例えば、ホットページ最適化と最適化の間、またはメモリ圧力のためのガベージコレクションが実行されるとき、容易にリセットすることが出来る。
【００５５】
時間の経過と共にプログラムが進歩するにつれ、ホットオブジェクトは発展し、ホットオブジェクトの発展に伴ってホットページも発展する。ここに記述するオーバーヘッドの低いプロファイリングにより、（単数または複数の）ホットページを動的に変更してプログラム性能を向上させることが出来る。
【００５６】
（例示的なパックされたオブジェクトページ）
後に説明するように、１つまたは複数のメトリックが、単独または組合せで使用されて、局所性最適化をトリガする時期を決定する（例えば、割り当て率、パフォーマンスメトリックなど）。データ局所性のための最適化がトリガされると、ホットであることを示す（単数または複数の）対応ビットを有するライブオブジェクトが、識別されて、（単数または複数の）ホットページ上に配置される。別の例においては、ホットオブジェクトに関する複数のページがある。一実施例において、ホットオブジェクト全部を先ずヒープの外にコピーして一時バッファにアセンブルし、スペースのための従来のガベージコレクションを通常通り進行させて、次いでホットオブジェクト全部の集合をヒープの新しい端に配置する。ここで、新規に割り当ててられたオブジェクトが、これらホットライブオブジェクトの近くに配置される。この実装は、低オーバーヘッドで、データ局所性を大きく増加させる。
【００５７】
（パックされたオブジェクトページの例示的な最適化）
別の例においては、局所性のためのＧＣの間にホットオブジェクトに遭遇するとき（例えば、設定ビットにより示されるとき）、そのホットオブジェクトを評価してそれらが指す別のホットオブジェクトを調べる。このような一例においては、ホットオブジェクトが別のホットオブジェクトをポイントしているとき、両方のホットオブジェクトが（単数または複数の）ホットページ上に配置されるだけでなく、それらは互いに近接して配置される。これは、ホットページの一部がキャッシュに移動されるとき、キャッシュに移動されたオブジェクトが次々に参照されると思われる尤度が増加する、オーバーヘッドの低い方法を提供する。これは効率的であることが多い。
【００５８】
（小さいデータ局所性を有する例示的プログラム）
下記のＡ表は、ｃ＃で書かれた４つのテストアプリケーションのページ密度を示す。これらの数値は、動的トランスレータを用いてこれらのアプリケーションを動作させ、メモリ読取および書込をロギングすることにより得られた結果である。この数値は、スタックページに対する参照を含まない。密度のメトリックは、ページ上で読取り、または書込まれた固有バイトの数をページのサイズで割ったものに等しい。この例において、１間隔は１０６回参照に設定した。下記のＡ表は、データページが極めて非能率に使用されていることを示し、これは通常、空間局所性の低さを意味する。
【００５９】
【表１】
2006092532.tif 000003
【００６０】
（例示的なシステム）
一例においては、ジェネレーショナルガベージコレクタをコピーすることを最適化して、データ局所性を増加する。例えば、方法として、ガベージコレクションを含むメモリ管理を備えた仮想マシンを使用してもよい。この例において、このシステムは、仮想マシンに関するその他の詳細のほとんどに関して寛容である。
【００６１】
図７は、このシステムの１つの可能な実施例のアーキテクチャの概観７００を示す。ジャストインタイム（ＪＩＴ）コンパイラ７０２は、中間言語表現７０４（例えば、ＭＳＩＬ）を採用して、それを特定のアーキテクチャのために機械コード７０６にコンパイルする構成となっている。ＪＩＴコンパイラは、コンパイルされるコード内に軽量なインストゥルメンテーションを挿入するように、変更することが出来る。実装されたコード７０８は、最近アクセスされたオブジェクトをマークする。監視コードは、アプリケーションが動作している間にメトリックを収集するように、ランタイム（例えば、共通言語ランタイム（ＣＬＲ）またはＪａｖａ（登録商標）ランタイム）に挿入することが出来る。監視コードは、局所性のためのＧＣをトリガするため、監視データおよびヒューリスティックを使用することが出来る。局所性のためのＧＣの間、最近アクセスされた（ホット）およびマークされたオブジェクトを識別し、ヒープの残りの部分とは離れたページにおいて同一の場所に配置する。局所性のためのＧＣは、メモリ圧力の検出に際してトリガされる通常のＧＣと無関係にトリガすることが出来る。
【００６２】
（例示的なページの最適化とキャッシュ最適化の対比）
データを局所性のために配列するとき、ページ局所性のために最適化するかまたはキャッシュ局所性のため最適化するかの２つの選択肢がある。
【００６３】
一例においては、データページに関するページ密度を増加することが有利である。例えば、ページ最適化のためプロファイル情報を集めることは、安価である場合もある。ページ（典型的に４ＫＢ）は、キャッシュライン（典型的に６４−１２８バイト）より、桁違いにもっと大きいので、効率の良いパッキングをおこなうため、データアクセスの明確な時間的順序を入手する必要はない。「ビン」のサイズが大きいので、データをより大まかにパックすることができる。単にページ密度を増加することにより、（コールド介在オブジェクトの削除により）キャッシュ利用度を良くするために、同様にデータをパックする機会が増加することに留意されたい。これは、事実上ページ最適化の副次的な悪影響がない時に、多数のプログラムの重要なキャッシュの利点につながる。
【００６４】
さらに、ページフォールトおよびＴＬＢミスのコストは、通常Ｌ２キャッシュミスより遙かに高価である。そこで、ページ最適化の潜在的な節約は、キャッシュ最適化の場合より大きいこともある。勿論、これは一挙両得で、つまりコールドページ上の単一のホットオブジェクトは、そのページをフォールトさせて、最適化のほとんどの利益を帳消しにする場合がある。したがって、ホットデータ群の良い適用範囲があることを保証するのに有用である場合がある。
【００６５】
場合によっては、Ｌ２キャッシュは仮想アドレスではなく物理メモリアドレス上で典型的にインデックスが付与される（例えば、ｘ８６アーキテクチャ全てにおいて当てはまる）。そこで、ＴＬＢにおいてページエントリが欠落しているときは、Ｌ２キャッシュ内にデータを有することは、あまり役に立たない場合がある。
【００６６】
（例示的なインストゥルメンテーションモデル）
キャッシュ利用度ではなくページ密度を改善するには、データ要素間の厳密な時間的アフィニティを判定する必要はない。その代わり、実施例によっては、トリガされる動的な最適化の間、または時間間隔の間に、頻繁にアクセスされるオブジェクトを単に記録するだけで十分である。アクセスされたこれらのオブジェクト（例えば、オブジェクト、方法、手順、データ構造など）は、このときホットと見なされる。最適化の間に、ホットオブジェクトは、ヒープのセクション内のページ（またはページ群）上でグループ化される。
【００６７】
一例においては、カウンタを使用して、どのオブジェクトがホットであるかを判定する。別の例においては、コンパイラ（またはＪＩＴコンパイラ）を使用して、ヒープデータにアクセスする、あるクリティカルな命令のためのリードバリアを挿入する。このような一例において、このリードバリアコードは、カウンタが設定されていないときそれを更新するヘルパールーチンに対する単一の呼出し命令を含む。ライトバリアは、コンパイラにより自動的に生成されて、ジェネレーショナルＧＣをサポートし、カウンタの条件付き更新を挿入するため変更することが出来る。
【００６８】
このような一例において、システムは、カウンタの実装、リードバリアの実装、および読取および／または書込をカウントするためのオブジェクト（例えば、ヒープに対して読込／書込をするオペレーション）のインストゥルメンテーションを含む。
【００６９】
オブジェクト参照カウンタは、各種の方法で実装することが出来る。例えば、オブジェクト参照カウンタは、オブジェクトに組込んでもよい。別の例において、オブジェクト参照カウンタは、別個のテーブルとして実装してもよい。別の例においては、オブジェクトに組込まれる１−ビットカウンタが使用される。このような実施例において、１つのオブジェクトがタッチされるとビットが設定されて、一間隔の間にそのオブジェクトが少なくとも一度タッチされたことを反映する。別の例においては、１つのオブジェクトに対応する数個のビットが、一間隔の間にオブジェクトがタッチされた回数を反映するカウンタとして機能することが出来る。このような一例において、それぞれのタッチは、タッチされるオブジェクトに対応するカウンタに加算される。タッチの閾値回数が、そのオブジェクトがホットであるか否かを確立する。一間隔における１つまたは複数のタッチを使用して、ホットオブジェクトを識別することが出来る。ホットオブジェクトには、一間隔の間にインスタンス化（作成）されたオブジェクトも含まれる。オブジェクトに対応する（単数または複数の）ビットは、オブジェクト自体の中または何処か別の場所に格納してもよい。オブジェクトに対応するカウンタがそのオブジェクトの外にあるときは、カウントのオーバーヘッドを最小にしなければならないので、速くアクセスすることの出来る位置にあるのが好適である。
【００７０】
別の例において、カウンタ（１つ以上のビット）は、オブジェクト自体の中に格納される。例えば、ＣＬＲは、各種目的（例えば、軽量ロックの実装のために）に使用することの出来るオブジェクトそれぞれのための４バイトのオブジェクトヘッダを有する。実施例によっては、１つまたは複数のこれら３２ビットのものを、カウンタのため（またはホットビットのため）使用することが可能である。
【００７１】
表Ｂは、リードバリアコードの一例に関するサンプルコードである。例えば、プロファイリングコードを使用してアクセスされたオブジェクトをマークすることが出来る。この例においては、ｒｇはオブジェクトアドレスを保持するレジスタであり、オブジェクトヘッダは、オブジェクトのスタートからオフセット−４にある。OBJECT_ACCESSED_BITは、オブジェクトヘッダ内に単一ビットを設定するのに使用されるビットマスクである。
【００７２】
【表２】
2006092532.tif 000004
【００７３】
このような一例においては、オブジェクトヘッダが（例えば、そのオブジェクト上にロックするとき）別のスレッドにより同時に変更されるので、インターロックされた操作を使用して、このビットを設定する。インターロックされた操作は、ｘ８６アーキテクチャ（例えば２０−３０クロックサイクル）上では高価な場合がある。さらに、マルチプロセッサ上のアプリケーションの拡張性を損なう場合がある読取操作の間に、キャッシュラインを汚染する場合がある。したがって、別の例においては、条件付きリードバリアはリードバリアコードのサイズを増加するけれども、無条件のリードバリアではなく、条件付きリードバリアを用いてもよい。別の例においては、増加したコードのサイズを小さくするため、リードバリアはインラインにしない。代わりに、リードバリアコードは、ヘルパールーチン（例えば、レジスタ毎に１つ）として実装される。
【００７４】
別の例においては、最適化アルゴリズムがリードバリアの数を減らして、性能を向上し、および／または追加コードの量を減少する。一例においては、採用されるリードバリアは、それに対する呼出しがアクセスポイント毎に挿入されない点で通常のアクセスバリアと異なる。例えば、リードバリアコードに対する呼出しは、共通部分式の削除（ＣＳＥ）の最適化にさらされる場合もある。別の例においては、例外の生成はまれなので、例外処理コードにプロファイリング呼出しは挿入されない。同様に、別の例においては、インラインでないコンストラクタは無視する。
【００７５】
さらに、カウンタ（またはホットビット）をリセットする時期を考慮することが望ましい。一例においては、カウンタがオブジェクトに組込まれているとき、そのカウンタはライブオブジェクト全てを走査しないでは手軽にクリアすることは出来ない。このような例においては、ガベージコレクション（ＧＣ）の最中にオブジェクトをトラバースしながら、カウンタをクリアする。別の例においては、局所性のためのＧＣの間に、ホットオブジェクトに遭遇する都度、カウンタをクリアする。
【００７６】
コピージェネレーショナルガベージコレクションを用いる一例においては、局所性のためのＧＣの間に、ガベージコレクションが頻繁に且つ安価に生じる低いジェネレーション内のオブジェクトに関して、カウンタのクリアが良く機能する。高いジェネレーションは、収集されることが少ないので、参照ビットは時間の経過と共に新鮮でなくなる。したがって、１つの代替例においては、到達可能性のグラフまたはヒープ全体をトラバースすることなく、カウンタをクリアする方法を備えるのが良い。例えば、到達度グラフまたはヒープ全体の完全なトラバーサルに依存することなくカウンタをクリアさせることが出来る（オブジェクトに対応する）カードテーブルを用いる。別の例においては、ページおよび／またはヒープに対応するホットビットテーブルまたはホットビットフィールドが、カウンタ／ビットをクリアする時間を軽減するのに役立つ。
【００７７】
（例示的なサンプリング）
一例において、上述のインストゥルメンテーションモデルは、低オーバーヘッドを有するので、全体としての性能の速度向上に十分適している。しかしながら、動的なヒープ再編成がアプリケーションの性能を著しくは向上させるとは限らないシナリオが幾つかある（例えば、利用可能のメモリに合わせるにはデータセットがあまりに小さいとき）。このようなアプリケーションに関しては、実装されたコード（例えばリードバリア）のコストは、高過ぎる場合がある（場合によっては、アプリケーションを４０％も劣化させる）。
【００７８】
インストゥルメンテーションのオーバーヘッドをさらに減少するのは、一例において、コードを断続的にプロファイルする場合のみである。例えば、方法がリードバリアをプロファイルすることで実装されている場合、方法の２番目のコピーは、実装しないものを生成してもよい。（即ち、監視、サンプリングなど）プロファイルする間は、実装されたバージョンが使用される。通常の操作の間は、実装しない方法が使用される。各方法の序盤は、コントロールの点検と転送を行うことを、方法を実装されたまたは実装されないバージョンの何れかに拡大適用することである。実施例によっては、バックエッジは変更されない。驚いたことに、この単純化はこの方法の実効性を低減しない場合がある（例えば、以下のベンチマーク上で−−長期にわたるホットループを有するいくらかの合成ベンチマークを除く）。さらなる最適化として、２つのコピーは２つの別個のコードヒープ内に配置してもよい。
【００７９】
多数の要因があって、これを変更してサンプリングを制御することが出来る。例えば、実装されたコードのバージョンを使用する頻度、およびサンプリングが始まってから実装されたバージョンを使用する期間である。これら２つのパラメータを調節することにより、適度に低いプロファイルオーバーヘッドで、有用なプロファイル情報を入手することが出来る。
【００８０】
一例においては、コードの通常のバージョンを普通に動作させ、コードの実装されたバージョンは、短時間だけ、且つ定期的にのみ動作させる。例えば、実装されたコードは、１０ｓ毎に、１０ｍｓだけ動作させる。これは、定期的サンプリング期間の間に、何のオブジェクトがタッチされるかについての情報を生成する。この情報を用いて、ホットページをパックする。
【００８１】
（例示的なヒープ再編成）
ＣＬＲ  ＧＣは、ジェネレーショナルマークコンパクトガベージコレクタを実装し、小さいオブジェクトヒープを三つのジェネレーションに分割する。一例において、局所性のためのヒープ再編成は、０より大きいジェネレーションに限られる。ジェネレーション０コレクションの間にヒープ再編成をおこなわない理論的根拠の１つは、このジェネレーション０オブジェクトのほとんどが最近割り当てられたということである。それらは最近割り当てられたので、既にキャッシュまたはワーキングセット内にあり、したがって局所性改善からさほどの利益を受けない。一例において、ＧＣの間に、システムは、以下のようなオブジェクト全てを識別する。a) 前回の局所性コレクション以後ホットとしてマークされたオブジェクト、およびb) 収集されているジェネレーションに対し等しいか、または低いジェネレーションに属するオブジェクトである。この例においては、これらのオブジェクトのみが局所性最適化のための候補である。候補オブジェクト全てが識別された後、局所性最適化は、それらの配置方法および次いでホットオブジェクトをＧＣヒープ上で配置を戻すべき場所を判定することが出来る。
【００８２】
一例において、ホットオブジェクトのレイアウトは、２つのコピーフェーズを用いておこなわれる。第一に、階層分解順序（例えば、ホットオブジェクトが別のホットオブジェクトに対するポインタを含むときは、これらのホットオブジェクトを一緒にグループ化する）により、ホットオブジェクトをヒープの外で一時バッファにコピーして、ページ局所性の利益と共に、余分のオーバーヘッドなしに、何らかのキャッシュ局所性の利益を得る。元の位置は、フリーとマークされるのでコレクタにより再利用される。第二に、上手く再配置されたホットオブジェクトの集約を、次いでヒープの新しい方の端に配置を戻してもよい。別の例においては、二重コピーを避ける（例えば、ヒープの指定領域を予約することによる）。別の例において、レイアウトは、異なるジェネレーションからのオブジェクトを混合しない。
【００８３】
ホットオブジェクトの集まりをヒープの新しい方の端に配置することは、僅かな潜在的利点を有する。例えば、ここにはホットオブジェクトの集合体を収容するのに十分なスペースがあると思われる。さらに、古いジェネレーションを収集するのは新しいジェネレーションより高価なので、オブジェクトは偶発的に進めない方が良い。最後に、長命のオブジェクトは再使用された直後に死ぬ傾向があるので、降格はこれらオブジェクトの占有するスペースの再利用を加速する場合がある。実施例によっては、多数のオブジェクトを降格することは良くない場合がある。しかしながら、それでもこれは（ヒープの小さい部分を構成する）ホットオブジェクトのために、選択的に行ってもよい。さらに、ジェネレーション間のポインタをあまり多数作成しすぎないことが重要である。
【００８４】
（例示的な最適化トリガポリシー）
別の考察事項は、局所性のための最適化をトリガする時期の判定である。さらに、局所性最適化のネット性能の利益が低減するとき、無益に継続しないように、局所性最適化のトリガが働かない時期の判定である。
【００８５】
局所性最適化に関しトリガの時期を決定するためには幾つかの可能性または組合せがある。一例においては、ハードウエアパフォーマンスカウンタを監視して、ＤＴＬＢおよびＬ２キャッシュのミス率を決定する。ミスの増加の間、局所性のための最適化をトリガする。
【００８６】
別の例においては、メモリ圧力がかかったＧＣコレクションのレートを監視する。このような場合、ホットオブジェクト局所性最適化は、コレクションをトリガしたメモリの２番目、３番目、・・・Ｎ番目毎に行われる。例によっては、ＧＣをトリガしたメモリ圧力毎に局所性最適化を行うことが有益である。
【００８７】
別の例においては、オブジェクト割り当て率を監視する。新規オブジェクトの割り当てに著しい減少があるとき、アプリケーションは新規オブジェクトの割り当ての代わりに再使用をしていると推定される。割り当て率が低下して比較的安定すると、局所性に関する最適化がトリガされる。
【００８８】
別の例においては、オブジェクト内の参照カウントを見るのが有益な場合がある。オブジェクトに関する高い参照カウントは、同一オブジェクトが繰り返し何度もタッチされていることを示し、最適化が有利であると立証できる場合がある。しかしながら、参照カウントが低いときは、プロセッサが同一オブジェクトを何度も要求しないので、最適化が有益であると示すのは難しい。
【００８９】
別の例においては、割り当て率とパフォーマンスカウンタの双方を監視する。割り当て率が増加して高い間は、最適化は行わない。しかし、割り当て率が低下し比較的安定になると、プログラムのためのデータ構造が設定されたと考えられ、さらにそのオブジェクトが繰り返しアクセスされるだろうと考えられて、局所性最適化から利益を得る機会を作る。さらに、割り当て率が低下して比較的安定になると、パフォーマンスカウンタにより示されるようなＤＴＬＢまたはＬ２のキャッシュミスの高いレートは、最適化のため適切なトリガを提供すると考えられる。新規割り当てが低いので、ＤＴＬＢおよびＬ２のキャッシュミスは、ブロックがＲＡＭおよびキャッシュを出入りして迅速に移動していることを示しており、ホットオブジェクトを集めることは、全体としてＤＴＬＢおよびＬ２のキャッシュミスを減少すると思われる。
【００９０】
別の例においては、データ局所性のための最適化は、規則的または多様な間隔でトリガすることが出来るであろう。別の例においては、前の最適化により性能の改善が少ないと示され（例えば、最適化後もＤＴＬＢミス率が同じなど）、最適化の一間隔が小さ過ぎる場合、次の最適化の前の間隔を大きくすることが出来るだろう。以前の最適化がＤＴＬＢキャッシュミス率を閾値よりも大きく改善し、最適化の一間隔が大き過ぎる場合は、次の最適化を早めにトリガしてもよい。
【００９１】
これらの学習の組合せも可能である。パフォーマンスカウンタ法に伴う欠点の１つは、これらがプロセスに対し通常は仮想化されない（即ち、全体的にカウントしている）ので、システム上で動作する別のアプリケーションにより数値が歪められるであろう。しかしながら、それらは、チップによっては追加のコストを有しないとの利点を有する。それらは、処理と平行してカウントされる。実施例によっては、割り当てのレートは、局所性最適化をトリガするため、かなり信頼性のある測定基準になる場合がある。
【００９２】
一例においては、最適化をおこなうことの利益を監視することが有利である。例えば、パフォーマンスカウンタを使用して、最適化後にデータＴＬＢおよびＬ２キャッシュに関するミス率を測定する。データＴＬＢおよびＬ２キャッシュのミス率が、何らかの相対的な基準にしたがって改善されない場合、局所性のためＧＣをトリガすることを、暫くの期間または利益がコストを正当化することを示す結果になるまで、中止するかまたは減少するのが望ましい場合がある。
【００９３】
このように、アクセスされたオブジェクトをクラスタするため、ヒープの再編成を直接または間接にトリガするものは何でも、プログラム挙動と見なされる。監視されるプログラム挙動が示されるとき、ヒープは再編成される（例えば、クラスタされる）。1つまたは複数の監視されるプログラム挙動インジケータが、ライブホットオブジェクトのヒープ再編成をトリガすることが出来る。
【００９４】
（例示的なＧＣの増加率）
メモリ圧力のためＧＣをトリガすることに関する多数の文献は、追加のＧＣのコレクションのコストが高いため、ＧＣのコレクションの数を減少させることに注力している。その代わり、本明細書の方法とシステムは、多くのＧＣのコレクションが、局所性最適化により補強される場合、ＧＣのコレクションの数が増加するときであっても、全体としての性能を向上させることを示す。一例において（下に記述するような、Ｘａｍｌパーサテスト）、ＧＣのコレクションが５０％も増加するが、全体としての性能は改善される。
【００９５】
（例示的なパフォーマンスカウンタ）
プロセッサによっては、パフォーマンスカウンタの各種バージョンを提供するものがある。一例において、パフォーマンスカウンタは、何のオブジェクトがタッチするかを判定する方法を提供する（例えば、ＩＡ６４プロセッサ）。この例においては、コードを実装する必要はない場合がある。パフォーマンスカウンタが、一定期間中にまたはカウンタがリセットされて以後、何のオブジェクト（例えば、ヒープの中のアドレス）がタッチされたかを示す。これは、ホットオブジェクトを識別するためにヒープにタッチする操作を実装する必要がないので有益であろう。例えば、この命令を通じてＴＬＢミスアドレスを提供することが出来るだろう。
【００９６】
その上、メモリの中のオブジェクトがアクセスされる（例えば、読取／書込）ときは何時でも記録する命令がすぐに導入されるとの噂がある。これらのアドレスまたはオブジェクトは、内部のサーキュラバッファに記録されて利用可能になる。
【００９７】
アクセスされるこれらのオブジェクトは、ホットページ（単数または複数の）の作成に必要な情報を提供する。
【００９８】
（例示的なクラスタリング）
割り当てられたオブジェクトは「ライブ」であるが、また最近アクセスされたライブオブジェクトのみが「ホット」である。歴史的に、ホットオブジェクトは、ガベージコレクションを行う際には、知られても考えられてもいなかった。ガベージコレクションの間に、ライブオブジェクトは圧縮され、デッドオブジェクト（例えば、割り当て解除または解放されたオブジェクト）は新たなフリースペースのため集められた。本明細書の技術を使用して、ガベージコレクションを必要としなくても、ライブオブジェクトはまとめてヒープ上にクラスタされる。面白いことに、この技術が重要な利益を与えるためには、アクセスされたオブジェクト全部をヒープの同一領域に配置することが必要とは限らない。例えば、サンプリング期間を用いて、アクセスされるオブジェクトを監視しアクセスビットを設定するときは、サンプリング期間の間にアクセスされるオブジェクトのみがヒープの上のホットクラスタに配置される。したがって、ヒープ上の１つまたは複数のクラスタは、この技術の範囲内であるために、最近アクセスされたオブジェクト全部を含む必要はない。その上、オブジェクトアクセス監視が継続的なときであっても（定期的なサンプリング期間、またはその他の場合と比較して）、記述した技術から有意義な利益を得るために、アクセスされたオブジェクト全部を同一クラスタ内に配置する必要があるとは限らない。例えば、ヒープの何処かに２つのクラスタが作成されると、ヒープのページ全体にわたって分散するのではなく、二箇所（数箇所の位置であっても）で、ホットオブジェクトを有することは、重要な利益がある。このように、ホットライブオブジェクトの密度の著しく高い１つまたは複数の位置にあるヒープ上にライブホットオブジェクトをクラスタすることを検討する。勿論、ホットオブジェクトが、単一クラスタ内に密接に近接して配置されると、これはさらに良い結果を与える。例えば、ヒープの１ページ以内にうまく納まるクラスタは理想的であるかもしれないが、必ずしも必須ではない。別の例において、ホットオブジェクトのワーキングセットが、ヒープ上の複数のページを占有するのに十分な大きさであるときは、これら複数のページを互いに近接して配置するのが有益な場合があるが、必須ではない。別の例においては、キャッシュが、ホットオブジェクトのクラスタを受け入れるのに十分な大きさであると役に立つ。このような一例において、ホットオブジェクトのワーキングセットが複数のクラスタを占有するとき、クラスタのうち１つがキャッシュに運び込まれるときはいつも、そのクラスタ内にある別のホットオブジェクトが間もなくアクセスされる可能性がある。さらに、キャッシュに出入りする確率の高いクラスタを交換することは、それぞれ個々のクラスタがヒープ上で含まれる場所に関係なく、僅かの交換で済むと思われる。これらの考察の全ては、最近アクセスされたライブオブジェクトをクラスタ化することを意図する。最後に、最近割り当ててられたオブジェクトの近傍にクラスタすることは、追加の利益を与える。例えば、ジェネレーショナルガベージコレクションヒープにおいて、ヒープの最も新しいジェネレーションに近くクラスタすることは、新たに割り当てられたオブジェクトも一般的に古いオブジェクトよりホットなので、役に立つ。
【００９９】
（例示的なベンチマーク）
一例において、実験結果を考察した。プロトタイプがホットオブジェクトのＧＣヒープ再編成をトリガすると、その再編成が性能に有益な結果を与えた。使用したプロトタイプは、ウインドウズＸＰオペレーティングシステム上で無効にされた同時に実行可能なＧＣを有する市販ＣＬＲ実装のワークステーションバージョンであった。実験は、メモリ、キャッシュサイズ、およびＣＰＵ速度の異なる構成の数個のマシンの上で行った。局所性のためのＧＣは、小さいＬ２キャッシュとメモリを有するマシン上で、性能を最も良く改善した。これは予期しないことではない。
【０１００】
４つのマイクロベンチマークを作成し、Ｃ＃で書かれた２つのアプリケーションを解析のため入手した。４つのマイクロベンチマーク（即ち、ツリー、アレー、Ｓリストおよびハッシュテーブル）は、局所性のためのＧＣの性能強化を試験するため書かれた。このマイクロベンチマークは、何らかのガベージデータでインターリーブされランダムに生成される多数のデータからそれぞれのデータ構造を作成する。このマイクロベンチマークは、訓練ループと強制実行ＧＣの後に、データ群を繰り返し検索する。「Ｘｍａｌパーサテスト」と呼ばれる１つの試験アプリケーションは、ＸＡＭＬファイルから３回読取って、パーサの異なるコンポーネントの性能を測定する。ＸＡＭＬ（拡張可能アプリケーションマークアップ言語）は、ＸＭＬに基づく。使用した入力ファイルは、簡単だが１１０００レベルの深くネストされたノードを含む。別の「ＳＡＴソルバ」と言う名のアプリケーションは、そのＣ＋＋実装からＣ＃実装に変換されたＳＡＴソルバである。入力ファイルは、２４６４０  ３２５０−可変ＣＮＦ（論理積正規形）に伴う問題インスタンスを記述する。
【０１０１】
（例示的な性能結果）
ベンチマークのための実行時間を、表Ｃに示す。作成された４つのマクロベンチマーク全部について、最適化は期待通りに行う。しかしながら、得られたベンチマークの2つについて、局所性のためのＧＣの性能は、Ｘｍａｌパーサテストを著しく改善しＳＡＴソルバを少ししか改善しない。性能の利益は、ポインタ集約的なアプリケーションにおいては、低減する。このような例においては、ガベージコレクション自体のオーバーヘッドは、実行時間のおよそ１／６から１／３に達しており、最適化（即ち、ＧＣの間のホットオブジェクトの監視および再編成）がなくても、既に高過ぎる。
【０１０２】
【表３】
2006092532.tif 000005
【０１０３】
（例示的なプロファイリングオーバーヘッド）
インストゥルメンテーションバーヘッドは、常時オン方法を採用するか、またはサンプリング方法を採用するかによって変動する場合がある。表Ｄは、常時オン方法とサンプリング方法とのプロファイリングオーバーヘッドを比較している。サンプリングは、プロファイリングオーバーヘッドが最適化を受けられるようにする。
【０１０４】
【表４】
2006092532.tif 000006
【０１０５】
（例示的なページ密度改善）
表Ｅは、１間隔毎にアクセスされたページ数の平均値およびページ密度の平均値を、最適化（即ち、ホットオブジェクトを（単数または複数の）ページ上で再編成するためＧＣをトリガすること）有りと無しについて、示す。これを測定するのに、メモリ参照のトレースを収集し、実行を１００００００参照間隔に分割し（ハッシュテーブルマイクロベンチマークに関して、１間隔毎に１０００００００回の参照を含む）、１間隔当たりにアクセルされたページ数および各ページ上で実際にアクセスされたデータの百分率を最後の１０００間隔について計算する。一般的に、プログラムのアクセスパターンにしたがってオブジェクトをパックすることにより、最適化は各ページ上でワーキングセットを減少し「有用な」データを増加する場合がある。ＳＡＴソルバについては、１間隔当たりにアクセスされるページ数は、最適化と共に増加する。それは、最適化はさらに多数のＧＣを伴い、それらの各々がヒープの一部または全部を走査し、計算はガベージコレクタがおこなうアクセスを除外しないからである。
【０１０６】
【表５】
2006092532.tif 000007
【０１０７】
（例示的な局所性改善）
最適化の改善を、ワーキングセット及びページ密度の上で検証するため、表Ｆに示すように、ＤＴＬＢミスの数に関してもデータを収集した。ワーキングセット及びページ密度の上での改善の結果、最適化はＤＴＬＢミスをも減少する。表Ｆには、ベンチマークについてＬ２ミスの数も示す。最適化はキャッシュ局所性には中心を置かないけれども、これは、キャッシュ局所性にも大変良く働く。
【０１０８】
【表６】
2006092532.tif 000008
【０１０９】
（例示的コンピューティング環境）
図８および以下の議論は、実装のために適切なコンピューティング環境の、簡潔で一般的な記述を提供することを目的とする。本発明を、コンピュータおよび／またはネットワークデバイスの上で動作するコンピュータプログラムのコンピュータ実行可能命令の一般的コンテキストにおいて記述するであろうが、当業者は、本発明が別のプログラムモジュールとの組合せにおいて実装されてもよいことを認識するであろう。一般的に、プログラムモジュールは、特定のタスクを行うかまたは特定の抽象データタイプを実装するルーチン、プログラム、コンポーネント、データ構造などを含む。さらに、当業者にとって当然のことながら、本発明を、マルチプロセッサシステム、マイクロプロセッサベースの電子機器、ミニコンピュータ、メインフレームコンピュータ、ネットワーク機器、無線装置、等を含む別のコンピュータシステム構成を用いて実施してもよい。  拡張は、ネットワークコンピューティング環境、またはスタンドアロンコンピュータの上で実施することができる。
【０１１０】
図８を参照すると、実装のための例示的システムは、（パーソナルコンピュータ、ラップトップ、サーバ、メインフレーム、およびその他の多種多様のコンピュータのような）従来のコンピュータ８２０を含み、（このコンピュータは）処理ユニット８２１，システムメモリ８２２．およびシステムメモリを含む各種のシステムコンポーネントを処理ユニット８２１に対して接続するシステムバス８２３を含む。処理ユニットは、市販で入手することのできる任意の各種プロセッサであって、Iｎｔｅｌ社のｘ８６、Ｐｅｎｔｉｕｍ（登録商標）および、Ｉｎｔｅｌ社およびＣｙｒｉｘ社、ＡＭＤ社およびＮｅｘｇｅｎ社を含む他社の互換性のあるマイクロプロセッサ、Ｄｉｇｉｔａｌ社のＡｌｐｈａ、ＭＩＰＳ  Ｔｅｃｈｎｏｌｏｇｙ社、ＮＥＣ社、ＩＤＴ社、Ｓｉｅｍｅｎｓ社および他社のＭＩＰＳ、Ｓｕｎ社および他社のＳＰＡＲＣ、およびＩＢＭ社とＭｏｔｏｒｏｌａ社のＰｏｗｅｒＰＣを含む。デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャも処理ユニット８２１として使用することができる。
【０１１１】
システムバスは、バス構造のいくつかのタイプのいずれかであってもよく、メモリバスまたはメモリコントローラ、ペリフェラルバス、および、数例を挙げるとＰＣＩ、ＶＥＳＡ、ＡＧＰ、マイクロチャンネル、ＩＳＡおよびＥＩＳＡのような任意の各種の従来のバスアーキテクチャを用いるローカルバスを含む。システムメモリは、リードオンメモリ（ＲＯＭ）８２４およびランダムアクセスメモリ（ＲＡＭ）８２５を含む。スタートアップの間などに、コンピュータ８２０の中の要素の間で情報を転送するのを助ける基本ルーチンを含む基本入出力システム（ＢＩＯＳ）は、ＲＯＭ８２４内に格納される。
【０１１２】
コンピュータ８２０はさらに、例えば、リムーバブルディスク８２９に読取／書込をするためのハードディスクドライブ８２７、磁気ディスクドライブ８２８、および、例えば、ＣＤ−ＲＯＭディスク８３１を読取りまたはその他の光媒体に読取／書込をするための光ディスクドライブ８３０を含む。ハードディスクドライブ８２７、磁気ディスクドライブ８２８および光ディスクドライブ８３０は、それぞれハードディスクドライブインターフェース８３２、磁気ディスクドライブインターフェース８３３および光ディスクドライブインターフェース８３４を用いて、システムバス８２３に接続される。ドライブおよびそれに関連したコンピュータ読取可能媒体は、データ、データ構造、コンピュータ実行可能命令などの不揮発性ストレージを、コンピュータ８２０に提供する。コンピュータ読取可能媒体に関する上の記述は、ハードディスク、レムーバブル磁気ディスクおよびＣＤを指すが、当業者にとっては当然のことながら、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ等、コンピュータが読取ることのできる別のタイプの媒体も、例示的オペレーション環境において使用してもよい。
【０１１３】
オペレーティングシステム８３５，１つまたは複数のアプリケーションプログラム８３６、別のプログラムモジュール８３７、およびプログラムデータ８３８を含む多数のプログラムモジュールを、記述した監視および最適化８５６実施に加えて、ドライブおよびＲＡＭ８２５に格納してもよい。
【０１１４】
ユーザは、キーボード８４０およびマウス８４２のようなポインティングデバイスを通じて、コマンドおよび情報をコンピュータ８２０に入力してもよい。これらおよびその他の入力装置は、システムバスに結合されるシリアルポートインターフェース８４６を通じて処理ユニット８２１にしばしば接続されるが、パラレルポート、ゲームポートまたはユニバーサルシリアルバス（ＵＳＢ）のような、別のインターフェースにより接続してもよい。モニタ８４７または別のタイプの表示装置も、ビデオアダプタ８４８のようなインターフェースを経由して、システムバス８２３に接続される。モニタに加えて、コンピュータは典型的に、スピーカおよびプリンタのような、別の周辺出力装置（不図示）を含む。
【０１１５】
コンピュータ８２０は、リモートコンピュータ８４９のような、１つまたは複数のリモートコンピュータに対する論理接続を用いるネットワーク環境においてオペレートする。リモートコンピュータ８４９は、サーバ、ルータ、ピアデバイスまたはその他の共通ネットワークノードであり、メモリストレージデバイス８５０のみを図示したけれども、典型的にコンピュータ８２０に関連して記述した要素のほとんどまたは全部を含む。描かれている論理接続は、ローカルエリアネットワーク（ＬＡＮ）８５１および広域ネットワーク（ＷＡＮ）８５２を含む。このようなネットワーク環境は、事務所、企業内コンピュータネットワーク、イントラネットおよびインターネットにおいては普通のことである。
【０１１６】
ＬＡＮネットワーク環境において使用されるとき、コンピュータ８２０は、ネットワークインターフェースまたはアダプタ８５３を通じてローカルネットワーク８５１に接続される。ＷＡＮネットワーク環境において使用されるとき、コンピュータ８２０は、典型的に、インターネットのような広域ネットワーク８５２の上で（例えばＬＡＮ８５１およびゲートウェイまたはプロキシサーバ８５５を経由して）通信を確立するためのモデム８５４またはその他の手段を含む。モデム８５４は内部または外部であってもよいが、シリアルポートインターフェース８４６を通じてシステムバス８２３に接続される。ネットワーク環境において、コンピュータ８２０に関連して描かれたプログラムモジュール、またはその一部は、リモートメモリストレージ内に格納してもよい。当然のことながら、ここに示すネットワーク接続は例示的であり、無線あるいはその他の、コンピューティングデバイス間で通信リンクを確立するための他の手段を使用してもよい。
【０１１７】
代替案
図示する例を参照して本発明の原理を記述し図示したように、例は配置および細部において、当該原理から逸脱することなく変更することができることは認識されるであろう。その上、普通のコンピュータ科学者には明らかなように、例の一部または全部は、全体または一部において、別の例の別の部分と結合することができる。当然のことながら、ここに記述するプログラム、プロセスまたは方法は、別途に指示しない限り、特定のタイプのコンピュータ装置の何れにも関連または制限されない。各種のタイプの汎用または専門のコンピュータ装置が、ここに記述する技術に従って使用されるかまたはそれによってオペレーションを実行してもよい。ソフトウエアで示された実施形態の要素は、ハードウエアで実装してもよく、逆もまた同様である。一例からの技術を、別の例の何れにも組み込むことができる。
【０１１８】
本発明の原理が適用されてもよい多数の可能な実施形態の観点から、細部はただ例示的であって、本発明の範囲を制限すると理解してはならないことは認識されなければならない。むしろ、以下の請求項および同等の事項の範囲と精神の範囲内に入ってもよいこのような実施形態のすべてを、我々の発明として請求する。
【図面の簡単な説明】
【０１１９】
【図１】ヒープのデータ局所性を最適化するための例示的方法に関するフローチャートである。
【図２】ヒープのデータ局所性を最適化するための例示的システムのブロック図である。
【図３】変動するアクセス速度を有する複数レベルを経由するメモリ管理のための例示的システムのブロック図である。
【図４】最適化を行うための実行可能コード作成に関する例示的方法の図である。
【図５】最適化を行うためにメモリ内のページ全体に広がる例示的オブジェクトを示す例示的図である。
【図６】例示的ジェネレーショナルなガベージコレクション方法およびシステムの図である。
【図７】ガベージコレクションを用いるヒープのデータ局所性最適化のための例示的システムのブロック図である。
【図８】記述する技術を実装する分散コンピュータシステムのブロック図である。
【符号の説明】
【０１２０】
２００、３００  コンピュータシステム
３０２  中央処理装置
３０４  プロセッサ
３０６、３０８、３１０  オンチップキャッシュ
３１２、３１４  オフチップキャッシュ
３１６  ＲＡＭ
３２２  ページ
５００、６００  ヒープ
５０２  グリッド
５０４  ライブオブジェクト
５０６  廃棄されたオブジェクト
６０８  ジェネレーションバウンダリを示すデータ構造体
７０８  実装されたコード
【図１】
2006092532.tif 000009
【図２】
2006092532.tif 000010
【図３】
2006092532.tif 000011
【図４】
2006092532.tif 000012
【図５】
2006092532.tif 000013
【図６】
2006092532.tif 000014
【図７】
2006092532.tif 000015
【図８】
2006092532.tif 000016
【外国語明細書】
2006092532000001.pdf