(57)【特許請求の範囲】
【請求項１】
１つ以上のクラスによって定義される複数のオブジェクトをメモリ内で再配列するための機構を生成する方法であって、
前記１つ以上のクラスのうちの選択された１つのクラスの複数のオブジェクトに含まれる１つ以上のフィールドによって参照されるデータの、前記１つ以上のクラスのうちの前記選択された１つのクラスの前記複数のオブジェクトに含まれる前記複数のフィールドのうちの残りのフィールドによって参照されるデータに対する、メモリ内でのアクセス回数を測定する工程と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するためのクラスフィールド順序を、前記１つ以上のクラスのうちの前記選択された１つのクラスのために、前記アクセス回数から決定する工程と、
前記１つ以上のクラスの各々に対して、前記測定する工程と前記決定する工程とを繰り返す工程と、
前記１つ以上のクラスに属する前記複数のオブジェクトに含まれる前記複数のフィールドのメモリ内での前記アクセスの記録を、コンピュータアプリケーションの実行中に、生成する工程と、
各パスが前記コンピュータアプリケーションの実行中に採用される総回数を示すカウントを計算することを可能にするコンピュータコードを、前記コンピュータアプリケーションに挿入する工程と、
前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる他の複数のフィールドに対する各フィールドの参照回数を測定する工程と、
前記コンピュータアプリケーションの実行中に採用される前記パスの各々の前記カウントを計算するために、前記挿入されたコンピュータコードを用いる工程と、
前記クラスフィールド順序を、関連するクラスに対して決定するために、前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる他の複数のフィールドに対する各フィールドの前記測定された参照回数を、前記コンピュータアプリケーションの実行中に採用された前記パスの各々の前記計算されたカウントと結合する工程と、
前記１つ以上のクラスについて、前記クラスフィールド順序に従って、前記メモリ内の前記複数のオブジェクトを再配列する工程と、
を備える生成方法。
【請求項２】
請求項１記載の方法であって、
前記再配列する工程は、ガーベージコレクションプロセス中に実行される、生成方法。
【請求項３】
ガーベージコレクション中において、１つ以上のクラスによって定義される複数のオブジェクトの複数のフィールドが訪問される順序を変更するための機構を生成する方法であって、
前記１つ以上のクラスのうちの選択された１つのクラスの複数のオブジェクトに含まれる１つ以上のフィールドによって参照されるデータの、前記１つ以上のクラスのうちの前記選択された１つのクラスの前記複数のオブジェクトに含まれる前記複数のフィールドのうちの残りのフィールドによって参照されるデータに対する、メモリ内でのアクセス回数であって、前記複数のフィールドによって参照されるデータのメモリ内でのアクセスの参照の頻度と近さとを示すアクセス回数を測定する工程と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの前記複数のオブジェクトに含まれる前記複数のフィールドのうちの残りのフィールドの、メモリ内でのアクセスの頻度を確認する工程と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するためのクラスフィールド順序を、前記１つ以上のクラスのうちの前記選択された１つのクラスのために、前記アクセスの頻度から確認する工程と、
前記１つ以上のクラスのそれぞれのために、前記クラスフィールド順序を確認する工程と、前記アクセスの頻度を確認する工程と、前記測定する工程とを繰り返す工程と、
前記１つ以上のクラスに属する前記複数のオブジェクトに含まれる前記複数のフィールドのメモリ内での前記アクセスの記録を、コンピュータアプリケーションの実行中に、生成する工程と、
各パスが前記コンピュータアプリケーションの実行中に採用される総回数を示すカウントを計算することを可能にするコンピュータコードを、前記コンピュータアプリケーションに挿入する工程と、
前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる他の複数のフィールドに対する各フィールドの参照回数を測定する工程と、
前記コンピュータアプリケーションの実行中に採用される前記パスの各々の前記カウントを計算するために、前記挿入されたコンピュータコードを用いる工程と、
前記クラスフィールド順序を関連するクラスに対して決定するために、前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる他の複数のフィールドに対する各フィールドの前記測定された参照回数を、前記コンピュータアプリケーションの実行中に採用された前記パスの各々の前記計算されたカウントと結合する工程と、
を備える生成方法。
【請求項４】
１つ以上のクラスによって定義される複数のオブジェクトをメモリ内で再配列するための機構を生成する方法であって、
前記１つ以上のクラスのうちの選択された１つのクラスの複数のオブジェクトに含まれる１つ以上のフィールドによって参照されるデータの、前記１つ以上のクラスのうちの前記選択された１つのクラスの前記複数のオブジェクトに含まれる前記複数のフィールドのうちの残りのフィールドによって参照されるデータに対する、メモリ内でのアクセス回数を測定する工程と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するためのクラスフィールド順序を、前記複数のフィールドのメモリ内でのアクセス回数から決定する工程と、
前記１つ以上のクラスの各々に対して、前記アクセス回数を測定する工程と前記クラスフィールド順序を決定する工程とを繰り返す工程と、
を備える生成方法。
【請求項５】
請求項４記載の機構生成方法であって、さらに、
前記選択されたクラスに関連付けられた前記複数のフィールドを、該クラスの前記クラスフィールド順序に従って、ソートする工程を備える、生成方法。
【請求項６】
請求項４記載の機構生成方法であって、
前記アクセス回数は、前記複数のフィールドによって参照されるデータのメモリ内でのアクセスの頻度と近さとを示す、生成方法。
【請求項７】
請求項４記載の機構生成方法であって、
前記アクセス回数は、前記選択されたクラスの前記複数のフィールドの各々が、前記選択されたクラス内の別のフィールドの直後に参照される回数を特定する、生成方法。
【請求項８】
請求項４記載の機構生成方法であって、
前記アクセス回数は、前記選択されたクラスの前記複数のフィールドの各々が、前記選択されたクラス内の別のフィールドの直前に参照される回数を特定する、生成方法。
【請求項９】
請求項４記載の機構生成方法であって、
前記アクセス回数は、前記選択されたクラスの前記複数のフィールドの各々が、前記選択されたクラス内の別のフィールドの後に参照される回数を特定する、生成方法。
【請求項１０】
請求項４記載の機構生成方法であって、
前記アクセス回数は、前記選択されたクラスの前記複数のフィールドの各々が、前記選択されたクラス内の別のフィールドの前に参照される回数を特定する、生成方法。
【請求項１１】
請求項４記載の機構生成方法であって、
前記選択されたクラスに関する複数のフィールドのメモリ内でのアクセス回数を測定する工程は、
前記選択されたクラスの前記複数のフィールドのうちの１つが、前記選択されたクラスの前記複数のフィールドの残りのフィールドの各々から参照される回数を、前記複数のフィールドのうちの前記１つに対して１つ以上のカウントが生成されるようにカウントする工程と、
前記選択されたクラスに関する前記複数のフィールドの各々に対して前記カウントの工程を繰り返す工程と、
前記複数のフィールドの各々に関する前記１つ以上のカウントから前記クラスフィールド順序を生成する工程と、
を含む生成方法。
【請求項１２】
請求項４記載の機構生成方法であって、さらに、
コンピュータアプリケーションの実行中に前記１つ以上のクラスに関する前記複数のフィールドのメモリ内での前記アクセスの記録を生成する工程を備える、生成方法。
【請求項１３】
請求項１２記載の機構生成方法であって、
前記１つ以上のクラスに関する前記複数のフィールドのメモリ内での前記アクセスの記録を生成する工程は、前記コンピュータアプリケーションの実行中にメモリ内での前記アクセスのログを生成する工程を含む、生成方法。
【請求項１４】
請求項１２記載の機構生成方法であって、
前記１つ以上のクラスに関する前記複数のフィールドのメモリ内での前記アクセスの記録を生成する工程は、パスプロファイル生成を実行する工程を含む、生成方法。
【請求項１５】
請求項１２記載の機構生成方法であって、さらに、
各パスが前記コンピュータアプリケーションの実行中に採用される総回数を示すカウントを計算することを可能にするコンピュータコードを前記コンピュータアプリケーションに挿入する工程と、
前記パスの各々について、前記複数のクラスのうちの選択された同じ１つのクラスの複数のオブジェクトに含まれる残りの各フィールドに対する各フィールドの参照回数を決定する工程と、
前記コンピュータアプリケーションの実行中に採用される前記パスの各々の前記カウントを計算するために、前記挿入されたコンピュータコードを用いる工程と、
前記クラスフィールド順序を、関連するクラスに対して決定するために、前記パスの各々について、前記複数のクラスのうちの同じ１つのクラスの複数のオブジェクトに含まれる残りの各フィールドに対する各フィールドの前記決定された参照回数を、前記コンピュータアプリケーションの実行中に採用された前記パスの各々の前記計算されたカウントと結合する工程と、
を備える生成方法。
【請求項１６】
請求項４記載の機構生成方法であって、さらに、
前記１つ以上のクラスに関する前記クラスフィールド順序に従って、前記メモリ内の前記複数のオブジェクトを再配列する工程を備える、生成方法。
【請求項１７】
請求項１６記載の機構生成方法であって、
前記再配列の工程は、ガーベージコレクション処理中に実行される、生成方法。
【請求項１８】
請求項１７記載の機構生成方法であって、
前記ガーベージコレクション処理は、コピーによるガーベージコレクション処理である、生成方法。
【請求項１９】
請求項４記載の機構生成方法であって、さらに、
前記関連するクラスの前記クラスフィールド順序に従って、メモリ内の複数のオブジェクトの複数のフィールドをトラバースするガーベージコレクションコードを生成する工程を備える、生成方法。
【請求項２０】
請求項１９記載の機構生成方法であって、
前記生成されたガーベージコレクションコードは、オブジェクトのクラスを決定するとともに、前記複数のオブジェクトの前記クラスの前記クラスフィールド順序に従ってコピーによるコレクション中に前記オブジェクトの前記複数のフィールドを訪問する、生成方法。
【請求項２１】
メモリ内に格納された複数のオブジェクトのセットに対してガーベージコレクションを実行する方法であって、
メモリ内の複数のオブジェクトの前記セットのうちの１つを識別する工程と、
前記オブジェクトのクラスを確認する工程と、
前記オブジェクトの前記クラスに関するクラスフィールド順序であって、前記オブジェクトの前記クラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するクラスフィールド順序を決定する工程と、
前記オブジェクトの前記クラスに関する前記クラスフィールド順序に従って、ガーベージコレクション中に前記オブジェクトの前記複数のフィールドを訪問する工程と、
を備える実行方法。
【請求項２２】
メモリ内の１つ以上のクラスに関連付けられた複数のオブジェクトを再配列するための機構を作成するためのコンピュータ読み取り可能な記録媒体であって、
前記１つ以上のクラスのうちの選択された１つのクラスの複数のオブジェクトに含まれる１以上のフィールドの、前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のオブジェクトに含まれる複数のフィールドのうちの残りのフィールドに対する、メモリ内でのアクセスの頻度を確認するためのコンピュータ命令と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するためのクラスフィールド順序を、前記複数のフィールドのメモリ内でのアクセスの頻度から決定するためのコンピュータ命令と、
前記１つ以上のクラスの各々に対して前記頻度の確認と前記クラスフィールド順序の決定とを繰り返すためのコンピュータ命令と、
前記１つ以上のクラスに関する前記複数のフィールドのメモリ内での前記アクセスの記録を、コンピュータアプリケーションの実行中に、生成するためのコンピュータ命令と、
各パスが前記コンピュータアプリケーションの実行中に採用される総回数を示すカウントを計算することを可能にするコンピュータコードを、前記コンピュータアプリケーションに挿入するためのコンピュータ命令と、
前記パスの各々について、前記複数のクラスのうちの同じ１つのクラスに含まれる残りの各フィールドに対する各フィールドの参照回数を測定するためのコンピュータ命令と、
前記コンピュータアプリケーションの実行中に採用される前記パスの各々の前記カウントを計算するために、前記挿入されたコンピュータコードを用いるためのコンピュータ命令と、
前記クラスフィールド順序を、関連するクラスに対して決定するために、前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる残りの各フィールドに対する各フィールドの前記測定された参照回数を、前記コンピュータアプリケーションの実行中に採用された前記パスの各々の前記計算されたカウントと結合するためのコンピュータ命令と、
を含む記録媒体。
【請求項２３】
請求項２２記載のコンピュータ読み取り可能な媒体であって、さらに、
前記関連のクラスの前記クラスフィールド順序に従って、メモリ内の複数のオブジェクトの複数のフィールドをトラバースするガーベージコレクションコードを生成するためのコンピュータ命令を含む、媒体。
【請求項２４】
メモリ内の１つ以上のクラスに関連付けられた複数のオブジェクトを再配列するための機構を生成するためのシステムであって、
プロセッサと、
コンピュータ命令を格納するメモリとを含み、
前記コンピュータ命令は、
前記１つ以上のクラスのうちの選択された１つのクラスの複数のオブジェクトに含まれる１以上のフィールドの、前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のオブジェクトに含まれる複数のフィールドのうちの残りのフィールドに対する、メモリ内でのアクセスの頻度を確認するためのコンピュータ命令と、
前記１つ以上のクラスのうちの前記選択された１つのクラスの複数のフィールドがガーベージコレクション中にトラバースされる順序を識別するためのクラスフィールド順序を、前記複数のフィールドのメモリ内でのアクセスの頻度から決定するためのコンピュータ命令と、
前記１つ以上のクラスの各々に対して前記頻度の確認と前記クラスフィールド順序の決定とを繰り返すためのコンピュータ命令と、
前記１つ以上のクラスに関する前記複数のフィールドのメモリ内での前記アクセスの記録を、コンピュータアプリケーションの実行中に、生成するためのコンピュータ命令と、
各パスが前記コンピュータアプリケーションの実行中に採用される総回数を示すカウントを計算することを可能にするコンピュータコードを、前記コンピュータアプリケーションに挿入するためのコンピュータ命令と、
前記パスの各々について、前記複数のクラスのうちの同じ１つのクラスに含まれる残りの各フィールドに対する各フィールドの参照回数を測定するためのコンピュータ命令と、
前記コンピュータアプリケーションの実行中に採用される前記パスの各々の前記カウントを計算するために、前記挿入されたコンピュータコードを用いるためのコンピュータ命令と、
前記クラスフィールド順序を、関連するクラスに対して決定するために、前記各パスについて、前記複数のクラスのうちの同じ１つのクラスに含まれる残りの各フィールドに対する各フィールドの前記測定された参照回数を、前記コンピュータアプリケーションの実行中に採用された前記パスの各々の前記計算されたカウントと結合するためのコンピュータ命令と、
を含むシステム。
【請求項２５】
請求項２４記載の機構生成システムであって、
前記メモリは、さらに、前記関連するクラスの前記クラスフィールド順序に従って、メモリ内の複数のオブジェクトの複数のフィールドをトラバースするガーベージコレクションコードを生成するためのコンピュータ命令を格納する、システム。
【請求項２６】
請求項２４記載の機構生成システムであって、
前記機構生成システムは、Ｊａｖａ（登録商標）プラットフォームに実装される、システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、コンピュータソフトウェアに関する。特に、本発明は、メモリにおけるデータの配置を改善することにより、データへのアクセス速度を増大させることに関する。
【０００２】
【従来の技術】
キャッシュメモリは、メモリ速度を増大させるためにメインメモリと組み合わせて用いられることが多い。通常、データの部分は、キャッシュメモリが、メインメモリのこれらの部分のコピーを含むように、メインメモリからコピーされる。ＣＰＵがワードを読むことを試みる際には、そのワードがキャッシュ内にあるか否かを決定するための確認がなされる。そのワードがキャッシュ内にある場合には、そのワードは、キャッシュから読み出される。そうでない場合には、多くのワードが、メインメモリから読み出されてキャッシュに格納され、上述のワードがＣＰＵに提供される。
【０００３】
ワードがキャッシュ内にない場合には、メインメモリから読み出す必要があり、そのため、メモリアクセス時間が増大する。要求されるデータがキャッシュ内に存在する可能性を高めるために、キャッシュは通常、どのデータがアクセスされるかをヒューリスティクスによって予測し、このデータをキャッシュにコピーする。そのため、コンピュータのメモリシステムは、最も頻繁にアクセスされる項目をプロセッサの近くに維持するために、キャッシュを頼りにすることが多い。
【０００４】
キャッシュには複数のワードが同時に格納されるので、メモリ内のデータの配置が、キャッシュの効率に影響し、それによって、コンピュータシステム全体の動作速度に影響する可能性がある。したがって、速度を最大にするためには、メモリ内のデータ（例えば、オブジェクト）を効率的に配置すべきである。以前に提案された技術は、大きなオーバーヘッドを有し、すなわち、Ｊａｖａバイトコードを実行するような動的な環境では用いることができない。
【０００５】
もはやメモリから参照されないオブジェクトを削除するために、しばしば、ガーベージコレクションが実行される。一般に用いられているガーベージコレクションの２つの実行方法は、「マーク・アンド・スイープ」を行う方法と「コピーによるガーベージコレクション」を行う方法とである。以下に詳しく説明するように、メモリ内でのデータの再配置は、ガーベージコレクションのプロセスの間に、ある程度までは実行することができる。
【０００６】
図１Ａは、従来のマーク・アンド・スイープによるガーベージコレクションのプロセスにおけるメモリ内のオブジェクトの配置を示すブロック図である。図１Ａには、オブジェクト１０２、１０４、１０６、および１０８が示されている。より詳細には、オブジェクト１０２は、オブジェクト１０４および１０６の両方を参照し、実行スレッドによって参照されている。マーク・アンド・スイープによるガーベージコレクションは通常、２つのパスで実行される。第１のパスでは、オブジェクトによって参照されない各オブジェクトがマークされる。例えば、オブジェクト１０８は、オブジェクト１０２、１０４、および１０６のいずれによっても参照されないため、削除のためにマークされる。第２のパスでは、マークされない各オブジェクトのためのメモリは再利用される。
【０００７】
図１Ｂは、従来のマーク・アンド・スイープによるガーベージコレクションプロセスの完了時における図１Ａのメモリを示すブロック図である。図示されているように、図１Ａでマークされたオブジェクト１０８は、削除されたために図１Ｂには示されていない。オブジェクト１０２、１０４、および１０６は、ガーベージコレクションプロセスの完了後も残っている。オブジェクトは、マーク・アンド・スイープによるガーベージコレクションの間、通常は再配置されないことに注意すべきである。
【０００８】
ガーベージコレクションの別の方法（すなわち、コピーによるガーベージコレクション）も、一般に用いられている。図２Ａは、従来のコピーによるガーベージコレクションのプロセスにおけるメモリ内のオブジェクトを示すブロック図である。図示されているように、メモリ２００内には、複数のオブジェクトが存在する。例えば、第１のオブジェクト２０２（Ａ）、第２のオブジェクト２０４（Ｂ）、および第３のオブジェクト２０６（Ｄ）は、メモリ内に格納されており、すべてルートから到達可能である。さらに、第４のオブジェクト２０８（Ｃ）は、メモリ２００内に格納されているが、メモリ内の他のオブジェクトによって参照されていない。
【０００９】
図２Ｂは、従来のコピーによるガーベージコレクションプロセスの完了時における図２Ａのメモリを示すブロック図である。コピーによるガーベージコレクションでは、１つ以上のオブジェクトによって参照されているオブジェクトはすべてコピーされ、他のオブジェクトによって参照されていないオブジェクトはコピーされない。そのため、コピーされていないオブジェクトはすべてガーベージである。例えば、図２Ｂに示されているように、第４のオブジェクト２０８（Ｃ）は、コピーされていない。コピーされると、図２Ａに示されている元のオブジェクトのためのメモリは、再利用されてもよい。
【００１０】
コピーによるガーベージコレクションでは、オブジェクトは、コピーのプロセス中には様々な順序で配置されてよい。図３Ａは、メモリ内のオブジェクトの構成例を示すブロック図である。図示されているように、メモリ３００は、第１のオブジェクト３０２（Ａ）と、第２のオブジェクト３０４（Ｂ）と、第３のオブジェクト３０６（Ｄ）とを格納している。第１のオブジェクト３０２は、第２のオブジェクト３０４および第３のオブジェクト３０６の両方を参照している。第４のオブジェクト３０８（Ｃ）は、どのオブジェクトからも参照されていない。
【００１１】
第１のオブジェクト３０２は、第２と第３のオブジェクト３０４、３０６両方を参照しているので、それらのオブジェクトは、２つの異なる順序で配置することができる。図３Ｂは、コピーによるガーベージコレクションの完了時における図３Ａのオブジェクトの１つの可能な構成を示すブロック図である。図示されているように、第２のオブジェクト３０４は、第１のオブジェクト３０２に隣接して配置され、第３のオブジェクト３０６は、第２のオブジェクト３０４に隣接して配置されている。
【００１２】
図３Ｃは、コピーによるガーベージコレクションの完了時における図３Ａのオブジェクトの別の可能な構成を示すブロック図である。図示されているように、第２のオブジェクト３０４を第１のオブジェクト３０２に隣接して配置せずに、第３のオブジェクト３０６が、第１のオブジェクト３０２に隣接して配置されている。図３Ｂおよび図３Ｃに示されている簡単な例では、それらのオブジェクトは、２つの異なる順序で配置することができる。オブジェクトの順序付けと共に、メモリ内のオブジェクトのアクセス速度を最大にすることを可能にする機構が設計されたら有益であろう。
【００１３】
オブジェクト指向のプログラミングにおいては、コードとデータがオブジェクトに組み込まれる。各オブジェクトは、オブジェクトの特性を決定するクラスを通して定義される。すなわち、オブジェクトは、あるクラスの個々のインスタンスである。さらに、各オブジェクトは、メソッドはもちろん、様々なフィールドも含んでいてよい。
【００１４】
「Ｕｓｉｎｇ  Ｇｅｎｅｒａｔｉｏｎａｌ  Ｇａｒｂａｇｅ  Ｃｏｌｌｅｃｔｉｏｎ  Ｔｏ  Ｉｍｐｌｅｍｅｎｔ  Ｃａｃｈｅ−Ｃｏｎｓｃｉｏｕｓ  Ｄａｔａ  Ｐｌａｃｅｍｅｎｔ」、Ｔｒｉｓｈｕｌ  Ｍ．  ＣｈｉｌｉｍｂｉとＪａｍｅｓ  Ｒ．  Ｌａｒｕｓ著、メモリ管理に関する国際シンポジウム（ＩＳＭＭ  ‘９８）、１９９８年１０月、に記載されているように、互いに近い時間にアクセスされるオブジェクトは、同じキャッシュラインでフェッチされるようにメモリに格納することができる。Ｃｈｉｌｉｍｂｉに開示されているそのプロセスについて、図４Ａ、４Ｂ、および４Ｃを参照して簡単に説明する。図４Ａは、メモリおよび関連フィールドに格納されたオブジェクトのセットの例を示すブロック図である。図示されているように、第１のオブジェクト４００（Ａ）は、第１のフィールド４０２（ｘ）と、第２のフィールド４０４（ｙ）とを含む。同様に、第２のオブジェクト４０６（Ｂ）は、第１のフィールド４０８（ｗ）と、第２のフィールド４１０（ｚ）とを含む。第３のオブジェクト４１２（Ｃ）は、フィールド４１４（ｅ）を含み、第４のオブジェクト４１６（Ｄ）は、フィールド４１８（ｆ）を含む。
【００１５】
図４Ｂは、図４Ａのオブジェクトおよびフィールドにアクセスするコンピュータアプリケーションの実行中に作成できるメモリアクセスのログの例を示すブロック図である。Ｃｈｉｌｉｍｂｉでは、コンピュータアプリケーションは、メモリ参照（例えば、ロードや格納のコマンド）が記録されるように実装される。実装されたコンピュータアプリケーションが実行されると、メモリアクセスのログ４２０が作成される。より詳細には、オブジェクト４２２が、メモリアクセスごとに記録される。例えば、第１のオブジェクト４００（Ａ）のフィールド（例えば、第１のフィールド４０２）がメモリからフェッチされると、このメモリアクセスは、エントリ４２６に示されているように記録される。
【００１６】
次いで、メモリアクセスのログは、オブジェクト間の参照の局所性をモデリングする一時的な参照グラフを作成するために用いられる。図４Ｃは、メモリ内のオブジェクトのアクセスと、図４Ｂに示されているメモリアクセスのログから作成できるこれらのメモリアクセスの一時的な関係とを示す一時的な参照グラフの例である。一時的な参照グラフ４２８に示されているように、オブジェクトのアクセスは、メモリアクセスのログ４２０に示されるメモリアクセスの一時的な関係に従って、グラフに配置される。次いで、一時的な参照グラフ４２８は、近い時間にアクセスされるオブジェクトが互いに近く配置されるようにオブジェクトの適切な配置を実現するために用いることができる。より詳細には、一時的な参照グラフ４２８は、コピーによるガーベージコレクションの際にオブジェクトがコピーされる順序を導くために用いられる。しかしながら、Ｃｈｉｌｉｍｂｉは、対応するメモリアクセス内でアクセスされる特定のフィールドを無視していることに注意すべきである。さらに、ログの作成は、すべてのメモリ参照に対してかなりのオーバーヘッドを必要とするため、時間とメモリリソースを必要とする。
【００１７】
Ｃｈｉｌｉｍｂｉは、メモリ内のオブジェクトを再配列する工程を開示しているが、これらのオブジェクト内でアクセスされる特定のフィールドは無視されている。Ｃｈｉｌｉｍｂｉは、そのフィールドのアクセスを無視しているが、単一のオブジェクト内でのフィールドの再配列は考慮されており、それについては、図５Ａ、図５Ｂ、および図５Ｃを参照して説明する。
【００１８】
図５Ａは、メモリおよび関連フィールドに格納されたオブジェクトのセットの例を示すブロック図である。図示されているように、第１のオブジェクト５００（Ａ）は、第１のフィールド５０２（ｙ）と、第２のフィールド５０４（ｘ）と、第３のフィールド５０６（ｖ）とを含む。さらに、第２のオブジェクト５０８（Ｂ）は、第１のフィールド５１０（ｚ）と、第２のフィールド５１２（ｗ）とを含む。
【００１９】
図５Ｂは、図５Ａのオブジェクトおよびフィールドにアクセスするコンピュータアプリケーションの実行中に作成できるメモリアクセスのログの例を示すブロック図である。メモリアクセスのログ５１４では、メモリ内でアクセスされた各オブジェクト５１６および関連のフィールド５１８が、識別および記録される。例えば、図示されているように、第２のフィールド５０４（ｘ）が第１のオブジェクト５００内でアクセスされた場合には、アクセスされたオブジェクト５２０（Ａ）とアクセスされたフィールド５２２（ｘ）とが記録される。
【００２０】
メモリアクセスのログが作成されると、そのログは、記録されたメモリアクセスの間の一時的な関係を決定するために用いられる。次いで、オブジェクト間の参照の局所性をモデリングする一時的な参照グラフが作成される。図５Ｃは、図５Ｂのログに示されたフィールド参照の間の一時的な関係を示す一時的な参照グラフ５２４の例である。そのグラフ５２４は、アクセスされたオブジェクト間の関係を示さずに、アクセスされたフィールド間の関係を示す。図示されているように、第１のオブジェクト５００（Ａ）の第１および第２のフィールド５０２（ｘ）および５０４（ｙ）が、グラフ化される。次いで、一時的な参照グラフ５２４は、オブジェクトＡ内でフィールドｘおよびｙを再配列するために用いられる。図示されているように、一次的な参照グラフ５２４は、フィールドｘおよびｙの互いに対しての順序が不適切であることを示している。しかしながら、第３のフィールド５０６（ｖ）の格納は、ｘおよびｙが互いに近くなるように、ｘおよびｙの格納を妨げてはならない。このように、ある特定のオブジェクト内のフィールドが再配列されてもよい。フィールドは、単一のオブジェクト内で再配列されたが、フィールドアクセスは、それらのフィールドが参照するオブジェクトを再配列するための解析を実行されていない。
【００２１】
各メモリ参照を装備せずに、パスプロファイル作成を通して実行しているプログラムが遭遇する制御フローのパスを装備することもできる。図６Ａは、コンピュータアプリケーションの実行中に可能なパスすべてを示すブロック図である。この例では、各ブロックは１つ以上のコンピュータの命令を表している。ブロック６００は、条件ステートメント６０２の前に実行される。例えば、条件ステートメント６０２は、ｉｆ‐ｔｈｅｎ‐ｅｌｓｅステートメントでよい。ｉｆ‐ｔｈｅｎ‐ｅｌｓｅステートメントの結果によると、実行可能な分岐は２つである。第１の分岐は、ブロック６０４および６０６を含む。第２の分岐は、ブロック６０８および６１０を含む。
【００２２】
パスプロファイル作成が実行されると、制御フローのパスが装備される。図６Ｂは、図６Ａのコンピュータアプリケーションに関連する可能なパスを示すパスプロファイルの例を示す図である。図示されているように、Ｃｈｉｌｉｍｂｉで実行されているように各ロードおよび格納のコマンドを実装せずに、ブロック６１２に示されたような決定点にコードが挿入される。制御フローのパスが実装されているので、パスプロファイル作成は、各分岐（すなわち、パス）が採用された頻度を決定することができる。このように、パスプロファイル作成は、各パス内に各ロードおよび格納のコマンドを実装するよりも、必要とするオーバーヘッドが少ないという利点を持つ。
【００２３】
上述の観点から、オブジェクトのフィールドへのアクセス速度を最大化するために、コピーによるガーベージコレクションのようなプロセスを通して、メモリ内のオブジェクトを再配列できることが望ましい。さらに、オブジェクトがコピーされる順序を決定するために、パスプロファイル作成のようなプロセスを用いて、オーバーヘッドを減らした状態で、オブジェクトのフィールドのアクセスの頻度と近さを解析できることが有益である。
【００２４】
【発明の概要】
本発明は、メモリからオブジェクトのフィールドのアクセスに関して得られた情報に従って、メモリ内のオブジェクトを再配列するための機構を生成する。例えば、これは、コピーによるガーベージコレクション中にフィールドのトラバースの順序を変更することによって実現できる。このように、メモリ内でオブジェクトを順序付けすることにより、後でオブジェクトをメモリからリトリーブする速度を最小化することができる。
【００２５】
本発明の一態様によると、メモリ内の複数のオブジェクトを再配列するための機構が作成される。コンピュータアプリケーション実行中の複数のオブジェクトに関する１つ以上のフィールドの互いに対してのメモリ内でのアクセス頻度が決定される。次いで、複数のオブジェクトに関する１つ以上のフィールドの互いに対してのメモリ内での決定されたアクセス頻度に従って、メモリ内で複数のオブジェクトを再配列するための機構が生成される。
【００２６】
本発明の一態様によると、生成された機構は、ガーベージコレクション中に複数のオブジェクトを再配列するためのガーベージコレクションコードを含む。ガーベージコレクションは、様々な方法で実装することができる。例えば、コピーによるガーベージコレクション、または、コピーによるガーベージコレクションの変形版を実行してもよい。
【００２７】
本発明のさらに別の態様によると、単一のクラスの全インスタンスにわたるフィールド参照の頻度と近さを示す情報から、メモリ内のオブジェクトを再配列するための機構を作成できる。一実施形態によると、ガーベージコレクション中にオブジェクトのフィールドが訪問（ＶＩＳＩＴ）される順序を変更するための機構が作成される。まず、クラスの全インスタンスに対して、フィールド参照情報が取得される。但し、フィールド参照情報は、互いにそのクラスのフィールドによって参照されるオブジェクトの参照の頻度と近さを示すものである。次いで、関連のフィールド参照情報からクラスフィールド順序が決定される。但し、クラスフィールド順序は、ガーベージコレクション中にそのクラスのフィールドがトラバースされる順序を特定するものである。このプロセスは、クラスフィールド順序が各対応するクラスに関連するように、複数のクラスに対して繰り返してもよい。
【００２８】
本発明の別の態様によると、ガーベージコレクションは、再配列機構を用いて実行される。一実施形態によると、オブジェクトが識別され、そのオブジェクトに関するクラスが確認される。オブジェクトのクラスに関するクラスフィールド順序が決定される。但し、クラスフィールド順序は、ガーベージコレクション中にそのクラスのフィールドがトラバースされる順序を特定するものである。次いで、オブジェクトのフィールドは、オブジェクトのクラスに関するクラスフィールド順序に従って、ガーベージコレクション（例えば、コピーによるガーベージコレクション）中に訪問される。例えば、訪問された各フィールドに対して、直接的もしくは間接的に指定された各オブジェクトをコピーしてもよい。
【００２９】
本発明は、メモリ内におけるオブジェクトのフィールドの参照の近さと頻度を示す情報に従って、オブジェクトを再配列することを可能とする。このように、これらのフィールドによって参照されるそれらのオブジェクトを、ガーベージコレクション中にメモリ内で再配列することができる。このように、互いに近い時間にアクセスされるオブジェクトを、メモリ内において近くに格納することができる。このことは、特に、キャッシュを実装するシステムにおいて有利である。何故なら、複数のオブジェクトが同じキャッシュラインにおいてリトリーブおよび格納される可能性が高くなるからである。したがって、互いに近くでアクセスされるオブジェクトをリトリーブする時間を、劇的に短くすることができる。
【００３０】
【発明の実施の形態】
以下の説明では、本発明の完全な理解を促すために、多くの詳細が具体的に示されている。しかしながら、本発明がこれらの具体的な詳細なしに実現できることは、当業者にとって明らかである。また、本発明を不必要に不明瞭化しないように、周知のプロセス動作の説明は省略してある。
【００３１】
本発明は、オブジェクトを、それらのオブジェクトのフィールドによって参照される他のオブジェクトが参照される頻度に従って、メモリ内で再配列することを可能とする。一実施形態によると、これは、与えられたクラスの全インスタンスにわたって、そのクラスのフィールドの参照（例えば、メモリアクセス）の頻度を生成することにより実現される。
【００３２】
さらに、一実施形態によると、パスプロファイル作成が用いられる。プロファイルは、例えばＪａｖａプログラムの解釈中に、短時間で取得され、次いで、実行時の間に少ないオーバーヘッドで、コンパイルされたコードから除去されることが可能である。このように、多くの時間とメモリを必要とせずに、オブジェクトを再配列することができる。
【００３３】
コピーによるガーベージコレクタは、様々な順序を選んでメモリ内のオブジェクトを配置することができる。一実施形態によると、アプリケーションによって近い時間にアクセスされるオブジェクトは、コピーによるガーベージコレクションプロセスによって、同じキャッシュラインにまとめられる。
【００３４】
本発明は、与えられたクラスの各オブジェクトに関するフィールド参照の頻度を調べずに、一実施形態に従って、与えられたクラスの全インスタンスにわたってフィールドアクセス（すなわち、フィールド参照）の頻度を一般化する。与えられたクラスのオブジェクトは、同じ目的に用いられることが多いため、これらのオブジェクトの振る舞いは、ほぼ同一であることが多い。そのため、単一のクラスの複数のインスタンスに関して実行されるメモリアクセスは、ほぼ同一であることが多い。このことについては、図７Ａないし７Ｃを参照して、さらに詳細に説明する。
【００３５】
図７Ａは、単一のクラス７００（Ａ）のインスタンスのセットの例を示すブロック図である。第１のインスタンス７０２（オブジェクトＡ１）と、第２のインスタンス７０４（オブジェクトＡ２）は両方とも、第１のフィールド７０６（ｘ）と、第２のフィールド７０８（ｙ）とを含む。このように、単一のクラスの複数のインスタンスは、同じフィールドを持つため、同じ種類のフィールドを持つ。
【００３６】
同じクラスのインスタンスは同じフィールドを持つため、これらのインスタンスは、同じ状況で用いられる可能性がある。例えば、これらのオブジェクトは、同じデータ構造で用いられることが多いため、これらのオブジェクトのフィールドに関するメモリアクセスは、ほぼ同じ頻度および順番で発生する。
【００３７】
そのようなデータ構造の一例は、ツリーデータ構造である。図７Ｂは、ツリーデータ構造における図７Ａのクラスインスタンスの使用例を示すブロック図である。図示されているように、ツリーデータ構造７１０は、ルートノード７１２と、２つの下位ノード７１４、７１６を含む。例えば、第１のインスタンス７０２（オブジェクトＡ１）が第１の下位ノード７１４であり、第２のインスタンス７０４（オブジェクトＡ２）が第２の下位ノード７１６であってよい。ツリーデータ構造の下位ノードに関するメモリアクセスは通常、ほぼ同様であるため、単一のクラスのインスタンスに関するメモリアクセスは、このインスタンス内のクラス全体にわたって生成されてもよい。
【００３８】
単一のクラスの複数のインスタンスが用いられるデータ構造の別の例は、リンクリストである。図７Ｃは、リンクリストデータ構造における図７Ａのクラスインスタンスの使用例を示すブロック図である。リンクリスト７１８は、３つのオブジェクトを含むよう示されている。すなわち、第１のオブジェクト７２０と、第２のオブジェクト７２２と、第３のオブジェクト７２４である。図示されているように、リンクリスト７１８内の第１のオブジェクト７２０は、クラスＡの第１のインスタンス７０２であってよい。同様に、リンクリスト７１８内の第２のオブジェクト７２２は、クラスＡの第２のインスタンス７０４であってよい。リンクリストの要素に関するメモリアクセスは通常、ほぼ同じ頻度で実行されるため、単一のクラスのインスタンスに関するメモリアクセスは、そのクラス全体にわたって一般化されてよい。
【００３９】
図８は、本発明の一実施形態に従って、互いに近い時間にアクセスされるフィールドを持つオブジェクトがメモリにおいて近くに格納されるように、メモリ内のオブジェクトを再配列するためのプロセスの概略を示すフローチャートである。コンピュータアプリケーションは、ブロック８０２で実行される。コンピュータアプリケーションが実行されると、メモリ内のフィールド参照の記録（例えば、フィールド参照のパスプロファイルまたはログ）が、ブロック８０４で生成される。次いで、ブロック８０６において、生成されたフィールド参照の記録（例えば、フィールド参照のパスプロファイルまたはログ）を用いて、オブジェクトがメモリ内で再配列される。例えば、オブジェクトは、コピーによるガーベージコレクションプロセスの間に再配列されてもよい。上述のプロセスが完了すると、オブジェクトは、互いに近い時間にアクセスされるフィールドを持つオブジェクトが、メモリ内において近くに格納されるように再配列される。それ故、これらのオブジェクトは、データがメモリからキャッシュにリトリーブされる際に、おそらく同じキャッシュラインに格納される。
【００４０】
オブジェクトは、様々なプロセスを用いて、ブロック８０６においてメモリに再配列されてもよい。一実施形態によると、図８のブロック８０４で記録されたフィールド参照の頻度と時間的な近さは、与えられたクラスの全インスタンスにわたって一般化される。図９は、図８のブロック８０６に示されているメモリ内のオブジェクトを再配列する方法の概略を示すフローチャートである。ブロック９０２では、各クラスに対して、互いに時間の近いフィールドの参照の、図８のブロック８０４で生成された記録における発生が、フィールド順序付け情報を生成するために、クラスの全インスタンスにわたって各フィールドに対してカウントされる。例えば、ある特定のクラス内でフィールド順序付け情報を生成するために収集できるデータは、各フィールドのアクセス回数と、そのフィールドが同じクラスの他のフィールドに対して参照したデータのアクセス間の時間と、同じクラスの他のフィールドに対するそのフィールドの参照の間の命令（もしくはメモリアクセス）の数と、およびクラスのフィールドがアクセスされる順序とを含んでよい。次いで、フィールドは、ブロック９０４において、フィールド順序付け情報に従ってソートされる。
【００４１】
ガーベージコレクション中にトラバースされるオブジェクトは、ツリーもしくは有向グラフのようなデータ構造に格納されてよい。例えば、オブジェクトは、深さ優先順でコピーされてよい。コピーによるコレクションでは、どのオブジェクトもしくはオブジェクトのセットを次にコピーするかを決定するための機構が必要である。換言すると、どのポインタが次にトラバースするかを決定するための機構が必要である。一実施形態によると、フィールド順序付け情報は、データ構造内でトラバースするのに適切なパスを決定するために用いられる。そのように、ガーベージコレクション中には、フィールドは、ブロック９０６において、ソートされた順序でスキャンされる。各フィールドが「スキャン」されると、フィールドによって（直接的もしくは間接的に）指定されたオブジェクトがコピーされる。換言すると、フィールドおよび／または関連のオブジェクトによって指定されたオブジェクトがコピーされる。したがって、ガーベージコレクション中に、各オブジェクトに対して、オブジェクトのクラスに関連するフィールド順序付け情報に従って、フィールドがトラバースされ、ソートされたフィールド各々によって（直接的もしくは間接的に）指定されたオブジェクトがコピーされる。例えば、オブジェクトのコピーは、深さ優先で実行されてよい。
【００４２】
上述のように、一実施形態によると、１つ以上のフィールドを持つオブジェクトに対して、それらのフィールドは、コピーによるガーベージコレクション中に適切なクラスに関するフィールド順序付け情報に従ってトラバースされる。図１０は、オブジェクトのセットの例と、図９のブロック９０６で実行されるコピーによるガーベージコレクション中のそれらのオブジェクトのメモリ内での配置とを示す図である。ガーベージコレクションに先立って、それらのオブジェクトは、メモリ１０００内に格納される。図示されているように、第１のオブジェクト１００２（Ａ）は、第１のフィールド１００４（ｙ）と、第２のフィールド１００６（ｘ）とを含む。第１のフィールド１００４（ｙ）は、第２のオブジェクト１００８（Ｂ）を参照し、第２のフィールド１００６は、第３のオブジェクト１０１０（Ｑ）を参照する。この例では、同じクラス内の他のフィールドに対するフィールド参照の総数が決定され、フィールド参照の総数によってフィールドがソートされると、第１のフィールド１００４（ｙ）によって参照されるデータは、第２のフィールド１００６（ｘ）によって参照されるデータよりも多くの回数参照されるように検索される。それ故、コピーによるガーベージコレクションが実行されると、第１のフィールド１００４（ｙ）によって参照されるオブジェクトが、最初にコピーされる。次いで、第２のフィールド１００６（ｘ）によって参照されるオブジェクトがコピーされる。したがって、図示されているように、第２のオブジェクト１００８（Ｂ）は、第１のオブジェクト１００２（Ａ）に最も近くなるように、最初にコピーされ、第３のオブジェクト１０１０（Ｑ）は、次にコピーされる。
【００４３】
オブジェクトを再配列する方法の概要は、図９および図１０に関連して上述した。図１１は、本発明の一実施形態に従って、メモリ内のオブジェクトを再配列する方法の詳細を示すフローチャートである。この実施形態によると、効率をよくするために、ログではなくパスプロファイルが用いられる。それ故、ブロック１１０２においては、各パスが実行時に採用される総回数を示す各パスのカウントを計算することを可能にするコードをコンピュータアプリケーションに挿入するために、コンピュータアプリケーションの制御フローが解析される。各パスに対して、（同じクラス内の他のフィールドに対する）各フィールドの参照の数が、ブロック１１０４において、各クラスに対して第１のテーブルを生成するために計算される。第１のテーブルの例については、図１２を参照して、以下で詳細に図示および説明する。ブロック１１０６において、実行時に採用された各パスのカウントは、次に、各クラスに対して第２のテーブルを生成するために、挿入されたコードを用いて計算される。第２のテーブルの例については、図１３を参照して、以下で詳細に図示および説明する。次いで、第１および第２のテーブルは、すべてのパスにわたって実行時の間に（同じクラス内の他のフィールドに対する）各フィールドのフィールド参照の数を取得するために、ブロック１１０８において結合される。第１および第２のテーブルの結合の結果については、図１４を参照して、以下で詳細に図示および説明する。次いで、フィールドは、ブロック１１１０において、クラスに対するすべてのパスにわたるフィールド参照の数によってクラスごとにソートされる。そのようなソートのプロセスの結果については、図１５を参照して、以下で詳細に図示および説明する。次いで、ソートされた順序でメモリ内のオブジェクトのフィールドをトラバースし、フィールドによって指定されたオブジェクトをコピーするガーベージコレクションコードが、ブロック１１１２において生成される。次いで、ガーベージコレクションは、ブロック１１１４において実行される。生成されたガーベージコレクションコード（もしくは別の機構）を用いてガーベージコレクションを実行する方法の詳細については、図１７を参照して説明する。
【００４４】
図１１に図示された実施形態に示されているように、ブロック１１０２〜１１０４は、コンパイル時１１１６の間に実行され、ブロック１１０６〜１１１４は、実行時に実行される。しかしながら、Ｊａｖａ(登録商標)では実行時にコンパイルが実行されることを認識することが重要である。それ故、上述の説明は例示的なものであり、工程は、個々のコンパイルおよび実行プロセス中に実行される必要はない。
【００４５】
図１１のブロック１１０４を参照して上述したように、（同じクラス内の他のフィールドに対する）各フィールドの参照（すなわち、メモリアクセス）の数は、各パスにわたって各クラスに対して第１のテーブルを生成するために計算される。図１２は、図１１のブロック１１０４で生成される第１のテーブルの例を示すブロック図である。図示されているように、ある特定のパス１２０２（例えば、パス５１１）に対して、（同じクラス内の他のフィールドに関する）ある特定のクラス内の各フィールド１２０６に対するそのパスに関するフィールド参照１２０４の数は、テーブルのフォーマットで提供される。例えば、クラスＡ内のフィールドｙ１２０８に対して、１２１０において、パス５１１に関する（フィールドｘについての）フィールド参照１２０８の数は２と示される。同様に、クラスＡ内のフィールドｘ１２１２に対して、パス５１１に関する（フィールドｙについての）フィールド参照１２１４の数は０と示される。フィールド参照の数は、フィールドの参照回数であるだけでなく、フィールド順序付け情報を含むことにも注意することが重要である。一例では、フィールド参照１２０４の数は、ある特定のフィールドが、同じクラス内の別のフィールド直後に参照された（すなわち、メモリからアクセスされた）回数を特定する。別の例では、フィールド参照１２０４の数は、ある特定のフィールドが、同じクラス内の別のフィールドの直前に参照された回数を特定する。他の例は、１つのフィールドに対して複数のカウントがコンパイルされるように、ある特定のフィールドが、同じクラス内の他のフィールド各々の前後に参照された回数をカウントする工程を含む。このように、フィールド順序付け情報が最終的にコンパイルされてもよい。
【００４６】
同様に、図１１のブロック１１０６を参照して上述しているように、各パスが実行時にトラバースされる回数がカウントされる。図１３は、図１１のブロック１１０６で生成される第２のテーブルの例を示すブロック図である。図示されているように、第２のテーブルは、各パス１３０２を識別し、識別されたパス１３０２がコンピュータアプリケーションの実行中にトラバースされる回数を示す関連のパスカウント１３０４を識別する。
【００４７】
図１２および図１３に示されたような第１および第２のテーブルが作成されると、図１１のブロック１１０８を参照して上述したように、テーブルが結合される。図１４は、図１２および図１３で示したようなテーブルから、図１１のブロック１１０８で生成される第３のテーブルの例を示すブロック図である。両テーブルが結合されると、ある特定のクラス内の各フィールド１４０２に対して、同じクラスの他のフィールドに対するフィールドの参照１４０４の数が決定される。例えば、図示されているように、クラスＡのフィールドｙに対して、クラスＡのフィールドｘに関するすべてのパスにわたる実行時のフィールド参照の数は５３である。換言すれば、この結果は、パスプロファイルではなくログが作成された場合に取得される結果と等しいはずである。同様に、図示されているように、クラスＡのフィールドｘに対して、クラスＡのフィールドｙに関するすべてのパスにわたる実行時のフィールド参照の数は５である。上述のように、フィールド参照の数は、同じクラスの他のフィールドに対する、関連のフィールドのいくつかの順序付け情報を示している。
【００４８】
各クラスのフィールドがソートされると、フィールド順序付け情報が、各クラスのフィールドに関連付けられる。図１５は、図１１のブロック１１１０で示したフィールドをソートする工程の結果の例を示すブロック図である。例えば、クラスＡ１５０２に対して、各フィールド１５０４がソートされる。結果として、フィールドｘ１５０６は、コピーによるガーベージコレクション中に最初にトラバースされ、フィールドｙ１５０８は、コピーによるガーベージコレクション中に２番目にトラバースされる。同様に、クラスＢ１５１０に対して、各フィールド１５１２がソートされる。結果として、フィールドｚ１５１４は、コピーによるガーベージコレクション中に最初にトラバースされ、フィールドｗ１５１６は、コピーによるガーベージコレクション中に２番目にトラバースされる。
【００４９】
ガーベージコレクションプロセス中にコピーされるオブジェクトは、ツリーもしくは有向グラフのようなデータ構造に格納されてよい。図１６は、ガーベージコレクションプロセス中にトラバースできるデータ構造の例を示す図である。図示されているように、ガーベージコレクションプロセスは、ルートノードまたはルートポインタ１６００から開始する。例えば、ルートポインタ１６００は、スタックから取得されてもよいし、静的変数であってもよい。ルートポインタは、第１のオブジェクト１６０２を指定する図示されているように、各オブジェクト１６０２、１６０４、１６０６、１６０８、および１６１０は、オブジェクトに関するクラスのフィールド順序に関連付けられた（すなわち、フィールド順序を指定する）オブジェクトヘッダを持つ。例えば、図示されているように、第１のオブジェクト１６０２は、クラスＡ１６１２に関連付けられている。各クラスの記述には、オフセットのリスト（図示せず）が通常、格納される。オフセット各々は、ある特定のフィールドに関連付けられている。さらに、各クラスは、関連のオブジェクトのフィールドが、コピーによるガーベージコレクションのようなガーベージコレクションプロセス中にトラバースされる順序を識別するクラスのフィールドに対する関連のフィールド順序を持つ。例えば、クラスＡ１６１２に対するフィールド順序１６１４は、フィールドｘがフィールドｙに先立ってトラバースされることを特定してもよい。同様に、図１６に示されているように、第４のオブジェクト１６０４および第３のオブジェクト１６０８は両方とも、クラスＢ１６１６に関連付けられている。クラスＢ１６１６は、フィールドｚがフィールドｗの前にトラバースされることを特定する関連のフィールド順序１６１８を持つ。それ故、第４のオブジェクト１６０４に関して、例えば、フィールドｚによって指定される第２のオブジェクト１６０６は、フィールドｗによって指定される第５のオブジェクト１６１０に先立ってトラバースされ、コピーされる。
【００５０】
図１１のブロック１１１４を参照して上述したように、ガーベージコレクションプロセスは、各関連のクラスに関するフィールド順序付け情報を用いて実行される。より詳細には、ガーベージコレクション（例えば、コピーによるコレクション）中にコピーされる各オブジェクトに対して、オブジェクトのクラスが決定され、オブジェクトのフィールドが、オブジェクトのクラスに関するフィールド順序付け情報に従ってコピーによるコレクション中に訪問される。図１７は、図１５に示されたようなソートプロセスの結果と、図１６に示されたようなオブジェクトのデータ構造とを用いて、図１１のブロック１１１４に示したようにガーベージコレクションを実行する一方法を示すフローチャートである。プロセスは、ブロック１７００で始まる。例えば、上述のように、プロセスはルートノードまたはルートポインタで開始してよい。次いで、現在のポインタ（例えば、ルートポインタ）によって指定されるオブジェクトが、ブロック１７０２において取得される。次いで、取得されたオブジェクトのクラスが、ブロック１７０４において決定される。例えば、オブジェクトのヘッダは、図１６に示すようにクラスを指定してもよい。それ故、オブジェクトヘッダから関連のクラスへポインタを追跡することにより、オブジェクトのクラスを確認してもよい。次に、クラス／オブジェクトが、トラバースされるいくつかの（または、さらなる）フィールドを持っているか否かが、ブロック１７０６において決定される。
【００５１】
オブジェクトが、トラバースすべきいくつかの、もしくは、いくつかの／さらなるフィールドを持っている場合、オブジェクトはブロック１７０８においてコピーされる。そうでない場合には、クラスフィールド順序付け情報で識別される次のフィールドが、ブロック１７１０において確認される。例えば、クラスの記述には通常、そのクラスのフィールドに関するオフセットのリストが含まれる。取得されたオブジェクトのフィールドの位置を特定するために、識別された次のフィールドのためのオフセットが、この記述から取得されてもよい。
【００５２】
次に、オブジェクトの認識されたフィールドが第２のオブジェクトを指定するか否かが、ブロック１７１２において決定される。そうである場合、ブロック１７１４において、第２のオブジェクトが（例えば、再帰的プロセスによって）取得される。オブジェクトの識別されたフィールドが第２のオブジェクトを指定しない場合、そのオブジェクトに関するさらなるフィールドに対して、プロセスはブロック１７０６を継続する。プロセスが再帰的に実行されると、トラバースされているデータ構造内の各オブジェクトは、最終的に、ブロック１７０８においてコピーされる。
【００５３】
本発明は、互いに近い時間にアクセスされるフィールドを持つオブジェクトが、近くに格納される可能性を最大化するように、メモリ内にオブジェクトを格納するために用いられてもよい。図１８は、メモリ内におけるオブジェクトの最適な構成を実現するための本発明の使用方法を示す図である。図示されているように、メインメモリ１８０２は、データのブロック１８０４内にオブジェクトを格納する。例えば、データの各ブロックは、３２バイトでよい。本発明を用いることにより、メインメモリ１８０２内のデータの単一のブロック１８０４に、第１のオブジェクト１８０６（Ａ）と、第２のオブジェクト１８０８（Ｂ）とを格納することができる。ＣＰＵ１８０８が、データのこのブロック１８０４をキャッシュ１８１０にコピーすると、オブジェクト１８０６および１８０８は、同じキャッシュライン１８１２（もしくは、１セットのキャッシュライン）に格納される。したがって、本発明を用いると、データの単一のブロックがメインメモリ１８０２からリトリーブされる際に、複数のオブジェクトが１つのキャッシュ内に同時に格納されることを可能にすることにより、互いに近い時間にアクセスされるフィールドを持つオブジェクトの効率的なアクセスを実現できる。
【００５４】
オブジェクトごとの局所性の情報を集めるのではなく、本発明は、クラスごとの局所性の情報を集めるため、オブジェクトとフィールドの種類を区別する。換言すると、本発明は、与えられたクラスのインスタンスが、おそらく同様のロード依存性を持つという観察を利用している。これは、一実施形態によると、パスプロファイル作成と、コピーによるコレクション中に、与えられたクラスのフィールドが訪問される順序を動的に変更するための機構とによって実現される。
【００５５】
本発明は、任意の適切なコンピュータシステムに実装してよい。図１９は、本発明を実装するのに適した代表的な汎用コンピュータシステム１９０２を示した図である。このコンピュータシステムは、任意の適切な形態をとってよい。例えば、コンピュータシステムは、デジタルテレビ受信機またはセットトップボックスと統合されていてもよい。
【００５６】
コンピュータシステム１９０２、すなわち具体的に言うとＣＰＵ１９０４は、当業者が理解するとおり、バーチャルマシンをサポートするよう構成されてもよい。コンピュータシステム１９０２は、一次記憶デバイス１９０６（通常、読み出し専用メモリすなわちＲＯＭ）と一次記憶デバイス１９０８（通常、ランダムアクセスメモリすなわちＲＡＭ）とを含むメモリデバイスに接続された任意の数のプロセッサ１９０４（中央処理装置すなわちＣＰＵとも呼ばれる）を備えている。当業者に周知のように、ＲＯＭは、ＣＰＵ１９０４にデータおよび命令を一方向的に転送するよう機能し、ＲＡＭは通常、データおよび命令を二方向的に転送するのに用いられる。両方の一次記憶デバイス１９０６および１９０８は、任意の適切なコンピュータ読み取り可能媒体を含んでいてよい。ＣＰＵ１９０４は、一般に、任意の数のプロセッサを含んでいて良い。
【００５７】
二次記憶媒体１９１０は、通常はマスメモリデバイスであり、二方向的にＣＰＵ１９０４に接続され、データ記憶容量を補っている。マスメモリデバイス１９１０は、コンピュータコード、データなどを含むプログラムを格納するのに用いることが可能なコンピュータ読み取り可能な媒体である。通常、マスメモリデバイス１９１０は、一般に一次記憶デバイス１９０６および１９０８よりも低速なハードディスクなどの記憶媒体である。
【００５８】
また、ＣＰＵ１９０４は、ビデオモニタ、トラックボール、マウス、キーボード、マイクロフォン、タッチセンシティブディスプレイ、トランスデューサカードリーダ、磁気もしくは紙テープリーダ、タブレット、スタイラス、音声もしくは手書き文字認識装置、もしくは、もちろん他のコンピュータのようなその他のよく知られた入力デバイス、を含むがそれらに限定されない１つ以上の入出力デバイス１９１２に接続されてもよい。最後に、ＣＰＵ１９０４は、１９１４に大まかに示されているネットワーク接続を用いて、コンピュータや、例えばインターネットネットワークもしくはイントラネットネットワークなどの通信ネットワークに随意的に接続されてもよい。このようなネットワーク接続により、ＣＰＵ１９０４は、上述した方法の段階を実行している間に、ネットワークから情報を受信したりネットワークに情報を出力したりすることができると予期される。このような情報は、ＣＰＵ１９０４を用いて実行される命令のシーケンスであることが多く、例えば搬送波で運ばれるコンピュータデータ信号の形で、ネットワークから受信したりネットワークに出力したりしてよい。
【００５９】
本明細書では、本発明の例示的な実施形態および用途を説明しているが、本発明の概念、範囲、および趣旨の範囲内で多くの変更を加えることが可能であり、これらの変更は、本出願を熟読した当業者にとって明らかである。例えば、本発明は、デジタルテレビ受信機に実装した例によって説明されている。しかしながら、本発明は、他の状況で用いられてもよい。さらに、本発明は、ＪＡＶＡ（登録商標）プラットフォームに実装した例によって説明されているが、別のプラットフォームに実装されてもよい。さらに、上述したプロセスのブロックは、単に例示的なものである。したがって、本発明の実装は、代替のデータ構造はもちろん、代替のプロセスのブロックを用いて実行されてもよい。したがって、上述した実施形態は、例示を目的としたものであって限定的ではなく、本発明は、本明細書で取り上げた項目に限定されず、添付した請求項の範囲および均等物の範囲内で変更することが可能である。
【図面の簡単な説明】
【図１Ａ】  従来のマーク・アンド・スイープによるガーベージコレクションのプロセスにおけるメモリ内のオブジェクトの配置を示すブロック図である。
【図１Ｂ】  従来のマーク・アンド・スイープによるガーベージコレクションプロセスの完了時における図１Ａのメモリを示すブロック図である。
【図２Ａ】  従来のコピーによるガーベージコレクションのプロセスにおけるメモリ内のオブジェクトを示すブロック図である。
【図２Ｂ】  従来のコピーによるガーベージコレクションプロセスの完了時における図２Ａのメモリを示すブロック図である。
【図３Ａ】  メモリ内のオブジェクトの構成例を示すブロック図である。
【図３Ｂ】  コピーによるガーベージコレクションの完了時における図３Ａのオブジェクトの１つの可能な構成を示すブロック図である。
【図３Ｃ】  コピーによるガーベージコレクションの完了時における図３Ａのオブジェクトの別の可能な構成を示すブロック図である。
【図４Ａ】  メモリおよび関連フィールドに格納されたオブジェクトのセットの例を示すブロック図である。
【図４Ｂ】  図４Ａのオブジェクトおよびフィールドにアクセスするコンピュータアプリケーションの実行中に作成できるメモリアクセスのログの例を示すブロック図である。
【図４Ｃ】  メモリ内のオブジェクトのアクセスと、図４Ｂに示されているメモリアクセスのログから作成できるこれらのメモリアクセスの一時的な関係とを示す一時的な参照グラフの例である。
【図５Ａ】  メモリおよび関連フィールドに格納されたオブジェクトのセットの例を示すブロック図である。
【図５Ｂ】  図５Ａのオブジェクトおよびフィールドにアクセスするコンピュータアプリケーションの実行中に作成できるメモリアクセスのログの例を示すブロック図である。
【図５Ｃ】  図５Ｂのログに示されたフィールド参照の間の一時的な関係を示す一時的な参照グラフの例である。
【図６Ａ】  コンピュータアプリケーションの実行中に可能なパスすべてを示すブロック図である。
【図６Ｂ】  図６Ａのコンピュータアプリケーションに関連する可能なパスを示すパスプロファイルの例を示す図である。
【図７Ａ】  単一のクラス（Ａ）のインスタンスのセットの例を示すブロック図である。
【図７Ｂ】  ツリーデータ構造における図７Ａのクラスインスタンスの使用例を示すブロック図である。
【図７Ｃ】  リンクリストデータ構造における図７Ａのクラスインスタンスの使用例を示すブロック図である。
【図８】  本発明の一実施形態に従って、互いに近い時間にアクセスされるフィールドを持つオブジェクトがメモリにおいて近くに格納されるように、メモリ内のオブジェクトを再配列するためのプロセスの概略を示すフローチャートである。
【図９】  図８のブロック８０６に示されているメモリ内のオブジェクトを再配列する方法の概略を示すフローチャートである。
【図１０】  図９のブロック９０６で実行されるコピーによるガーベージコレクションの完了時のオブジェクトのセットの例を示す図である。
【図１１】  本発明の一実施形態に従って、メモリ内のオブジェクトを再配列する方法の詳細を示すフローチャートである。
【図１２】  図１１のブロック１１０４で生成される第１のテーブルの例を示すブロック図である。
【図１３】  図１１のブロック１１０６で生成される第２のテーブルの例を示すブロック図である。
【図１４】  図１２および図１３で示したようなテーブルから、図１１のブロック１１０８で生成される第３のテーブルの例を示すブロック図である。
【図１５】  図１１のブロック１１１０で示したフィールドをソートする工程の結果の例を示すブロック図である。
【図１６】  ガーベージコレクションプロセス中にトラバースできるデータ構造の例を示す図である。
【図１７】  図１５に示されたようなソートプロセスの結果と、図１６に示されたようなオブジェクトのデータ構造とを用いて、図１１のブロック１１１４に示したようにガーベージコレクションを実行する一方法を示すフローチャートである。
【図１８】  キャッシュ内でのオブジェクトのアクセスを効率化するようなメモリ内におけるオブジェクトの格納を実現するための本発明の使用法を示す図である。
【図１９】  本発明の実装に適した代表的な汎用コンピュータシステムを示したブロック図である。
【符号の説明】
１０２…オブジェクト
１０４…オブジェクト
１０６…オブジェクト
１０８…オブジェクト
２００…メモリ
２０２…第１のオブジェクト
２０４…第２のオブジェクト
２０６…第３のオブジェクト
２０８…第４のオブジェクト
３００…メモリ
３０２…第１のオブジェクト
３０４…第２のオブジェクト
３０６…第３のオブジェクト
３０８…第４のオブジェクト
４００…第１のオブジェクト
４０２…第１のフィールド
４０４…第２のフィールド
４０６…第２のオブジェクト
４０８…第１のフィールド
４１０…第２のフィールド
４１２…第３のオブジェクト
４１４…フィールド
４１６…第４のオブジェクト
４１８…フィールド
４２０…メモリアクセスのログ
４２２…オブジェクト
４２６…エントリ
４２８…一時的な参照グラフ
５００…第１のオブジェクト
５０２…第１のフィールド
５０４…第２のフィールド
５０６…第３のフィールド
５０８…第２のオブジェクト
５１０…第１のフィールド
５１１…パス
５１２…第２のフィールド
５１４…メモリアクセスのログ
５１６…オブジェクト
５１８…フィールド
５２０…アクセスされたオブジェクト
５２２…アクセスされたフィールド
５２４…一時的な参照グラフ
６０２…条件ステートメント
７００…クラス
７０２…第１のインスタンス
７０４…第２のインスタンス
７０６…第１のフィールド
７０８…第２のフィールド
７１０…ツリーデータ構造
７１２…ルートノード
７１４…下位ノード
７１６…下位ノード
７１８…リンクリスト
７２０…第１のオブジェクト
７２２…第２のオブジェクト
７２４…第３のオブジェクト
１０００…メモリ
１００２…第１のオブジェクト
１００４…第１のフィールド
１００６…第２のフィールド
１００８…第２のオブジェクト
１０１０…第３のオブジェクト
１２０２…パス
１２０４…フィールド参照
１２０６…フィールド
１２０８…フィールド
１２１２…フィールド
１２１４…フィールド参照
１３０２…パス
１３０４…パスカウント
１４０２…フィールド
１４０４…フィールド参照
１５０２…クラス
１５０４…フィールド
１５０６…フィールド
１５０８…フィールド
１５１０…クラス
１５１２…フィールド
１５１４…フィールド
１５１６…フィールド
１６００…ルートポインタ
１６０２…第１のオブジェクト
１６０４…第４のオブジェクト
１６０６…第２のオブジェクト
１６０８…第３のオブジェクト
１６１０…第５のオブジェクト
１６１２…クラス
１６１４…フィールド順序
１６１６…クラス
１６１８…フィールド順序
１８０２…メインメモリ
１８０４…データのブロック
１８０６…オブジェクト
１８０８…オブジェクト
１８０８…ＣＰＵ
１８１０…キャッシュ
１８１２…キャッシュライン
１９０２…コンピュータシステム
１９０４…プロセッサ
１９０６…一次記憶デバイス
１９０８…一次記憶デバイス
１９１０…二次記憶媒体
１９１２…入出力デバイス
１９１４…ネットワーク
１９３０…コンピュータシステム
１９３２…ＣＰＵ
【図１Ａ】
0004812997.tif 000002
【図１Ｂ】
0004812997.tif 000003
【図２Ａ】
0004812997.tif 000004
【図２Ｂ】
0004812997.tif 000005
【図３Ａ】
0004812997.tif 000006
【図３Ｂ】
0004812997.tif 000007
【図３Ｃ】
0004812997.tif 000008
【図４Ａ】
0004812997.tif 000009
【図４Ｂ】
0004812997.tif 000010
【図４Ｃ】
0004812997.tif 000011
【図５Ａ】
0004812997.tif 000012
【図５Ｂ】
0004812997.tif 000013
【図５Ｃ】
0004812997.tif 000014
【図６Ａ】
0004812997.tif 000015
【図６Ｂ】
0004812997.tif 000016
【図７Ａ】
0004812997.tif 000017
【図７Ｂ】
0004812997.tif 000018
【図７Ｃ】
0004812997.tif 000019
【図８】
0004812997.tif 000020
【図９】
0004812997.tif 000021
【図１０】
0004812997.tif 000022
【図１１】
0004812997.tif 000023
【図１２】
0004812997.tif 000024
【図１３】
0004812997.tif 000025
【図１４】
0004812997.tif 000026
【図１５】
0004812997.tif 000027
【図１６】
0004812997.tif 000028
【図１７】
0004812997.tif 000029
【図１８】
0004812997.tif 000030
【図１９】
0004812997.tif 000031