JP5871589B2 - 情報処理装置、配列の初期サイズ調整プログラム及び方法 - Google Patents

Description

本発明は、配列の初期サイズを調整する技術に関し、より詳細には、配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法に関する。

従来、配列の適切なサイズが前もって分からない場合、最初は小さいサイズの配列を割り付け、必要に応じて拡張したサイズの配列を割り付けるプログラミングパターン（以下、「配列拡張パターン」という）が利用されている。配列拡張パターンの一例を図１３に示す。図１３に示すStringBuilderクラスでは、最初、コンストラクタにより要素数１６の配列char[]が割り付けられる（図１３の(a)を参照）。そして、メソッドappendにより配列char[]の要素に値が設定される際に、if文で配列の拡張が必要であるか否かが判定され、if文の条件が真となる場合に倍のサイズの配列newchar[]が新たに割り付けられる（図１３の(ｂ)を参照）。新たに割り付けた配列newchar[]の各要素には元の配列char[]の各要素の値がコピーされる。

しかしながら上記プログラミングパターンの利用には、配列の初期サイズはしばしば大き過ぎたり小さ過ぎたりするため実行に無駄が生じるという問題がある。特に配列の寿命が短く頻繁に割り付けられる場合には、ゼロ初期化やコピーのオーバーヘッドが大きい。

可変長オブジェクトの初期サイズの選択方法に関する従来技術として非特許文献１が存在する。非特許文献１は、可変長オブジェクトとしてコレクションオブジェクトに着目し、以下の初期サイズ選択方法を開示する。１．コレクションオブジェクトを割り付けるときに呼び出しコンテキストを取得してこれを割り付けたコレクションオブジェクトのオブジェクト情報構造体に記録する。２．コレクションオブジェクトに対するメソッド呼び出しの種別や回数を対応するオブジェクト情報構造体に記録する。３．コレクションオブジェクトを破棄する際に、対応するオブジェクト情報構造体の記録を割付呼び出しコンテキスト毎の情報構造体に集計する。４．プログラム実行終了後、集計結果に基づきコレクションオブジェクトの適切な初期サイズをプログラマに提案する。

そこで上記非特許文献１の技術を配列の初期サイズの決定処理に適用することを考える。すると、図１３に示す(ａ) 、(ｂ)の２箇所で割り付けられた配列へのアクセス情報及び配列の割付呼び出しコンテキスト情報を、それぞれ対応するオブジェクト情報構造体に記録し、記録した情報を割付呼び出しコンテキスト毎の情報構造体に集計することで、(ａ) 、(ｂ)の２箇所でそれぞれ割り付けられる配列について適切な初期サイズをプログラマに提案することが可能となる。しかしこの場合、プロファイル情報は割付呼び出しコンテキスト単位でしかまとめることができないので、 (ｂ)で割り付けられた配列のプロファイル情報を（ａ）で割り付けられた配列の割付呼び出しコンテキストにフィードバックすることができない。結果、(ａ) 、(ｂ)の２箇所で大きすぎるサイズの配列を割り付けることはなくなるが、配列の拡張処理をなくしたり、その回数を減らしたりすることはできない。

以下、本発明の先行技術調査において見つかった他の文献について説明する。

特許文献１は、インライン割付元の可変長インスタンスの大きさを、実行プロファイルを使うなどの方法により予測し、例えば、配列の大きさを４と予測した場合に、実行時に定まった配列の長さが４以下である場合には配列をインライン割付け先のインスタンスの中にインライン割付けし、４を超える場合には、配列をインライン割付け先のインスタンスとは別個に割付ける技術を開示する。しかしながら特許文献１の技術は、各割り付け場所で割り付けられる可変長オブジェクトのサイズをプロファイルしており、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたか否かについては全く考慮に入れておらず、従って、特許文献１の技術は配列拡張パターンを最適化することはできない。

特許文献２は、プログラム実行時にメモリ容量変更の必要がある場合、環境設定ファイルを参照し、この環境設定ファイルの最大配列長、あるいは最小配列長と実行マシンの実メモリにより、プログラム中で必要とする配列長の最適な値を算出する手段と、次にソースプログラム中の配列長を変更し、再コンパイルして、実行する手段とを備えたことを特徴とする配列領域確保装置を開示する。しかしながら、
特許文献２の技術は、プログラム中で割り付ける配列のサイズを、実行するマシンが持つメモリの大きさに応じて調整するものであり、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたかに応じて調整するものではなく、従って、特許文献２の技術は配列拡張パターンを最適化することはできない。

特許文献３は、配列のデータ領域の各行を指し示すデータ領域へのポインタを含むデータ領域へのポインタ配列の先頭を指すポインタ配列へのポインタを格納するメモリ管理テーブルおよび前記メモリ管理テーブルの大きさをそれぞれプライベートなメンバ変数として実装し、かつ、前記メモリ管理テーブルを初期化する初期化関数コンストラクタ、配列の領域の確保・割り当てを行うメモリ確保関数、領域の解放を行うためのメモリ解放関数、前記データ領域および前記データ領域へのポインタ配列を前記メモリ解放関数を使用して解放する解放関数デストラクタをそれぞれパブリックなメンバ関数として実装する、第１のＣ＋＋言語における配列の領域の動的確保・解放方法を開示する。しかしながら、特許文献３の技術は、多次元配列で高次元のサイズをコンパイル時定数でなく実行時変数とするためのものであり、かかる手法では割り付けた配列が実行時に拡張されることはない。そのため、特許文献３の技術は配列拡張パターンを最適化することはできない。

特開２００３−０２７１３９３号公報 特開１９９３−０２０４６１６号公報 特開２０００−００６６９００号公報

O. Shacham, M. Vechev, E. Yahav,"Chameleon: Adaptive Selection of Collections.", PLDI '09 ACM SIGPLAN Conference on Programming Language Design and Implementation Dublin, Ireland, 2009, PP.408-418

この発明は、上記の問題点を解決するためになされたものであって、配列拡張パターンにおいて配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法を提供することを目的とする。

本発明は、上記課題を解決するために、以下の特徴を有する配列の初期サイズを動的に調整する調整プログラムを提供する。該プログラムはコンピュータに、（ａ）実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、（ｂ）前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、（ｃ）前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、（ｄ）各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、（ｅ）前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップとを実行させる。

好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ（ｅ）は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む。

また好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ（ｅ）は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む。

また好ましくは、配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられる。そしてステップ（ｂ）は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む。

また好ましくは、ステップ（ｄ）の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる。

以上、配列の初期サイズを動的に調整する調整プログラムとして本発明を説明した。しかし、本発明は、上記調整プログラムをインストールしたコンピュータにおいて実行される、配列の初期サイズを動的に調整する調整方法として把握することもできる。また、本発明は、上記調整プログラムをインストールすることにより実現される、配列の初期サイズを動的に調整するための情報処理装置（以下、「調整装置」という）として把握することもできる。

本発明では、サイズ拡張後の配列のプロファイル情報を記録する際に、これをサイズ拡張後の配列の割付呼び出しコンテキストではなく、サイズ拡張前の元の配列の割付呼び出しコンテキストに関連付ける。結果、サイズ拡張後の配列についてのプロファイル情報を、拡張前の元の配列の割付呼び出しコンテキストにフィードバックすることが可能となり、拡張処理を減らすことのできる配列の適切な初期サイズを実行環境において動的に決定することが可能となった。本発明のその他の効果については、各実施の形態の記載から理解される。

本発明の実施形態に係るコンピュータ５０のハードウェア構成の一例を示す。 本発明の実施形態に係るコンピュータ５０のソフトウェア構成の一例を示す。 本発明の実施形態に係る調整装置２００の機能構成を示す。 標準ライブラリの一部として提供される新ＡＰＩの一例を示す。 getCharArrayOfBestSize()の実行時コンパイルされたコードの一例を示す。 extendCharArray ()の実行時コンパイルされたコードの一例を示す。 図３Ａに示す新ＡＰＩを用いたStringBuilderの一例を示す。 図４に示すStringBuilderを用いて配列を生成するプログラムの一例を示す。 図５Ａの３行目で割り付けられる配列についてのプロファイル結果の一例を示す。 図５Ｂに示すプロファイル結果を参照してインライン展開されたコードを示す。 図４に示すStringBuilderを用いて配列を生成するプログラムの他の例を示す。 図６Ａの３行目で割り付けられる配列についてのプロファイル結果の一例を示す。 図６Ｂに示すプロファイル結果を参照してインライン展開されたコードを示す。 本実施形態に係る調整装置２００の動作フローの一例を示す。 図７に示すステップ７４０の初期化部２１０による処理の詳細な動作フローの一例を示す。 図７に示すステップ７２０のメモリ管理部１２５の詳細な動作フローの一例を示す。 図７に示すステップ７５０のプロファイラ１３０による処理の詳細な動作フローの一例を示す。 図７に示すステップ７６０の動的コンパイラ１３５による他の処理の詳細な動作フローの一例を示す。 速度向上率に関する実験結果を示す。 従来の配列拡張パターンを示すプログラムの一例を示す。 アノテーションで割付場所を指定するＡＰＩを用いたプログラムの一例を示す。 ネイティブライブラリとして提供される新たなＡＰＩの一例を示す。

以下、本発明の実施形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。

図１は、本発明の実施形態による情報処理装置としてのコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメイン・メモリ４を含んでいる。ＣＰＵ１は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＣｏｒｅ ｉ（商標）シリーズ、Ｃｏｒｅ ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＰｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ又はＳｅｍｐｒｏｎ（商標）が使用されうる。

またハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。

これら記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システム、Ｊ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、その他のプログラム及びデータが、メイン・メモリ４にロード可能に記憶されている。更に、上記記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ１に命令を与え、本発明を実施するためのコンピュータ・プログラムを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を本発明の実施形態による調整装置２００として機能させる調整プログラムやデータを記録することができる。

上記調整プログラムは、配列生成モジュールと、拡張配列生成モジュールと、マーク設定モジュールと、初期化モジュールと、呼び出し設定モジュールと、集計モジュールと、プロファイル情報収集モジュールと、インライン展開モジュールと、サイズ決定モジュールと、コード書き換えモジュールとを含む。これらプログラム及びモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、各々後述する配列生成部２０２と、拡張配列生成部２０３、設定部２０５と、初期化部２１０と、呼び出し設定部２１５と、集計２２０と、プロファイル情報収集部２２５と、インライン展開部２３５と、サイズ決定部２４０と、コード書き換え部２４５としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。

コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。

以上の説明により、コンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。

図１Ｂは、本発明を実現するソフトウェアの構成を示すブロック図である。同図において、オペレーティング・システム１０５は、ＣＰＵやメモリを資源として管理し、時分割によるマルチスレッドの機能を実現する。仮想マシン１１０は、アプリケーション１４０とオペレーティング・システム１０５とのインタフェースを行うソフトウェアであり、アプリケーション１４０から見て仮想マシン以下の階層全体を例えばＪａｖａ（登録商標）仮想マシン（Virtual Machine）として作用させる。仮想マシン１１０は、プログラムがバイトコード等の中間コードで与えられるときこれを解釈する実行部（インタープリタ）１２０と、その解釈に応じて呼び出されるプロファイラ１３０と、メモリ管理部１２５とを含む。また、仮想マシン１１０はＪＩＴコンパイラ等の動的コンパイラ１３５を含み、バイトコードを実行時に動的に機械語にコンパイルしてネイティブコードを生成し、プログラムの実行を高速化する。なお、上記中間コードはＡＰＩの記述を含みうる。実行部１２０は中間コード内にＡＰＩの記述を検出すると、ライブラリからそのＡＰＩの機能を呼び出して実行する。

ところで本発明は、配列拡張パターンにおける配列の初期サイズをプロファイル結果に基づいて実行時に動的に調整することを目的とするが、配列の初期サイズをコンピュータの演算処理により勝手に変更するとプログラムの意味が変ってしまう場合がある。そのため、配列の初期サイズを変更してもプログラムの意味が変らない箇所を見つけ、当該箇所に対して最適化を行う必要ある。しかし、そのような箇所を動的コンパイラ１３５の解析のみで検出しようとすると、重い手続き間解析が必要となり現実的でない。そこで本発明では、そのような箇所をプログラマが最適化対象として簡単に指定できるように、配列を割り付けるためのＡＰＩを新たに導入する。プログラマは、配列拡張パターンの配列割り付け箇所を実行環境（仮想マシン１０５）が特別扱いできるように、new演算子を用いて配列を割り付ける代わりに、新たに定義されたＡＰＩを用いて配列を割り付ける。

新たに導入するＡＰＩは、標準ライブラリの一部として提供し、プリミティブ型の配列（Ｊａｖａ（登録商標）言語の場合、boolean[]、byte[]、char[]、Object［］型などの配列）毎に、初期サイズの配列を割り付けるメソッド（特許請求の範囲における「第１のＡＰＩ」に対応）、サイズ拡張した配列を割り付けるメソッド（特許請求の範囲における「第２のＡＰＩ」に対応）の２種類を用意する。各メソッドの仕様は、「第１引数で指定されたサイズを参照して何らかのサイズの配列を返す」というものである。但し、サイズ拡張した配列を割り付けるメソッドに対しては、更に、サイズ拡張前の元の配列を指定する第２引数を用意し、サイズ拡張した配列についてのプロファイル結果を元の配列の割付呼び出しコンテキストにフィードバックできる仕組みを組み込む。フィードバックの仕組みの詳細は後述する。

図３Ａに、文字型の配列に対して新たに導入するＡＰＩの例を示す。図３Ａに示す例では、新たなＡＰＩを、java.lang.Systemクラスにstaticメソッドとして追加している。図３Ａにおいて、char[] getCharArryOfBestSize(int)は、初期サイズの配列を割り付けメソッドであり、char[] extendCharArry(int, char[])は、サイズ拡張した配列を割り付けるメソッドである。各メソッドは実行時に動的コンパイラ１３５によって動的コンパイルされない限りは単に指定されたサイズの配列を返す。

そして、メソッドgetCharArryOfBestSizeは、実行時に動的コンパイラ１３５によって、図３Ｂに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドgetCharArryOfBestSizeは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。プロファイル情報格納領域には、割り付けた配列の割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。

同様にメソッドextendCharArryは、実行時に動的コンパイラ１３５によって、図３Ｃに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドextendCharArryは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。但し、拡張した配列を割り付けるメソッドextendCharArryでは、プロファイル情報格納領域には、第２引数で指定された元の配列を割り付けた割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。

上記新たなＡＰＩを用いるためには、プログラマはこれまで直接new演算子を用いて配列を生成した箇所を、新たなＡＰＩのメソッドの呼び出しに書き換えるだけでよい。図４に示すプログラムは、図１３に示すStringBuilderのプログラムを、新たなＡＰＩを用いて書き換えたものである。図１３に示すnew演算子を用いて初期サイズ１６の配列を割り付ける箇所(a)は、図４に示すメソッドgetCharArryOfBestSizeの呼び出し箇所(a‘)に対応する。また、図１３に示すnew演算子を用いて倍のサイズの配列を割り付ける箇所(ｂ)は、図４に示すメソッドextendCharArryの呼び出し箇所(ｂ’)に対応する。

このように、新たに導入するＡＰＩは、実行時に動的コンパイルされない限りは単に指定されたサイズの配列を返すだけのものとし、ＡＰＩのユーザが実装に依存したコードを書かないように、ＡＰＩのユーザからは各メソッドの実装が見えないようにしなければならない。例えば、配列の初期サイズを変更してもプログラムの意味が変らない箇所をＡＰＩで指定する別のやり方として、new文にアノテーションをつけるだけのＡＰＩを利用する方法が考えられる。しかしながら、このようなＡＰＩでは本発明は正しく動作しない。この理由を、本発明が正しく動作するためにＡＰＩに課される設計上の３つの要件と共に説明する。

まず１つ目は、Ｊａｖａ（登録商標）言語の意味を変えないという要件である。例えば図１４に示すプログラムのように、アノテーションで割り付け場所を指定する手法はＪａｖａ（登録商標）言語の意味を変えてしまう（Ｊａｖａ（登録商標）言語では文にアノテーションを付けることはできないが、説明の便宜上付けられると仮定する。）。なぜならば、本発明を適用すると例えば図１４の(a)ではプロファイル結果に基づき１６要素より大きかったり小さかったりする配列charが生成されうるが、これはＪａｖａ（登録商標）言語の仕様上正しくないからである。従って、図３Ａを参照して説明した２つのＡＰＩのように、配列をnewする部分をメソッド呼び出しでラップしてJava（登録商標）プログラマから見えなくするＡＰＩを用意する必要がある。

２つ目は、移植性が高いという要件である。例えば図１５に示すように、ネイティブライブラリとしてＡＰＩを提供する手法は、異なるＣＰＵやJava（登録商標）ＶＭ間での移植性が低い。従って、図３Ａを参照して説明した２つのＡＰＩのように、単に指定されたサイズの配列を返すだけのデフォルトの実装を提供するＡＰＩを用意する必要がある。

３つ目は、配列を拡張した際に拡張した配列のプロファイル情報を拡張前の元の配列を割り付けた割付呼び出しコンテキストにフィードバックできるという要件である。上述したように、本実施例では、サイズ拡張した配列を割り付けるメソッドが、サイズ拡張前の元の配列を指定する第２引数を取るようにした。第２引数を手掛かりに元の配列の割付呼び出しコンテキストの情報を取得できるので、サイズ拡張した配列についてのプロファイル情報を元の配列の割付呼び出しコンテキストにフィードバックすることが可能となる。

図１Ｂに戻って、本発明では、上記３つの要件を満たす所定のサイズの配列を割り付ける第１のＡＰＩと、引数で指定された元の配列を拡張し、元の配列よりもサイズの大きい配列を割り付ける第２のＡＰＩとを、標準ライブラリの一部としてかつstaticメソッドとしてライブラリ格納部１１７に用意する。中間コード格納部１１５は、上記第１及び第２のＡＰＩを用いて書き換えられた配列拡張パターンを含む実行対象のプログラムである中間コードを格納する。実行部１２０は、中間コード格納部１１５から読み出したプログラムを解釈して、ＡＰＩの記述を検出すると、対応するＡＰＩの機能をライブラリ格納部１１７から呼び出して実行する。動的コンパイラ１３５は、第１のＡＰＩと第２のＡＰＩを実行時に変換し、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードとする。

図２は、図１Ａに示すコンピュータ５０のハードウェア機能と図１Ｂに示すソフトウェア機能とを有する、本発明の実施形態に係る調整装置２００の機能構成を示す。本発明の実施形態に係る調整装置２００は、配列生成部２０２と、拡張配列生成部２０３と、マーク設定部２０５と、初期化部２１０と、呼び出し設定部２１５と、集計部２２０と、プロファイル情報収集部２２５と、インライン展開部２３５と、サイズ決定部２４０と、コード書き換え部２４５とを備える。更に調整装置２００は、プロファイル情報収集部２２５により収集されたプロファイル情報を格納する配列毎のプロファイル情報格納部２３０と、集計部２２０により配列の割付呼び出しコンテキスト毎に収集されたプロファイル情報を格納するコンテキスト毎のプロファイル情報格納部２２３とを備える。なお、配列生成部２０２、拡張配列生成部２０３、マーク設定部２０５及び初期化部２１０の機能は、新たに導入したＡＰＩを呼び出して実行する、図１Ｂに示す実行部１２０の機能として実装してよい。また、呼び出し設定部２１５、集計部２２０及びコンテキスト毎のプロファイル情報格納部２２３の機能は図１Ｂに示すメモリ管理部１２５の機能として実装してよい。また、プロファイル情報収集部２２５及び配列毎のプロファイル情報格納部２３０は、図１Ｂに示すプロファイラ１３０の機能として実装してよい。また、インライン展開部２３５、サイズ決定部２４０及びコード書き換え部２４５の機能は、図１Ｂに示す動的コンパイラ１３５の機能として実装してよい。

配列生成部２０２は、実行対象プログラムからの配列の新規割り付け要求に応答して、所定のサイズの配列を生成する。また、拡張配列生成部２０３は、実行対象プログラムからの配列の拡張要求に応答して、所定のサイズよりも大きいサイズの配列を新規に生成し、生成した配列の各要素に元の配列の対応する要素の値をコピーする。配列生成部２０２及び拡張配列生成部２０３は配列を生成すると、後述するマーク設定部２０５を呼び出して生成した配列の先頭を指すポインタを渡す。このとき拡張配列生成部２０３は更に、配列の拡張要求と共に受け取った拡張すべき元の配列の情報をマーク設定部２０５へ渡す。本実施例では元の配列の情報は元の配列の先頭を指すポインタとする。

マーク設定部２０５は、配列生成部２０２または拡張配列生成部２０３から呼び出されると、サンプリング頻度に基づき、生成された配列をプロファイル対象とするか否かを決定し、プロファイル対象とすると決定した場合に、該配列の先頭を指すポインタにプロファイル対象であることを示すマークを設定する。

ここでサンプリング頻度とは、例えば１ＭＢ割り付けるたび１つオブジェクトをサンプリングするといったようなサンプリングを行う頻度である。また、上記マークの設定は、一例として、ポインタの空いている下１ビットをフラグとして利用したり、ポインタにオフセットを足してヒープ領域外を指すようにしたりして行ってよい。マーク設定部２０５はマークを設定すると、後述する初期化部２１０を呼び出して、マークを付けた配列の先頭を指すポインタと、該当する場合は拡張前の元の配列の先頭を指すポインタとを渡す。

初期化部２１０は、マーク設定部２０５から呼び出されると、後述する集計部２２０やプロファイル情報収集部２２５が、収集したプロファイル情報を所定のデータ構造で所定の領域にそれぞれ格納できるように、予め所定のデータ構造のプロファイル情報を生成し初期化して所定の領域に格納しておく。ここで所定のデータ構造のプロファイル情報は、収集したプロファイル情報を効率よく格納するためのものであり、プロファイル情報収集部２２５によって利用される配列毎のプロファイル情報構造体と、集計部２２０によって利用される割付呼び出しコンテキスト毎のプロファイル情報構造体とを含む。

初期化部２１０は、生成した配列毎のプロファイル情報構造体をその配列の先頭を指すポインタをキーとするハッシュ表（以下、「第１ハッシュ表」という）に登録できるように、実行対象のプログラムの実行直前又は直後に第１ハッシュ表を生成して配列毎のプロファイル情報格納部２３０に格納する。同様に、初期化部２１０は、生成した割付呼び出しコンテキスト毎のプロファイル情報構造体をその割付呼び出しコンテキストをキーとするハッシュ表（以下、「第２ハッシュ表」という）に登録できるように、実行対象のプログラムの実行直前又は直後に第２のハッシュ表を生成して割付呼び出しコンテキスト毎のプロファイル情報格納部２２３に格納する。

配列毎のプロファイル情報構造体は、その配列の割付呼び出しコンテキストに対応するコンテキスト毎のプロファイル情報構造体へのポインタを格納する第１フィールドと、その配列中でアクセスされた最後の要素のインデックスを格納する第２フィールドとを有する。ここでアクセスされた最後の要素とは、アクセスされた要素の中で配列中最も後ろに位置する要素を意味する。例えばある配列Ｔの各要素が、Ｔ［０」、Ｔ［３」、Ｔ［９］、Ｔ［０｝、Ｔ［２｝の順でアクセスされたとすると、配列中でアクセスされた最後の要素のインデックス値は９である。また、割り付けた配列の割付呼び出しコンテキストとは、配列を割り付けるに至るまでのメソッド間の呼び出し関係をいう。

例えば、図５Ａに示すプログラムは、図４に示すStringBuilderを呼び出して配列を割り付けるが、この場合の配列の割付呼び出しコンテキストは、１つは、該プログラムが実行され３行目で配列が割り付けられる時点におけるコンテキストである。即ち、図５Ａに示すプログラムMySample1.method1は、３行目でStringBuilderのコンストラクタを呼び出し、該コンストラクタは図４に示すプログラムの４行目でメソッドgetCharArrayOfBestSizeを呼び出し、メソッドgetCharArrayOfBestSizeはそのメソッド内で配列を割り付ける。従って、この場合の配列の割付呼び出しコンテキストは、MySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)である。

コンピュータは、配列の割付呼び出しコンテキストを任意の表現方法で保持してよい。例えば、配列の割付呼び出しコンテキストを、上記のようにメソッド名を呼び出し順に繋いだ文字列として保持してもよい。或いは、メソッドを示すメソッド情報構造体へのポインタを呼び出し順に繋いでポインタの配列として保持してもよい。

割付呼び出しコンテキスト毎のプロファイル情報構造体は、配列毎のプロファイル情報構造体の第２フィールドの値を割付呼び出しコンテキスト毎に集計するためのデータ構造であり、必要に応じて拡張される表形式をとる。表の各エントリは、アクセスされた一番最後の要素のインデックスを格納する第１フィールドと、第１フィールドに格納された値をアクセスされた一番最後の要素のインデックスとし、かつ、その割付呼び出しコンテキストによって割り付けられた配列の数又は頻度を格納する第２フィールドとを含む。図５Ｂは、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)によって割り付けられた複数の配列についてのプロファイル結果をまとめた表の一例を示す。

初期化部２１０は、マーク設定部２０５から呼び出されると、受け取ったポインタによりアクセスされる新規に割り付けられた配列に対して、配列毎のプロファイル情報構造体の生成及び初期化を行う。初期化部２１０は、配列毎のプロファイル情報構造体を生成すると、これをその配列の先頭を指すポインタをキーとして第１ハッシュ表に登録する。このとき初期化部２１０は、生成した配列毎のプロファイル情報構造体の第２フィールドを値−１で初期化する。初期化部２１０はまた、配列の生成要求元に応じて、生成した配列毎のプロファイル情報構造体の第１フィールドを初期化する。

配列が、新規割り付け要求に応答して配列生成部２０２により生成されたものである場合、初期化部２１０は、まず、該配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在するか否かを確認する。対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在する場合、初期化部２１０は、生成した配列毎のプロファイル情報構造体の第１フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在しない場合、初期化部２１０は、新たに割付呼び出しコンテキスト毎のプロファイル情報構造体を生成し、これをその配列の割付呼び出しコンテキストをキーとして第２ハッシュ表に登録する。そして初期化部２１０は、生成した配列毎のプロファイル情報構造体の第１フィールドに、新たに生成した割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。

なお、初期化部２１０は、配列の割付呼び出しコンテキストの情報を、配列を割り付けたスレッドのスタックを辿ることにより取得する。スタックは、完了していないメソッドにそれぞれ対応する１以上のフレームから構成されており、各フレームには対応するメソッドの状態情報（メソッド名を含む）が格納されている。スタックトップのフレームは現在実行中のメソッドのためのものであり、該メソッドを呼び出したメソッドのフレームがその下にある。このようにスタックには、１以上のフレームがそれぞれ対応するメソッドの呼び出し順に従って下から上へ積まれている。スタックを辿る際は、一番下のmainメソッドまで辿ってもよく、或いは、予め定めた段数（例えば２０段）だけ辿ってもよい。初期化部２１０はコンテキスト情報を取得すると、これをキーとして第２ハッシュ表から割付呼び出しコンテキスト毎のプロファイル情報構造体を取得する。ヒットしない場合、生成した配列に対応するコンテキスト毎のプロファイル情報構造体は未だ生成されていないことを意味する。

一方、配列が配列の拡張要求に応答して配列拡張生成部２０３により生成された場合、初期化部２１０は、マーク設定部２０５から受け取った拡張前の元の配列の先頭を指すポインタをキーとして第１ハッシュ表から配列毎のプロファイル情報構造体を取得する。そして初期化部２１０は、その第１フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを読み出し、これを生成した配列毎のプロファイル情報構造体の第１フィールドに設定する。

呼び出し設定部２１５は、マークを付されたポインタを介して配列へのアクセスがあるとプロファイラ１３０が呼び出されるように、プロファイラ１３０の呼び出しを設定する。該設定には、実行対象のプログラムのコード（中間コード）を書き換えて行う方法と、ページ保護機構を利用する方法とがある。呼び出し設定部２１５は後者を採用し、前者については、後述するコード書き換え部２４５が採用する。従って、調整装置２００は、呼び出し設定部２１５と後述するコード書き換え部２４５のうち少なくとも一方を含めばよいことに留意されたい。

ページ保護機構を利用する呼び出し設定部２１５は、より具体的には、プロファイル対象であることを示すマークを付されたポインタが指す先のページを読み書き禁止に設定し、該ポインタを介して配列がアクセスされるとシグナルハンドラが呼び出されるようにする。この場合、シグナルハンドラがプロファイラ１３０としてプロファイル情報の収集を行う。なお、呼び出し設定部２１５は、上記プロファイラ１３０の呼び出し設定を、例えば実行対象プログラムの実行開始前、又は直後に行う。

プロファイル情報収集部２２５は、プロファイラ１３０又はシグナルハンドラの呼び出しに応答して、即ち、プロファイル対象に設定された配列へのアクセスを検出することに応答して、該アクセスに関するプロファイル情報の収集を行う。プロファイル情報収集部２２５は、収集したプロファイル情報を、対応する配列毎のプロファイル情報構造体に格納する。より具体的には、プロファイル情報収集部２２５は、アクセスされた配列の先頭を指すポインタをキーにして配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を得る。そしてプロファイル情報収集部２２５は、取得した配列毎のプロファイル情報構造体の第２フィールドの値を読み出し、上記配列の現在アクセスされた要素のインデックスと比較する。現在のインデックスのほうが大きい場合、プロファイル情報収集部２２５は、現在のインデックスで上記第２フィールドの値を更新する。

集計部２２０は、ガーベジコレクションにおけるプロファイル対象の配列の破棄処理に応答して、対応する配列毎のオブジェクト情報構造体の記録を、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体に集計する。具体的には、集計部２２０はまず、破棄対象の配列のポインタをキーとして、配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表から対応する配列毎のオブジェクト情報構造体を取得する。そして集計部２２０は、その第１フィールドのポインタ値から、割付呼び出しコンテキスト毎のプロファイル情報格納部２２３に格納される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体である表の中に、取得した配列毎のオブジェクト情報構造体の第２フィールドの値に対応するエントリが既に存在しているか否かを確認する。対応するエントリが既に存在する場合、集計部２２０は、該エントリの第２フィールドの頻度値を１増加する。対応するエントリが存在しない場合、集計部２２０は、取得した割付呼び出しコンテキスト毎のプロファイル情報構造体の表にエントリを１つ追加し、そのエントリの第１フィールドに、取得した配列毎のオブジェクト情報構造体の第２フィールドの値を設定し、そのエントリの第２フィールドに、頻度として値１を設定する。

インライン展開部２３５は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、上記中間コードの部分に含まれる配列の割付呼び出しコンテキストについて十分なプロファイル情報が集まっていることを条件に、そのコンテキストをインライン展開する。例えばインライン展開部２３５は、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体の全エントリについての頻度の合計が予め定めた閾値よりも大きい場合に、該コンテキストについて十分なプロファイル情報が集まっていると判断してよい。インライン展開部２３５はインライン展開処理の後、後述するサイズ決定部２４０を呼び出す。

サイズ決定部２４０は、インライン展開部２３５から呼び出されると、インライン展開された配列の割付呼び出しコンテキストに対し、該コンテキストに対して収集されたプロファイル情報に基づいて該コンテキストが割り付ける配列の初期サイズを決定する。なお、収集されたプロファイル情報とは、上記コンテキストをキーとしてコンテキスト毎のプロファイル情報格納部２２３に格納される第２ハッシュ表を引いて取得される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体である。好ましくは、サイズ決定部２４０は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を配列の割り付け初期サイズとする。これに代えて、サイズ決定部２４０は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を配列の割り付け初期サイズとしてもよい。

ここで図５Ａ〜図５Ｃ及び図６Ａ〜図６Ｃを参照して、インライン展開部２３５のインライン展開処理と、サイズ決定部２４０のサイズ決定処理を具体的に説明する。上述したように図５Ａに示すプログラムは、図４に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図５Ｂに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。なお、十分なプロファイルが集まっていると判断するための予め定められた閾値を２０とする。

すると、図５Ｂに示す表の頻度の合計は２５であるため、インライン展開部２３５は、上記コンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部２３５は、図３Ｂに示すメソッドgetCharArrayOfBestSize(int)の定義を、図５Ａに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図５Ｃに示すコードを得る。このときサイズ決定部２４０は、図５Ｂに示す表において最大のインデックス値が１であることから、配列のサイズは要素数２で十分であると判定し、配列の割り付け初期サイズを２に決定する。なお、図４に示すように、当初配列の初期サイズは１６であったことに留意されたい。

図６に示すプログラムもまた、図４に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキスト、MySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図６Ｂに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。図６Ｂに示す表の頻度の合計は２４であるため、インライン展開部２３５は、上記コンテキストMySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部２３５は、図３Ｂに示すメソッドgetCharArrayOfBestSize(int)の定義を、図６Ａに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図６Ｃに示すコードを得る。このときサイズ決定部２４０は、図６Ｂに示す表において最大のインデックス値が１６５９であることから、配列のサイズは要素数１６６０で十分であると判定し、配列の割り付け初期サイズを１６６０に決定する。なお、図４に示すように、当初配列の初期サイズは１６であったことに留意されたい。

コード書き換え部２４５は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、プロファイル対象であることを示すマークを付されたポインタを介して配列へのアクセスがあるとプロファイラ１３０が呼び出されるように、上記中間コードの部分に含まれるプロファイル対象の配列へのアクセス命令に対してプロファイラ１３０の呼び出しを設定する。上述したように、コード書き換え部２３５は上記プロファイラ１３０の呼び出しの設定をコードの書き換えによって行う。より具体的には、コード書き換え部２３５は、実行対象のプログラムに含まれる全てのポインタ経由の配列へのアクセス命令の前に、プロファイル対象であることを示すマークの有無を判定するコードと、マークが付されているとの判定結果に対してプロファイラ１３０を呼び出すコードとを挿入する。

次に図７乃至図１１を参照して、調整装置２００の動作を説明する。図７は、本実施形態に係る調整装置２００の動作フローの一例を示す。図８は、図７に示すステップ７４０の実行部１２０（初期化部２１０）による処理の詳細な動作フローの一例を示す。図９は、図７に示すステップ７２０のメモリ管理部１２５による処理の詳細な動作フローの一例を示す。図１０は、図７に示すステップ７５０のプロファイラ１３０による処理の詳細な動作フローの一例を示す。図１１は、図７に示すステップ７６０の動的コンパイラ１３５による処理の詳細な動作フローの一例を示す。

図７に示す調整装置２００の動作フローはステップ７００から開始し、実行部１２０は、メモリ管理部１２０を呼び出して、プロファイラ１３０の呼び出しのためのページ保護機構を設定させる。続いて実行部１２０は、実行対象プログラム（中間コード）の実行を開始して、次に実行しようとする命令を取得する（ステップ７０５）。続いて実行部１２０は、実行しようとする現在の命令がオブジェクトを割り付けるか否かを判定する（ステップ７１０）。現在の命令がオブジェクトを割り付けると判定した場合（ステップ７１０：ＹＥＳ）、実行部１２０はガーベジコレクションが必要であるか否かを判定する（ステップ７１５）。ガーベジコレクションが必要であると判定した場合（ステップ７１５：ＹＥＳ）、実行部１２０は、メモリ管理部１２５を呼び出して処理を実行させる。メモリ管理部１２５による処理の詳細は、図９を参照して後述する。

メモリ管理部１２５による処理の後、続いて実行部１２０は、実行する命令が所定サイズの配列を割り付ける第１のＡＰＩによる配列割付の命令であり、かつ、該命令により割り付ける配列をサンプリング頻度に基づきサンプリング対象とすべきか否かを判定する（ステップ７２５）。第１のＡＰＩによる配列割付の命令でない場合、又は第１のＡＰＩによる配列割付の命令であるがサンプリング対象としないと決定した場合（ステップ７２５：ＮＯ）、処理はステップ７３０へ進み、続いて実行部１２０は、実行する命令が、第２引数で指定された元の配列を拡張する第２のＡＰＩによる拡張配列の割付命令であり、かつ、第２引数で指定された元の配列の先頭を指すポインタにサンプリング対象であることを示すマークが付いているか否かを判定する。第２のＡＰＩによる配列割付の命令でない場合、又は第２のＡＰＩによる配列割付の命令であるが、受け取った上記ポインタにマークが付いてない場合（ステップ７３０：ＮＯ）、処理はステップ７４５へ進む。なお、ステップ７２５において少なくとも第１のＡＰＩによる配列割付の命令であると判定した場合、又はステップ７３０において少なくとも第２のＡＰＩによる拡張配列の割付命令であると判定した場合、実行部１２０はそれぞれ要求される配列を割り付ける。

ステップ７２５またはステップ７３０において肯定的な判定結果が得られた場合（ステップ７２５：ＹＥＳまたはステップ７３０：ＹＥＳ）、処理はステップ７３５へ進み、実行部１２０は、ステップ７２５またはステップ７３０で割り付けた配列の先頭を指すポインタに、プロファイル対象であることを示すマークを付ける。続いて実行部１２０は、プロファイル対象とした配列に対して初期化処理を行う（ステップ７４０）。初期化処理の詳細は図８を参照して後述する。

ステップ７４０の後、ステップ７１０において現在の命令がオブジェクトを割り付けないと判定した場合（ステップ７１０：ＮＯ）、又はステップ７３０において否定的な判定結果が得られる場合（ステップ７３０：ＮＯ）、処理はステップ７４５へ進み、実行部１１５２０は、現在の命令はサンプリングされた、即ちプロファイル対象の配列へのアクセス命令であるか否かを判定する。プロファイル対象の配列へのアクセス命令であると判定した場合（ステップ７４５：ＹＥＳ）、実行部１２０はプロファイラ１３０を呼び出して処理を実行させる（ステップ７５０）。プロファイラ１３０による処理の詳細は、図１０を参照して後述する。

ステップ７５０の後、又はステップ７４５において現在の命令がプロファイル対象の配列へのアクセス命令ではないと判定した場合（ステップ７４５：ＮＯ）、処理はステップ７５５へ進み、実行部１２０は、次に実行する中間コードの部分を動的にコンパイルする必要があるか否かを判定する。動的コンパイルが必要であると判定した場合（ステップ７５５：ＹＥＳ）、実行部１２０は動的コンパイラ１３５を呼び出して処理を実行させる（ステップ７６０）。動的コンパイラ１３５による処理の詳細は、図１１を参照して後述する。

ステップ７６０の後、又はステップ７５５において動的コンパイルが必要でないと判定した場合（ステップ７５５：ＮＯ）、処理はステップ７６５へ進み、実行部１２０は、実行対象プログラムの実行が終了したか否かを判定する。実行対象プログラムの実行がまだ終了していない場合（ステップ７６５：ＮＯ）、処理はステップ７０５へ戻る。一方、プログラムの実行が終了した場合（ステップ７６５：ＹＥＳ）、調整装置２００の動作フローは終了する。

図８に示す初期化２１０による処理の動作フローはステップ８００から開始し、初期化２１０は、図７に示すステップ７３５においてそのポインタにマークを付けた配列に対して、配列毎のプロファイル情報構造体を生成し、その第２フィールドを値―１で初期化する。続いて初期化部２１０は、上記配列の割付が、第２引数で指定された元の配列を拡張する第２のＡＰＩによる割付であったか否かを判定する（ステップ８０５）。第２のＡＰＩによる割付でなかった場合（ステップ８０５：ＮＯ）、続いて初期化部２１０は、上記配列を割り付けたスレッドのスタックを辿って、上記配列を割り付けた割付呼び出しコンテキストを取得する（ステップ８１０）。続いて初期化部２１０は、上記配列を割り付けた割付呼び出しコンテキストをキーとして割付呼び出しコンテキスト毎のプロファイル情報格納部２２３に格納される第２ハッシュ表を引き、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第２ハッシュ表に存在するか否かを判定する（ステップ８１５）。

対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第２ハッシュ表に存在しない場合（ステップ８１５：ＮＯ）、初期化部２１０は、上記配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を新たに生成し、該コンテキストをキーとして第２ハッシュ表に登録する（ステップ８２０）。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第２ハッシュ表に存在する場合（ステップ８１５：ＹＥＳ）、またステップ８２０の後、初期化部２１０は、ステップ８００において生成した配列毎のプロファイル情報構造体の第１フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。

一方ステップ８０５において、上記配列の割付が第２のＡＰＩによる割付であった場合（ステップ８０５：ＹＥＳ）、初期化部２１０は、第２のＡＰＩの第２引数で指定された拡張前の元の配列のポインタをキーとして配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する。そして初期化部２１０は、取得した配列毎のプロファイル情報構造体の第１フィールドに格納された割付呼び出しコンテキスト毎の構造体へのポインタを、ステップ８００で生成した配列毎のプロファイル情報構造体の第１フィールドに設定する。ステップ８２５又はステップ８３５から処理はステップ８３０へ進み、初期化部２１０は、ステップ８００で生成した配列毎のプロファイル情報構造体を、その配列の先頭を指すポインタをキーとして配列毎のプロファイル情報格納部２３０内の第１ハッシュ表に登録する。その後処理は終了する。

図９に示すメモリ管理部１２５による処理の動作フローはステップ９００から開始し、メモリ管理部１２５は、ヒープ領域に生成されている使用中の全オブジェクトを検出するために、オブジェクト間のポインタによる参照関係を示すツリー構造をスキャンし、使用中のオブジェクトを指す全ポインタについて以下の一連の処理を繰り返す。メモリ管理部１２５はまず、現在のポインタに対して、通常のガーベジコレクション処理を実行する（ステップ９０５）。通常のガーベジコレクション処理のアルゴリズムは周知の技術であり、本発明の要旨ではないので詳細な説明は省略する。

続いてメモリ管理部１２５は、ステップ９０５におけるガーベジコレクション処理で配列オブジェクトを破棄すると決定し、かつ、破棄すると決定した配列オブジェクトに対応する配列毎のプロファイル情報構造体が、配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表内に存在するか否かを判定する（ステップ９１０）。否定的な判定結果が得られた場合（ステップ９１０：ＮＯ）、現在のポインタについての処理は終わる。一方、肯定的な判定結果が得られた場合（ステップ９１０：ＹＥＳ）、メモリ管理部１２５は、破棄する配列に対応する配列毎のプロファイル情報構造体の第１フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを取得し（ステップ９１５）、ポインタが指す表に、破棄する配列に対応する配列毎のプロファイル情報構造体の第２フィールドに格納されるインデックス値に対応するエントリが存在するか否かを判定する（ステップ９２０）。

対応するエントリが存在すると判定した場合（ステップ９２０：ＹＥＳ）、メモリ管理部１２５は、
該エントリの第２フィールドの頻度値を１増やす（ステップ９２５）。一方、対応するエントリが存在しないと判定した場合（ステップ９２０：ＮＯ）、メモリ管理部１２５は、ステップ９１５で取得したポインタが指す表にエントリを１つ追加し、該エントリの第１フィールドに、破棄する配列に対応する配列毎のプロファイル情報構造体の第２フィールドに格納されるインデックス値を、該エントリの第２フィールドに、頻度値１をそれぞれ設定する（ステップ９３０）。

ステップ９２５又はステップ９３０の後、メモリ管理部１２５は、破棄する配列を割り付けた割付呼び出しコンテキストについて十分なプロファイルが集まったと判定することを条件に、動的コンパイラ１３５を呼び出して動的コンパイルを行わせる。動的コンパイラ１３５による動的コンパイル処理の詳細は図１１を参照して後述する。続いてメモリ管理部１２５は、破棄する配列に対応する配列毎のプロファイル情報構造体を、配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表から削除する（ステップ９４０）。使用中のオブジェクトを指す全ポインタについて上記一連の処理が行われると、処理は終了する。

図１０に示すプロファイラ１３０による処理の動作フローはステップ１０００から開始し、プロファイラ１３０は、プロファイラ１３０呼び出しの要因となった現在のオブジェクト・アクセス命令における配列をアクセスする。続いてプロファイラ１３０は、アクセスした配列の先頭を指すポインタをキーとして、配列毎のプロファイル情報格納部２３０に格納される第１ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する（ステップ１００５）。続いてプロファイラ１３０は、現在のオブジェクト・アクセス命令によりアクセスされる配列の要素のインデックス値と、取得した配列毎のプロファイル情報構造体の第２フィールドに格納されるインデックス値とを比較し、アクセスしようとする配列の要素のインデックス値が大きい場合、該インデックス値で上記第２フィールドの値を更新する（ステップ１０１０）。そして処理は終了する。

図１１に示す動的コンパイラ１３５による処理の動作フローはステップ１１００から開始し、動的コンパイラ１３５は、次に実行しようとする実行対象プログラムのコード部分を、中間コード（バイトコード）格納部１１５から読み込む。続いて動的コンパイラ１３５は、コンパイル対象の上記コード部分に含まれる割付呼び出しコンテキストについて、十分なプロファイルがコンテキスト毎のプロファイル情報格納部２２３に収集されていることを条件に、上記コンテキストをインライン展開する（ステップ１１０５）。

続いて動的コンパイラ１３５は、インライン展開された割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体に記録されたインデックスのうち最大のインデックスの値を、配列の割付初期サイズとしてインライン展開したコードに埋め込む（ステップ１１１０）。続いて動的コンパイラ１３５は、上記コード部分の上記割付呼び出しコンテキスト以外の部分について最適化処理を行う（ステップ１１１５）。最適化の種類は複数存在し、それぞれのアルゴリズムは既知の技術であり本発明の要旨でもないので、ここでは詳細な説明を省略する。

続いて動的コンパイラ１３５は、コンパイル対象の上記コード部分に対し、プロファイラ１３０呼び出しのためのコードの書き換えを行う（ステップ１１２０）。続いて、動的コンパイラ１３５は、上記コード部分の上記割付呼び出しコンテキスト以外の部分をコンパイルし、ネイティブコードを生成する（ステップ１１２５）。そして処理は終了する。

［実験］
１．実装
動作周波数最大４．７ＧＨｚのＲＩＳＣプロセッサ（クアッドコア、２スレッドのＳＭＴエンジン搭載のＰＯＷＥＲ６（商標））と利用した各ベンチマークが必要とする最低のヒープメモリ量の２倍のヒープメモリ量をハードウエアとして備え、オペレーティング・システムとしてＬｉｎｕｘ（商標）２．６．１８を用いるＩＢＭ社のＪａｖａ（登録商標）仮想マシンに、本発明の実施形態に係る調整プログラムを実装した。なお、実装した調整プログラムでは、８ＭＢ割り付ける毎に１つの配列をサンプリングするサンプリング頻度を用いた。また、ベンチマークＤａＣａｐｏの中からオブジェクトを多く割り付ける８つのベンチマークプログラム（fop、jython、lusearch、pmd、sunflow、tomcat、xalan、Geo．mean）を選択した。また、Ｊａｖａ（登録商標）標準ライブラリのjava.lang.StringBuilder、java.io、BufferedReader、lusearchベンチマークの２つのクラス、xalaベンチマークの３つのクラスの各々におけるは配列の割付を、本発明で新たに導入したＡＰＩを用いて行うように書き換えた。

２．実験結果
図１２は、速度向上率についての実験結果を示す。図１２に示されるように、ベンチマークによっては最大３００％以上（４倍以上）の性能向上が見られた。なお、性能低下は、最大でも２．２％であり、これはアクセスプロファイラのオーバーヘッドによるものである。

以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。

なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。

Claims (14)

1. 配列の初期サイズを動的に調整する調整プログラムであって、該プログラムはコンピュータに、
   （ａ）実行対象プログラムからの配列の割り付け要求に応答して、所定サイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
   （ｂ）前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
   （ｃ）前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、 （ｄ）各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
   （ｅ）前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
   を実行させる前記調整プログラム。
2. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ（ｅ）は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項１に記載の調整プログラム。
3. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ（ｅ）は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む、請求項１に記載の調整プログラム。
4. 配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられており、ステップ（ｂ）は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む、請求項１に記載の調整プログラム。
5. ステップ（ｄ）の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる、請求項１に記載の調整プログラム。
6. 情報処理装置おいて配列の初期サイズを動的に調整する調整方法であって、
   （ａ）前記情報処理装置が、実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
   （ｂ）前記情報処理装置が、前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
   （ｃ）前記情報処理装置が、前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、
   （ｄ）前記情報処理装置が、各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
   （ｅ）前記情報処理装置が、前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
   を含む調整方法。
7. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ（ｅ）は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項６に記載の調整方法。
8. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ（ｅ）は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項６に記載の調整方法。
9. 配列の初期サイズを動的に調整する情報処理装置であって、
   記憶装置と、
   前記記憶装置に格納された実行対象プログラムと、
   前記実行対象プログラムを解釈して、ＡＰＩの記述を検出することに応答して、対応するＡＰＩの機能を呼び出して実行する実行手段と、
   前記実行手段によって呼び出され得る、所定のサイズの配列を割り付ける第１のＡＰＩと、引数として拡張すべき配列の情報を受け取り、該配列よりもサイズの大きい配列を割り付ける第２のＡＰＩであって、前記第１及び第２のＡＰＩは、実行時に、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードに変換される、前記第１及び第２のＡＰＩと、
   プロファイル対象の配列へのアクセスの検出に応答して前記実行手段によって呼び出され得る、アクセスを検出された前記配列に対応するプロファイル情報格納領域に前記配列へのアクセス情報を格納するプロファイラと、
   次に実行すべき実行対象プログラムのコード部分を動的にコンパイルする動的コンパイラであって、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに関連づけられた全アクセス情報に基づき決定される配列のサイズを前記配列の割り付け初期サイズとして前記コード部分に埋め込む前記動的コンパイラと、
   を含む情報処理装置。
10. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとする、請求項９に記載の情報処理装置。
11. 各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとする、請求項９に記載の情報処理装置。
12. 前記第２のＡＰＩは、引数として受け取った拡張すべき配列の情報を用いて、該配列に対応するプロファイル情報格納領域から前記拡張前の配列の割付呼び出しコンテキスト情報を取得する、請求項９に記載の情報処理装置。
13. 前記第１及び第２のＡＰＩは、プリミティブ型の配列ごとに用意される、請求項９に記載の情報処理装置。
14. 前記第１及び第２のＡＰＩは、標準ライブラリの一部としてかつstaticメソッドとして用意される、請求項９に記載の情報処理装置。

Images