(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、スタック・フレームにあるオブジェクトをヒープ・オブジェクト化する方法であって、
ヒープ領域にコピーすべきスタック・フレーム上の所定のオブジェクトのアドレスをワーキング・セットに格納するステップと、
前記所定のオブジェクトをヒープ領域にコピーして、そのヒープ領域上でのアドレスを保持するステップと、
スタック・フレームを順に辿り、前記ワーキング・セットに格納したアドレスを指示するポインタが見つかると、それが指示するアドレスを、前記ヒープ領域上でのアドレスに変換し、次のスタック・フレームに進むステップであって、当該アドレス変換において、変換したアドレスがスタック・フレーム上のオブジェクトのフィールドの値として格納されている場合は、そのオブジェクトのアドレスをワーキング・セットに格納するステップと、
スタック・フレームに前記ワーキング・セットに格納したアドレスを指示するポインタが見つからないことに応答して、処理を停止するステップを有する、
方法。
【請求項２】
請求項１の方法を実行するステップを含む、スタック圧縮方法。
【請求項３】
請求項１の方法を実行するステップを含む、ワーク・スティーリング方法。
【請求項４】
前記各ステップは、Java(R)仮想マシン上で実行される、請求項１の方法。
【請求項５】
コンピュータの処理により、スタック・フレームにあるオブジェクトをヒープ・オブジェクト化するプログラムであって、
前記コンピュータに、
ヒープ領域にコピーすべきスタック・フレーム上の所定のオブジェクトのアドレスをワーキング・セットに格納するステップと、
前記所定のオブジェクトをヒープ領域にコピーして、そのヒープ領域上でのアドレスを保持するステップと、
スタック・フレームを順に辿り、前記ワーキング・セットに格納したアドレスを指示するポインタが見つかると、それが指示するアドレスを、前記ヒープ領域上でのアドレスに変換し、次のスタック・フレームに進むステップであって、当該アドレス変換において、変換したアドレスがスタック・フレーム上のオブジェクトのフィールドの値として格納されている場合は、そのオブジェクトのアドレスをワーキング・セットに格納するステップと、
スタック・フレームに前記ワーキング・セットに格納したアドレスを指示するポインタが見つからないことに応答して、処理を停止するステップを実行させる、
プログラム。
【請求項６】
前記各ステップは、Java(R)仮想マシン上で実行される、請求項５のプログラム。
【請求項７】
コンピュータの処理により、スタック・フレームにあるオブジェクトをヒープ・オブジェクト化するシステムであって、
ヒープ領域にコピーすべきスタック・フレーム上の所定のオブジェクトのアドレスをワーキング・セットに格納する手段と、
前記所定のオブジェクトをヒープ領域にコピーして、そのヒープ領域上でのアドレスを保持する手段と、
スタック・フレームを順に辿り、前記ワーキング・セットに格納したアドレスを指示するポインタが見つかると、それが指示するアドレスを、前記ヒープ領域上でのアドレスに変換し、次のスタック・フレームに進む手段であって、当該アドレス変換において、変換したアドレスがスタック・フレーム上のオブジェクトのフィールドの値として格納されている場合は、そのオブジェクトのアドレスをワーキング・セットに格納する手段と、
スタック・フレームに前記ワーキング・セットに格納したアドレスを指示するポインタが見つからないことに応答して、処理を停止する手段を有する、
システム。
【請求項８】
前記各手段は、Java(R)仮想マシン上で実行される、請求項７のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、一般的には、コンピュータの処理系におけるオブジェクトの処理に関し、より詳しくは、スタックに割り当てられたオブジェクトをヒープにコピーする処理に関する。
【背景技術】
【０００２】
従来より、Java(R)などの処理系で、関数がコールされると、関数内で生成され、関数の処理が終了する時点で利用されなくなるオブジェクトは、スタックに積まれることがある。ところが、再帰呼び出しなどで関数が頻繁に呼び出されると、スタック領域が消費されて、スタック・オーバーフローが起こることがある。そこで、スタック領域上のオブジェクトをヒープにコピーして、スタック・フレームをずらすことによりスタックのサイズを圧縮する処理が行われる。
【０００３】
あるいは、Java(R)のFork-Joinフレームワークのワーク・スティーリング(work stealing)処理において、ある関数内で生成したタスク・オブジェクトを、他のスレッドが処理可能な状態にし、タスク・オブジェクトの処理が終了するまで必ず待機する場合、そのタスク・オブジェクトはスタック上に配置することが可能である。この際、タスク・オブジェクトを生成したスレッド以外のスレッドが、そのタスク・オブジェクトを処理する場合、処理系の安全性のために、タスク・オブジェクトを、スタックからヒープに一旦コピーするという処理が必要になる。
【０００４】
このような、スタックに割り当てられたオブジェクトをヒープに割り当てる処理を、ヒープ・オブジェクト化(heapification)と呼ぶことにする。また、以下では便宜上、スタックに割り当てられたオブジェクト(stack-allocated object)をスタック・オブジェクト、ヒープに割り当てられたオブジェクトを、ヒープ・オブジェクト(heapified object)と呼ぶことにする。
【０００５】
ところが、その際、単にスタックからヒープにオブジェクトをコピーしただけでは、処理は完結しない。スタック・オブジェクトが、コピーされたヒープ・オブジェクトをきちんと指すようにしなくてはならないからである。そのための一連の処理を、図１〜図３を参照して説明する。
【０００６】
図１には、コンピュータのメモリにおける、スタック１０２と、ヒープ１０４が示されている。スタック１０２は、それぞれが関数呼び出しに対応するスタック・フレーム１０２ａ、１０２ｂ等からなる。
【０００７】
図示されているように、スタック・フレーム１０２ａには、スタック・オブジェクト１０６と、ローカル変数１０８が配置され、スタック・フレーム１０２ｂには、フィールド変数１１２ａをもつスタック・オブジェクト１１２が配置されている。
【０００８】
図１のようなスタック・オブジェクトと変数の配置は、例えば、次のようなコードで、fooの処理を要求した際に、barを処理中の状態に対応する。
class S {
}
class T {
S a;
}
void foo() {
S a = new S();
bar(a);
}
void bar(S a) {
T b = new T();
b.a = a;
...
}
【０００９】
さて、Java(R)仮想マシンまたはオペレーティング・システムに機能により、図２に示すように、スタック・オブジェクト１０６が、ヒープ１０４にコピーされ、ヒープ・オブジェクト２０２になったとする。
【００１０】
すると、ヒープ・オブジェクト２０２のアドレスをＢとすると、このヒープ・オブジェクト化により、スタック・フレームにおいて今までスタック・オブジェクト１０６を指していたアドレスＡを、図３に示すように、アドレスＢに書き換える必要がある。
【００１１】
ところが、このためには、Java(R)仮想マシンまたはオペレーティング・システムは、スタック・フレームを順に走査し、元のスタック・オブジェクト１０６のアドレスＡを指し示す変数を、ヒープ・オブジェクト２０２のアドレスＢを指し示すように書き換える処理が必要となる。しかし、どのスタック・フレームに、ヒープ・オブジェクト化する前のスタック・オブジェクトのアドレスを指し示す変数があるか分からないので、すべてのスタック・オブジェクトを走査する必要があり、その処理に時間がかかっていた。
【００１２】
Erik Corry,  "Optimistic stack allocation for java-like languages",  International Symposium on Memory Management archive, Proceedings of the 5th international symposium on Memory management table of contents, Ottawa, Ontario, Canada, Pages: 162 - 173, 2006に開示されている技術は、一旦オブジェクトをスタックに割当て、エスケープした時点でヒープにオブジェクトをコピーする。この技術は、メソッド・フレーム単位でなく、ループ単位でスタックを構成し、オブジェクトを割り当てた領域より後に呼ばれたループの領域を走査し、参照の張り直しを行っている。
【００１３】
Kevin Cleereman, Michelle Cheatham, "Runtime Support of Speculative Optimization for Offline Escape Analysis", ( http://knoesis.wright.edu/library/publications/SERP-07-EscapeAnalysis.pdf )に開示されている技術においても、オブジェクトが割り当てられたスタック・フレームより上のフレームのみが走査される。
【００１４】
しかし、これらの従来技術は、スタック・フレームの走査にかかる時間を削減する技法を開示するものではない。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Erik Corry,  "Optimistic stack allocation for java-like languages",  International Symposium on Memory Management archive, Proceedings of the 5th international symposium on Memory management table of contents, Ottawa, Ontario, Canada, Pages: 162 - 173, 2006
【非特許文献２】Kevin Cleereman, Michelle Cheatham, "Runtime Support of Speculative Optimization for Offline Escape Analysis", ( http://knoesis.wright.edu/library/publications/SERP-07-EscapeAnalysis.pdf )
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従って、本発明の目的は、スタックに割り当てられたオブジェクトをヒープに割り当てる際に必要となる、アドレス書き換えのためのスタック走査にかかる時間を低減する技法を提供することにある。
【課題を解決するための手段】
【００１７】
この発明は、上記課題を解決するためになされたものであり、この発明の機能を備えた処理系はまず、ヒープ・オブジェクト化されたスタック・オブジェクトのアドレスＡを、好適にはヒープに確保したメモリ領域である、ワーキング・セットに追加して、スタックを走査する。
【００１８】
処理系は、アドレスＡを割り当てるスタック・フレームを検出して、それを現在のスタック・フレームとする。そして、現在のスタック・フレーム中に、ワーキング・セットに追加されたアドレスを指し示す変数がみつかると、それを、対応するヒープ・オブジェクトのアドレスに書き換える。
【００１９】
現在のスタック・フレーム中のスタック・オブジェクトのフィールドが、ワーキング・セットに含まれているアドレスを指し示すなら、処理系は、そのスタック・オブジェクトのアドレスを、ワーキング・セットに追加する。
【００２０】
現在見ているスタック・フレームが、ワーキング・セットに含まれているアドレスに対するポインタを含むなら、次のスタック・フレームに進む。
【００２１】
現在見ているスタック・フレームが、ワーキング・セットに含まれているアドレスに対するポインタを含まないなら、処理系は、そこでスタックの走査を終了する。
【００２２】
ここでスタックの走査を打ち切るのは、現在見ているスタック・フレームが、ワーキング・セットに含まれているアドレスに対するポインタを含まないなら、それ以降のスタック・フレームが、ワーキング・セットに含まれているアドレスに対するポインタを含まないので最早調べる必要がないという、本発明の知見に基づく処理である。
【発明の効果】
【００２３】
この発明によれば、ヒープ・オブジェクト化処理において、ポインタの書き換えを行うためのスタック・フレームの走査において、全てのスタック・フレームを走査することなく、途中で走査を打ち切ることが可能となるので、ヒープ・オブジェクト化処理を高速化することができる。
【図面の簡単な説明】
【００２４】
【図１】ヒープ・オブジェクト化処理の様子を模式的に示す図である。
【図２】ヒープ・オブジェクト化処理の様子を模式的に示す図である。
【図３】ヒープ・オブジェクト化処理の様子を模式的に示す図である。
【図４】本発明を実施するためのハードウェアの一例のブロック図である。
【図５】処理環境の機能ブロックのレイヤを示す図である。
【図６】本発明のヒープ・オブジェクト化処理の処理のフローチャートを示す図である。
【図７】本発明のヒープ・オブジェクト化処理の処理のフローチャートを示す図である。
【図８】本発明に従うヒープ・オブジェクト化処理の様子を模式的に示す図である。
【図９】本発明に従うヒープ・オブジェクト化処理の様子を模式的に示す図である。
【発明を実施するための形態】
【００２５】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２６】
図４を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図４において、システム・バス４０２には、ＣＰＵ４０４と、主記憶（ＲＡＭ）４０６と、ハードディスク・ドライブ（ＨＤＤ）４０８と、キーボード４１０と、マウス４１２と、ディスプレイ４１４が接続されている。ＣＰＵ４０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(商標)4、インテル社のCore(商標) 2 DUO、Xeon(商標)、AMD社のAthlon(商標)などを使用することができる。主記憶４０６は、好適には、２ＧＢ以上の容量、より好ましくは、４ＧＢ以上の容量をもつものである。
【００２７】
ハードディスク・ドライブ４０８には、オペレーティング・システム５０２（図５）が、格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows XP(商標)、Windows(商標)2003サーバ、アップルコンピュータのMac OS(商標)などの、ＣＰＵ４０４に適合する任意のものでよい。
【００２８】
ハードディスク・ドライブ４０８にはまた、好適にはApacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存され、システムの起動時に、主記憶４０６にロードされる。
【００２９】
ハードディスク・ドライブ４０８にはさらに、Java(R)仮想マシン（ＪＶＭ）５０４（図５）を実現するためのJava(R) Runtime Environmentプログラムが保存され、システムの起動時に、主記憶４０６にロードされる。ＪＶＭ５０４は、本発明に係るヒープ・オブジェクト化の機能を実装する。
【００３０】
ハードディスク・ドライブ４０８にはさらに、アプリケーション・プログラムのバイトコード５０６（図５）が保存されている。
【００３１】
キーボード４１０及びマウス４１２は、オペレーティング・システム５０２が提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ４１４に表示されたアイコン、タスクバー、ウインドウなどのグラフィック・オブジェクトを操作するために使用される。
【００３２】
ディスプレイ４１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。
【００３３】
通信インターフェース４１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース４１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、あるいは処理結果を、クライアント・コンピュータ（図示しない）に返す。
【００３４】
図５は、ソフトウェアのレイヤを示す図である。図５において、最下層は、オペレーティング・システム５０２である。
【００３５】
オペレーティング・システム５０２の上では、オペレーティング・システム５０２に適合するＪＶＭ５０４が動作する。
【００３６】
ＪＶＭ５０４上では、アプリケーション５０６のバイトコードが動作する。アプリケーション５０６が動作する間に、ＪＶＭ５０４はシステムの状態を監視し、スタックのサイズ圧縮、あるいはワーク・スティーリングの処理を行い、それに伴って、ヒープ・オブジェクト化処理を実行する。
【００３７】
次に、図６と図７のフローチャート、及び図８と図９の例を参照して、ＪＶＭ５０４によるヒープ・オブジェクト化処理を、より詳細に説明する。ステップ６０２では、ＪＶＭ５０４は、ヒープ・オブジェクト化するスタック・オブジェクト８０６のアドレスＡをヒープ８０４にコピーし、コピー先のアドレスＢを特定するとともに、アドレスＢに、スタック・オブジェクト８０６をコピーする。コピーした結果は、ヒープ・オブジェクト８０８となる。
【００３８】
ステップ６０４では、ＪＶＭ５０４は、経由到達可能オブジェクト集合（ワーキング・セット）ＷＳに、アドレスＡを入れる。ワーキング・セットＷＳは、好適には、図示しないが、ヒープ８０２に確保した領域である。ワーキング・セットＷＳは、好適には、アドレスを格納する配列からなる。
【００３９】
ステップ６０６では、ＪＶＭ５０４は、アドレスＡが指定されたスタック・フレームを検索した結果見つかったスタック・フレームfcurrentを、fstartとする。
【００４０】
ここで、図７のフローチャートを参照して、ステップ６０６での処理をより詳細に説明する。図７のステップ７０２において、ＪＶＭ５０４は、ヒープ・オブジェクト化するスタック・オブジェクト８０６のアドレスＡを指定する。
【００４１】
ステップ７０４では、ＪＶＭ５０４は、アドレスＡが割り当てられたスタックＳを特定する。ここでは、スタックＳは、図８に示すスタック８０２である。
【００４２】
ステップ７０６では、ＪＶＭ５０４は、スタックＳ内で最初に呼ばれた関数に対応する関数フレームを特定し、それをfcurrentとする。ここでは、図８に示すスタック・フレーム８０２ａが、その関数フレームであるとする。
【００４３】
ステップ７０８では、ＪＶＭ５０４は、fcurrent内にアドレスＡが含まれるかどうか判断する。図８の例では、スタック・フレーム８０２ａにアドレスＡが含まれていないので、ステップ７１０に進み、fcurrentの次に呼ばれた関数に対応する関数フレーム８０２ｂを次のfcurrentとする。
【００４４】
このようにステップ７０８とステップ７１０を繰り返すことにより、スタック・フレーム８０２ａ→スタック・フレーム８０２ｂ→スタック・フレーム８０２ｃ→スタック・フレーム８０２ｄと順に走査し、スタック・フレーム８０２ｄに到達した時点で、スタック・フレーム８０２ｄにアドレスＡを指し示す変数が含まれているので、ステップ７０８での判断が肯定的になり、ステップ７１２に移行して、fcurrentをfstartとして、ステップ６０６に戻る。
【００４５】
こうして図６のフローチャートに戻って、ＪＶＭ５０４は次に、ステップ６０８で、スタック・フレームfcurrent内に、ワーキング・セットＷＳ内のアドレスを指すポインタが存在するかどうか判断する。
【００４６】
図８の例において、目下fcurrentは、スタック・フレーム８０２ｄなので、ワーキング・セットＷＳ内のアドレスＡを指すポインタが存在し、よって、ステップ６０８の判断が肯定的になり、ステップ６１０でfcurrent内のアドレスＡを指す変数（ポインタ）を、図８に示すヒープ・オブジェクト８０８を指すアドレスＢに書き換える。それは、スタック・フレーム８０２ｄでは、ローカル変数８０８である。ステップ６１２では、ＪＶＭ５０４は、ワーキング・セットＷＳ内のアドレスを指すポインタを含むスタック・オブジェクトがもし現在のスタック・フレーム８０２ｄにあれば、そのようなスタック・オブジェクトのアドレスをワーキング・セットＷＳに追加するが、スタック・フレーム８０２ａにはそのようなスタック・オブジェクトのアドレスはないので、ステップ６１２は実行されない。ステップ６１４では、fcurrentの次に呼ばれた関数に対する関数フレームをfcurrentとする。すなわち、図８では、スタック・フレーム８０２ｄの次のスタック・フレーム８０２ｅがfcurrentとなる。
【００４７】
fcurrentであるスタック・フレーム８０２ｅにおいて、ワーキング・セットＷＳ内のアドレスＡを指すポインタが存在し、よって、ステップ６０８の判断が肯定的になり、ステップ６１０でfcurrent内のアドレスＡを指すポインタを、図８に示すヒープ・オブジェクト８０８を指すアドレスＢに書き換える。スタック・フレーム８０２ｅでは、アドレスＡを指すのは、ローカル変数８１２及び、スタック・オブジェクト８１４のフィールド８１４ａであって、それらは、図９に示すように、Ｂに書き換えられる。ステップ６１２では、ＪＶＭ５０４は、ワーキング・セットＷＳ内のアドレスを指すポインタを含むスタック・オブジェクト８１４のアドレスＣをワーキング・セットＷＳに追加する。ステップ６１４では、fcurrentの次に呼ばれた関数に対する関数フレームをfcurrentとする。すなわち、図９において、スタック・フレーム８０２ｅの次のスタック・フレーム８０２ｆがfcurrentとなる。
【００４８】
そこで、ステップ６０８での判断に戻ったとき、ワーキング・セットＷＳに含まれているアドレスは、ＡとＣであるが、スタック・フレーム８０２ｆには、Ｅを指すローカル変数８１８と、Ｄを指すローカル変数８１６があるだけで、Ａを指すローカル変数もＣを指すローカル変数もないので、ステップ６０８の判断が否定的になり、ステップ６１６で、ＪＶＭ５０４は、スタック・フレームの探索を終了する。
【００４９】
上記の処理を、下記の関数呼び出しのソースコードの例で説明すると、ここで、下記の各々の関数呼び出しが、１つのスタック・フレームに対応する。
void foo() {
//ここでアドレスAにスタック割当てしたとする。
Object x = new Object();
bar(x);
}
void bar(Object y) {
System.out.println(y);
barbar();
}
void barbar() {
barbarbar()
}
void barbarbar() {
...
}
【００５０】
上記のコードで、bar(Object)のフレームは、スタックに割当てされたオブジェクトにアクセスすることができるが、barbar()のフレームからは、アクセスすることができない。
【００５１】
barbarbar()を実行中にヒープ・オブジェクト化を行う場合、foo()、bar(Object)の中では、スタック割当てしたオブジェクトへのポインタ（下の例だとxおよびy）を書き換える必要がある。
【００５２】
しかし、barbar()にはAへのポインタがないので、barbarbar()にも確実にAへのポインタがない。つまり、探索は、barbar()までで止めてもよい、ということが保証される。
【００５３】
以上、ＪＶＭ上で、Java(R)バイトコードが実行される場合のヒープ・オブジェクト化処理について説明したが、ＪＩＴコンパイラによって生成されたコードは、本発明に係るヒープ・オブジェクト化を実行するＪＶＭの関数を呼び出すようにすることで、本発明に係る処理を利用することができる。
【００５４】
また、ＪＶＭなどの特定のプラットフォームに関連して本発明の実施例を説明してきたが、本発明はこのような特定のプラットフォームでの実施に限定されず、任意のコンピュータのプラットフォームで実施可能である。
【００５５】
さらに、ヒープ・オブジェクト化処理は、ＪＶＭでなく、オペレーティング・システムが実行するようにしてもよい。
【符号の説明】
【００５６】
１０２          スタック
１０４          ヒープ
１０６、１１２  スタック・オブジェクト
２０２          ヒープ・オブジェクト
４０４          ＣＰＵ
４０６          主記憶
４０８  ハードディスク・ドライブ
５０２          オペレーティング・システム
５０４          ＪＶＭ
８０２          スタック
８０４          ヒープ
８０６、８１４  スタック・オブジェクト
８０８          ヒープ・オブジェクト
【図１】
0005379779.tif 000002
【図２】
0005379779.tif 000003
【図３】
0005379779.tif 000004
【図４】
0005379779.tif 000005
【図５】
0005379779.tif 000006
【図６】
0005379779.tif 000007
【図７】
0005379779.tif 000008
【図８】
0005379779.tif 000009
【図９】
0005379779.tif 000010