情報処理装置、配列の初期サイズ調整プログラム及び方法
【課題】配列の初期サイズを実行環境において動的に調整する技術を提供する。
【解決手段】
調整理置は、記憶装置と、記憶装置に格納された実行対象プログラムと、実行対象プログラムを解釈し、APIの記述の検出に応答して対応するAPIの機能を呼び出し実行する実行手段と、実行手段により呼び出され得る、所定のサイズの配列を割り付ける第1のAPIと、引数で指定された配列を拡張する第2のAPIとであって、実行時にそれぞれ、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードに変換される、上記第1及び第2のAPIと、配列へのアクセスをプロファイルするプロファイラと、動的コンパイル対象のコード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに関連づけられた全アクセス情報に基づき決定される配列のサイズを配列の初期サイズとして埋め込む動的コンパイラと、を含む。
【解決手段】
調整理置は、記憶装置と、記憶装置に格納された実行対象プログラムと、実行対象プログラムを解釈し、APIの記述の検出に応答して対応するAPIの機能を呼び出し実行する実行手段と、実行手段により呼び出され得る、所定のサイズの配列を割り付ける第1のAPIと、引数で指定された配列を拡張する第2のAPIとであって、実行時にそれぞれ、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードに変換される、上記第1及び第2のAPIと、配列へのアクセスをプロファイルするプロファイラと、動的コンパイル対象のコード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに関連づけられた全アクセス情報に基づき決定される配列のサイズを配列の初期サイズとして埋め込む動的コンパイラと、を含む。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、配列の初期サイズを調整する技術に関し、より詳細には、配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法に関する。
【背景技術】
【0002】
従来、配列の適切なサイズが前もって分からない場合、最初は小さいサイズの配列を割り付け、必要に応じて拡張したサイズの配列を割り付けるプログラミングパターン(以下、「配列拡張パターン」という)が利用されている。配列拡張パターンの一例を図13に示す。図13に示すStringBuilderクラスでは、最初、コンストラクタにより要素数16の配列char[]が割り付けられる(図13の(a)を参照)。そして、メソッドappendにより配列char[]の要素に値が設定される際に、if文で配列の拡張が必要であるか否かが判定され、if文の条件が真となる場合に倍のサイズの配列newchar[]が新たに割り付けられる(図13の(b)を参照)。新たに割り付けた配列newchar[]の各要素には元の配列char[]の各要素の値がコピーされる。
【0003】
しかしながら上記プログラミングパターンの利用には、配列の初期サイズはしばしば大き過ぎたり小さ過ぎたりするため実行に無駄が生じるという問題がある。特に配列の寿命が短く頻繁に割り付けられる場合には、ゼロ初期化やコピーのオーバーヘッドが大きい。
【0004】
可変長オブジェクトの初期サイズの選択方法に関する従来技術として非特許文献1が存在する。非特許文献1は、可変長オブジェクトとしてコレクションオブジェクトに着目し、以下の初期サイズ選択方法を開示する。1.コレクションオブジェクトを割り付けるときに呼び出しコンテキストを取得してこれを割り付けたコレクションオブジェクトのオブジェクト情報構造体に記録する。2.コレクションオブジェクトに対するメソッド呼び出しの種別や回数を対応するオブジェクト情報構造体に記録する。3.コレクションオブジェクトを破棄する際に、対応するオブジェクト情報構造体の記録を割付呼び出しコンテキスト毎の情報構造体に集計する。4.プログラム実行終了後、集計結果に基づきコレクションオブジェクトの適切な初期サイズをプログラマに提案する。
【0005】
そこで上記非特許文献1の技術を配列の初期サイズの決定処理に適用することを考える。すると、図13に示す(a) 、(b)の2箇所で割り付けられた配列へのアクセス情報及び配列の割付呼び出しコンテキスト情報を、それぞれ対応するオブジェクト情報構造体に記録し、記録した情報を割付呼び出しコンテキスト毎の情報構造体に集計することで、(a) 、(b)の2箇所でそれぞれ割り付けられる配列について適切な初期サイズをプログラマに提案することが可能となる。しかしこの場合、プロファイル情報は割付呼び出しコンテキスト単位でしかまとめることができないので、 (b)で割り付けられた配列のプロファイル情報を(a)で割り付けられた配列の割付呼び出しコンテキストにフィードバックすることができない。結果、(a) 、(b)の2箇所で大きすぎるサイズの配列を割り付けることはなくなるが、配列の拡張処理をなくしたり、その回数を減らしたりすることはできない。
【0006】
以下、本発明の先行技術調査において見つかった他の文献について説明する。
【0007】
特許文献1は、インライン割付元の可変長インスタンスの大きさを、実行プロファイルを使うなどの方法により予測し、例えば、配列の大きさを4と予測した場合に、実行時に定まった配列の長さが4以下である場合には配列をインライン割付け先のインスタンスの中にインライン割付けし、4を超える場合には、配列をインライン割付け先のインスタンスとは別個に割付ける技術を開示する。しかしながら特許文献1の技術は、各割り付け場所で割り付けられる可変長オブジェクトのサイズをプロファイルしており、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたか否かについては全く考慮に入れておらず、従って、特許文献1の技術は配列拡張パターンを最適化することはできない。
【0008】
特許文献2は、プログラム実行時にメモリ容量変更の必要がある場合、環境設定ファイルを参照し、この環境設定ファイルの最大配列長、あるいは最小配列長と実行マシンの実メモリにより、プログラム中で必要とする配列長の最適な値を算出する手段と、次にソースプログラム中の配列長を変更し、再コンパイルして、実行する手段とを備えたことを特徴とする配列領域確保装置を開示する。しかしながら、
特許文献2の技術は、プログラム中で割り付ける配列のサイズを、実行するマシンが持つメモリの大きさに応じて調整するものであり、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたかに応じて調整するものではなく、従って、特許文献2の技術は配列拡張パターンを最適化することはできない。
【0009】
特許文献3は、配列のデータ領域の各行を指し示すデータ領域へのポインタを含むデータ領域へのポインタ配列の先頭を指すポインタ配列へのポインタを格納するメモリ管理テーブルおよび前記メモリ管理テーブルの大きさをそれぞれプライベートなメンバ変数として実装し、かつ、前記メモリ管理テーブルを初期化する初期化関数コンストラクタ、配列の領域の確保・割り当てを行うメモリ確保関数、領域の解放を行うためのメモリ解放関数、前記データ領域および前記データ領域へのポインタ配列を前記メモリ解放関数を使用して解放する解放関数デストラクタをそれぞれパブリックなメンバ関数として実装する、第1のC++言語における配列の領域の動的確保・解放方法を開示する。しかしながら、特許文献3の技術は、多次元配列で高次元のサイズをコンパイル時定数でなく実行時変数とするためのものであり、かかる手法では割り付けた配列が実行時に拡張されることはない。そのため、特許文献3の技術は配列拡張パターンを最適化することはできない。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開2003−0271393号公報
【特許文献2】特開1993−0204616号公報
【特許文献3】特開2000−0066900号公報
【非特許文献】
【0011】
【非特許文献1】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
【発明の概要】
【発明が解決しようとする課題】
【0012】
この発明は、上記の問題点を解決するためになされたものであって、配列拡張パターンにおいて配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法を提供することを目的とする。
【課題を解決するための手段】
【0013】
本発明は、上記課題を解決するために、以下の特徴を有する配列の初期サイズを動的に調整する調整プログラムを提供する。該プログラムはコンピュータに、(a)実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、(b)前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、(c)前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、(d)各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、(e)前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップとを実行させる。
【0014】
好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む。
【0015】
また好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む。
【0016】
また好ましくは、配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられる。そしてステップ(b)は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む。
【0017】
また好ましくは、ステップ(d)の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる。
【0018】
以上、配列の初期サイズを動的に調整する調整プログラムとして本発明を説明した。しかし、本発明は、上記調整プログラムをインストールしたコンピュータにおいて実行される、配列の初期サイズを動的に調整する調整方法として把握することもできる。また、本発明は、上記調整プログラムをインストールすることにより実現される、配列の初期サイズを動的に調整するための情報処理装置(以下、「調整装置」という)として把握することもできる。
【発明の効果】
【0019】
本発明では、サイズ拡張後の配列のプロファイル情報を記録する際に、これをサイズ拡張後の配列の割付呼び出しコンテキストではなく、サイズ拡張前の元の配列の割付呼び出しコンテキストに関連付ける。結果、サイズ拡張後の配列についてのプロファイル情報を、拡張前の元の配列の割付呼び出しコンテキストにフィードバックすることが可能となり、拡張処理を減らすことのできる配列の適切な初期サイズを実行環境において動的に決定することが可能となった。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【0020】
【図1A】本発明の実施形態に係るコンピュータ50のハードウェア構成の一例を示す。
【図1B】本発明の実施形態に係るコンピュータ50のソフトウェア構成の一例を示す。
【図2】本発明の実施形態に係る調整装置200の機能構成を示す。
【図3A】標準ライブラリの一部として提供される新APIの一例を示す。
【図3B】getCharArrayOfBestSize()の実行時コンパイルされたコードの一例を示す。
【図3C】extendCharArray ()の実行時コンパイルされたコードの一例を示す。
【図4】図3Aに示す新APIを用いたStringBuilderの一例を示す。
【図5A】図4に示すStringBuilderを用いて配列を生成するプログラムの一例を示す。
【図5B】図5Aの3行目で割り付けられる配列についてのプロファイル結果の一例を示す。
【図5C】図5Bに示すプロファイル結果を参照してインライン展開されたコードを示す。
【図6A】図4に示すStringBuilderを用いて配列を生成するプログラムの他の例を示す。
【図6B】図6Aの3行目で割り付けられる配列についてのプロファイル結果の一例を示す。
【図6C】図6Bに示すプロファイル結果を参照してインライン展開されたコードを示す。
【図7】本実施形態に係る調整装置200の動作フローの一例を示す。
【図8】図7に示すステップ740の初期化部210による処理の詳細な動作フローの一例を示す。
【図9】図7に示すステップ720のメモリ管理部125の詳細な動作フローの一例を示す。
【図10】図7に示すステップ750のプロファイラ130による処理の詳細な動作フローの一例を示す。
【図11】図7に示すステップ760の動的コンパイラ135による他の処理の詳細な動作フローの一例を示す。
【図12】速度向上率に関する実験結果を示す。
【図13】従来の配列拡張パターンを示すプログラムの一例を示す。
【図14】アノテーションで割付場所を指定するAPIを用いたプログラムの一例を示す。
【図15】ネイティブライブラリとして提供される新たなAPIの一例を示す。
【発明を実施するための形態】
【0021】
以下、本発明の実施形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【0022】
図1は、本発明の実施形態による情報処理装置としてのコンピュータ50のハードウェア構成の一例を示した図である。コンピュータ50は、バス2に接続されたメインCPU(中央処理装置)1とメイン・メモリ4を含んでいる。CPU1は好ましくは、32ビット又は64ビットのアーキテクチャに基づくものであり、例えば、インテル社のCore i(商標)シリーズ、Core 2(商標)シリーズ、Atom(商標)シリーズ、Xeon(商標)シリーズ、Pentium(登録商標)シリーズ、Celeron(登録商標)シリーズ、AMD社のPhenom(商標)シリーズ、Athlon(商標)シリーズ、Turion(商標)シリーズ又はSempron(商標)が使用されうる。
【0023】
またハードディスク装置13、30、及びCD−ROM装置26、29、フレキシブル・ディスク装置20、MO装置28、DVD装置31のようなリムーバブル・ストレージ(記録メディアを交換可能な外部記憶システム)がフレキシブル・ディスクコントローラ19、IDEコントローラ25、SCSIコントローラ27などを経由してバス2へ接続されている。フレキシブル・ディスク、MO、CD−ROM、DVD−ROMのような記憶メディアが、リムーバブル・ストレージに挿入される。
【0024】
これら記憶メディアやハードディスク装置13、30、ROM14には、オペレーティング・システム、J2EEなどのJava(登録商標)処理環境、Java(登録商標)アプリケーション、Java(登録商標)仮想マシン(VM)、Java(登録商標)実行時(JIT)コンパイラを提供するプログラム、その他のプログラム及びデータが、メイン・メモリ4にロード可能に記憶されている。更に、上記記憶メディアやハードディスク装置13、30、ROM14には、オペレーティング・システムと協働してCPU1に命令を与え、本発明を実施するためのコンピュータ・プログラムを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ50にインストールされ、コンピュータ50を本発明の実施形態による調整装置200として機能させる調整プログラムやデータを記録することができる。
【0025】
上記調整プログラムは、配列生成モジュールと、拡張配列生成モジュールと、マーク設定モジュールと、初期化モジュールと、呼び出し設定モジュールと、集計モジュールと、プロファイル情報収集モジュールと、インライン展開モジュールと、サイズ決定モジュールと、コード書き換えモジュールとを含む。これらプログラム及びモジュールは、CPU1に働きかけて、コンピュータ50を、各々後述する配列生成部202と、拡張配列生成部203、設定部205と、初期化部210と、呼び出し設定部215と、集計220と、プロファイル情報収集部225と、インライン展開部235と、サイズ決定部240と、コード書き換え部245としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【0026】
コンピュータ50は、キーボード/マウス・コントローラ5を経由して、キーボード6やマウス7のような入力デバイスからの入力を受ける。コンピュータ50は、オーディオコントローラ21を経由して、マイク24からの入力を受け、またスピーカー23から音声を出力する。コンピュータ50は、視覚データをユーザに提示するための表示装置11に、グラフィックスコントローラ10を経由して接続される。コンピュータ50は、ネットワーク・アダプタ18(イーサネット(登録商標)・カードやトークンリング・カード)等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【0027】
以上の説明により、コンピュータ50は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【0028】
図1Bは、本発明を実現するソフトウェアの構成を示すブロック図である。同図において、オペレーティング・システム105は、CPUやメモリを資源として管理し、時分割によるマルチスレッドの機能を実現する。仮想マシン110は、アプリケーション140とオペレーティング・システム105とのインタフェースを行うソフトウェアであり、アプリケーション140から見て仮想マシン以下の階層全体を例えばJava(登録商標)仮想マシン(Virtual Machine)として作用させる。仮想マシン110は、プログラムがバイトコード等の中間コードで与えられるときこれを解釈する実行部(インタープリタ)120と、その解釈に応じて呼び出されるプロファイラ130と、メモリ管理部125とを含む。また、仮想マシン110はJITコンパイラ等の動的コンパイラ135を含み、バイトコードを実行時に動的に機械語にコンパイルしてネイティブコードを生成し、プログラムの実行を高速化する。なお、上記中間コードはAPIの記述を含みうる。実行部120は中間コード内にAPIの記述を検出すると、ライブラリからそのAPIの機能を呼び出して実行する。
【0029】
ところで本発明は、配列拡張パターンにおける配列の初期サイズをプロファイル結果に基づいて実行時に動的に調整することを目的とするが、配列の初期サイズをコンピュータの演算処理により勝手に変更するとプログラムの意味が変ってしまう場合がある。そのため、配列の初期サイズを変更してもプログラムの意味が変らない箇所を見つけ、当該箇所に対して最適化を行う必要ある。しかし、そのような箇所を動的コンパイラ135の解析のみで検出しようとすると、重い手続き間解析が必要となり現実的でない。そこで本発明では、そのような箇所をプログラマが最適化対象として簡単に指定できるように、配列を割り付けるためのAPIを新たに導入する。プログラマは、配列拡張パターンの配列割り付け箇所を実行環境(仮想マシン105)が特別扱いできるように、new演算子を用いて配列を割り付ける代わりに、新たに定義されたAPIを用いて配列を割り付ける。
【0030】
新たに導入するAPIは、標準ライブラリの一部として提供し、プリミティブ型の配列(Java(登録商標)言語の場合、boolean[]、byte[]、char[]、Object[]型などの配列)毎に、初期サイズの配列を割り付けるメソッド(特許請求の範囲における「第1のAPI」に対応)、サイズ拡張した配列を割り付けるメソッド(特許請求の範囲における「第2のAPI」に対応)の2種類を用意する。各メソッドの仕様は、「第1引数で指定されたサイズを参照して何らかのサイズの配列を返す」というものである。但し、サイズ拡張した配列を割り付けるメソッドに対しては、更に、サイズ拡張前の元の配列を指定する第2引数を用意し、サイズ拡張した配列についてのプロファイル結果を元の配列の割付呼び出しコンテキストにフィードバックできる仕組みを組み込む。フィードバックの仕組みの詳細は後述する。
【0031】
図3Aに、文字型の配列に対して新たに導入するAPIの例を示す。図3Aに示す例では、新たなAPIを、java.lang.Systemクラスにstaticメソッドとして追加している。図3Aにおいて、char[] getCharArryOfBestSize(int)は、初期サイズの配列を割り付けメソッドであり、char[] extendCharArry(int, char[])は、サイズ拡張した配列を割り付けるメソッドである。各メソッドは実行時に動的コンパイラ135によって動的コンパイルされない限りは単に指定されたサイズの配列を返す。
【0032】
そして、メソッドgetCharArryOfBestSizeは、実行時に動的コンパイラ135によって、図3Bに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドgetCharArryOfBestSizeは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。プロファイル情報格納領域には、割り付けた配列の割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。
【0033】
同様にメソッドextendCharArryは、実行時に動的コンパイラ135によって、図3Cに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドextendCharArryは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。但し、拡張した配列を割り付けるメソッドextendCharArryでは、プロファイル情報格納領域には、第2引数で指定された元の配列を割り付けた割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。
【0034】
上記新たなAPIを用いるためには、プログラマはこれまで直接new演算子を用いて配列を生成した箇所を、新たなAPIのメソッドの呼び出しに書き換えるだけでよい。図4に示すプログラムは、図13に示すStringBuilderのプログラムを、新たなAPIを用いて書き換えたものである。図13に示すnew演算子を用いて初期サイズ16の配列を割り付ける箇所(a)は、図4に示すメソッドgetCharArryOfBestSizeの呼び出し箇所(a‘)に対応する。また、図13に示すnew演算子を用いて倍のサイズの配列を割り付ける箇所(b)は、図4に示すメソッドextendCharArryの呼び出し箇所(b’)に対応する。
【0035】
このように、新たに導入するAPIは、実行時に動的コンパイルされない限りは単に指定されたサイズの配列を返すだけのものとし、APIのユーザが実装に依存したコードを書かないように、APIのユーザからは各メソッドの実装が見えないようにしなければならない。例えば、配列の初期サイズを変更してもプログラムの意味が変らない箇所をAPIで指定する別のやり方として、new文にアノテーションをつけるだけのAPIを利用する方法が考えられる。しかしながら、このようなAPIでは本発明は正しく動作しない。この理由を、本発明が正しく動作するためにAPIに課される設計上の3つの要件と共に説明する。
【0036】
まず1つ目は、Java(登録商標)言語の意味を変えないという要件である。例えば図14に示すプログラムのように、アノテーションで割り付け場所を指定する手法はJava(登録商標)言語の意味を変えてしまう(Java(登録商標)言語では文にアノテーションを付けることはできないが、説明の便宜上付けられると仮定する。)。なぜならば、本発明を適用すると例えば図14の(a)ではプロファイル結果に基づき16要素より大きかったり小さかったりする配列charが生成されうるが、これはJava(登録商標)言語の仕様上正しくないからである。従って、図3Aを参照して説明した2つのAPIのように、配列をnewする部分をメソッド呼び出しでラップしてJava(登録商標)プログラマから見えなくするAPIを用意する必要がある。
【0037】
2つ目は、移植性が高いという要件である。例えば図15に示すように、ネイティブライブラリとしてAPIを提供する手法は、異なるCPUやJava(登録商標)VM間での移植性が低い。従って、図3Aを参照して説明した2つのAPIのように、単に指定されたサイズの配列を返すだけのデフォルトの実装を提供するAPIを用意する必要がある。
【0038】
3つ目は、配列を拡張した際に拡張した配列のプロファイル情報を拡張前の元の配列を割り付けた割付呼び出しコンテキストにフィードバックできるという要件である。上述したように、本実施例では、サイズ拡張した配列を割り付けるメソッドが、サイズ拡張前の元の配列を指定する第2引数を取るようにした。第2引数を手掛かりに元の配列の割付呼び出しコンテキストの情報を取得できるので、サイズ拡張した配列についてのプロファイル情報を元の配列の割付呼び出しコンテキストにフィードバックすることが可能となる。
【0039】
図1Bに戻って、本発明では、上記3つの要件を満たす所定のサイズの配列を割り付ける第1のAPIと、引数で指定された元の配列を拡張し、元の配列よりもサイズの大きい配列を割り付ける第2のAPIとを、標準ライブラリの一部としてかつstaticメソッドとしてライブラリ格納部117に用意する。中間コード格納部115は、上記第1及び第2のAPIを用いて書き換えられた配列拡張パターンを含む実行対象のプログラムである中間コードを格納する。実行部120は、中間コード格納部115から読み出したプログラムを解釈して、APIの記述を検出すると、対応するAPIの機能をライブラリ格納部117から呼び出して実行する。動的コンパイラ135は、第1のAPIと第2のAPIを実行時に変換し、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードとする。
【0040】
図2は、図1Aに示すコンピュータ50のハードウェア機能と図1Bに示すソフトウェア機能とを有する、本発明の実施形態に係る調整装置200の機能構成を示す。本発明の実施形態に係る調整装置200は、配列生成部202と、拡張配列生成部203と、マーク設定部205と、初期化部210と、呼び出し設定部215と、集計部220と、プロファイル情報収集部225と、インライン展開部235と、サイズ決定部240と、コード書き換え部245とを備える。更に調整装置200は、プロファイル情報収集部225により収集されたプロファイル情報を格納する配列毎のプロファイル情報格納部230と、集計部220により配列の割付呼び出しコンテキスト毎に収集されたプロファイル情報を格納するコンテキスト毎のプロファイル情報格納部223とを備える。なお、配列生成部202、拡張配列生成部203、マーク設定部205及び初期化部210の機能は、新たに導入したAPIを呼び出して実行する、図1Bに示す実行部120の機能として実装してよい。また、呼び出し設定部215、集計部220及びコンテキスト毎のプロファイル情報格納部223の機能は図1Bに示すメモリ管理部125の機能として実装してよい。また、プロファイル情報収集部225及び配列毎のプロファイル情報格納部230は、図1Bに示すプロファイラ130の機能として実装してよい。また、インライン展開部235、サイズ決定部240及びコード書き換え部245の機能は、図1Bに示す動的コンパイラ135の機能として実装してよい。
【0041】
配列生成部202は、実行対象プログラムからの配列の新規割り付け要求に応答して、所定のサイズの配列を生成する。また、拡張配列生成部203は、実行対象プログラムからの配列の拡張要求に応答して、所定のサイズよりも大きいサイズの配列を新規に生成し、生成した配列の各要素に元の配列の対応する要素の値をコピーする。配列生成部202及び拡張配列生成部203は配列を生成すると、後述するマーク設定部205を呼び出して生成した配列の先頭を指すポインタを渡す。このとき拡張配列生成部203は更に、配列の拡張要求と共に受け取った拡張すべき元の配列の情報をマーク設定部205へ渡す。本実施例では元の配列の情報は元の配列の先頭を指すポインタとする。
【0042】
マーク設定部205は、配列生成部202または拡張配列生成部203から呼び出されると、サンプリング頻度に基づき、生成された配列をプロファイル対象とするか否かを決定し、プロファイル対象とすると決定した場合に、該配列の先頭を指すポインタにプロファイル対象であることを示すマークを設定する。
【0043】
ここでサンプリング頻度とは、例えば1MB割り付けるたび1つオブジェクトをサンプリングするといったようなサンプリングを行う頻度である。また、上記マークの設定は、一例として、ポインタの空いている下1ビットをフラグとして利用したり、ポインタにオフセットを足してヒープ領域外を指すようにしたりして行ってよい。マーク設定部205はマークを設定すると、後述する初期化部210を呼び出して、マークを付けた配列の先頭を指すポインタと、該当する場合は拡張前の元の配列の先頭を指すポインタとを渡す。
【0044】
初期化部210は、マーク設定部205から呼び出されると、後述する集計部220やプロファイル情報収集部225が、収集したプロファイル情報を所定のデータ構造で所定の領域にそれぞれ格納できるように、予め所定のデータ構造のプロファイル情報を生成し初期化して所定の領域に格納しておく。ここで所定のデータ構造のプロファイル情報は、収集したプロファイル情報を効率よく格納するためのものであり、プロファイル情報収集部225によって利用される配列毎のプロファイル情報構造体と、集計部220によって利用される割付呼び出しコンテキスト毎のプロファイル情報構造体とを含む。
【0045】
初期化部210は、生成した配列毎のプロファイル情報構造体をその配列の先頭を指すポインタをキーとするハッシュ表(以下、「第1ハッシュ表」という)に登録できるように、実行対象のプログラムの実行直前又は直後に第1ハッシュ表を生成して配列毎のプロファイル情報格納部230に格納する。同様に、初期化部210は、生成した割付呼び出しコンテキスト毎のプロファイル情報構造体をその割付呼び出しコンテキストをキーとするハッシュ表(以下、「第2ハッシュ表」という)に登録できるように、実行対象のプログラムの実行直前又は直後に第2のハッシュ表を生成して割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納する。
【0046】
配列毎のプロファイル情報構造体は、その配列の割付呼び出しコンテキストに対応するコンテキスト毎のプロファイル情報構造体へのポインタを格納する第1フィールドと、その配列中でアクセスされた最後の要素のインデックスを格納する第2フィールドとを有する。ここでアクセスされた最後の要素とは、アクセスされた要素の中で配列中最も後ろに位置する要素を意味する。例えばある配列Tの各要素が、T[0」、T[3」、T[9]、T[0}、T[2}の順でアクセスされたとすると、配列中でアクセスされた最後の要素のインデックス値は9である。また、割り付けた配列の割付呼び出しコンテキストとは、配列を割り付けるに至るまでのメソッド間の呼び出し関係をいう。
【0047】
例えば、図5Aに示すプログラムは、図4に示すStringBuilderを呼び出して配列を割り付けるが、この場合の配列の割付呼び出しコンテキストは、1つは、該プログラムが実行され3行目で配列が割り付けられる時点におけるコンテキストである。即ち、図5Aに示すプログラムMySample1.method1は、3行目でStringBuilderのコンストラクタを呼び出し、該コンストラクタは図4に示すプログラムの4行目でメソッドgetCharArrayOfBestSizeを呼び出し、メソッドgetCharArrayOfBestSizeはそのメソッド内で配列を割り付ける。従って、この場合の配列の割付呼び出しコンテキストは、MySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)である。
【0048】
コンピュータは、配列の割付呼び出しコンテキストを任意の表現方法で保持してよい。例えば、配列の割付呼び出しコンテキストを、上記のようにメソッド名を呼び出し順に繋いだ文字列として保持してもよい。或いは、メソッドを示すメソッド情報構造体へのポインタを呼び出し順に繋いでポインタの配列として保持してもよい。
【0049】
割付呼び出しコンテキスト毎のプロファイル情報構造体は、配列毎のプロファイル情報構造体の第2フィールドの値を割付呼び出しコンテキスト毎に集計するためのデータ構造であり、必要に応じて拡張される表形式をとる。表の各エントリは、アクセスされた一番最後の要素のインデックスを格納する第1フィールドと、第1フィールドに格納された値をアクセスされた一番最後の要素のインデックスとし、かつ、その割付呼び出しコンテキストによって割り付けられた配列の数又は頻度を格納する第2フィールドとを含む。図5Bは、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)によって割り付けられた複数の配列についてのプロファイル結果をまとめた表の一例を示す。
【0050】
初期化部210は、マーク設定部205から呼び出されると、受け取ったポインタによりアクセスされる新規に割り付けられた配列に対して、配列毎のプロファイル情報構造体の生成及び初期化を行う。初期化部210は、配列毎のプロファイル情報構造体を生成すると、これをその配列の先頭を指すポインタをキーとして第1ハッシュ表に登録する。このとき初期化部210は、生成した配列毎のプロファイル情報構造体の第2フィールドを値−1で初期化する。初期化部210はまた、配列の生成要求元に応じて、生成した配列毎のプロファイル情報構造体の第1フィールドを初期化する。
【0051】
配列が、新規割り付け要求に応答して配列生成部202により生成されたものである場合、初期化部210は、まず、該配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在するか否かを確認する。対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在する場合、初期化部210は、生成した配列毎のプロファイル情報構造体の第1フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在しない場合、初期化部210は、新たに割付呼び出しコンテキスト毎のプロファイル情報構造体を生成し、これをその配列の割付呼び出しコンテキストをキーとして第2ハッシュ表に登録する。そして初期化部210は、生成した配列毎のプロファイル情報構造体の第1フィールドに、新たに生成した割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。
【0052】
なお、初期化部210は、配列の割付呼び出しコンテキストの情報を、配列を割り付けたスレッドのスタックを辿ることにより取得する。スタックは、完了していないメソッドにそれぞれ対応する1以上のフレームから構成されており、各フレームには対応するメソッドの状態情報(メソッド名を含む)が格納されている。スタックトップのフレームは現在実行中のメソッドのためのものであり、該メソッドを呼び出したメソッドのフレームがその下にある。このようにスタックには、1以上のフレームがそれぞれ対応するメソッドの呼び出し順に従って下から上へ積まれている。スタックを辿る際は、一番下のmainメソッドまで辿ってもよく、或いは、予め定めた段数(例えば20段)だけ辿ってもよい。初期化部210はコンテキスト情報を取得すると、これをキーとして第2ハッシュ表から割付呼び出しコンテキスト毎のプロファイル情報構造体を取得する。ヒットしない場合、生成した配列に対応するコンテキスト毎のプロファイル情報構造体は未だ生成されていないことを意味する。
【0053】
一方、配列が配列の拡張要求に応答して配列拡張生成部203により生成された場合、初期化部210は、マーク設定部205から受け取った拡張前の元の配列の先頭を指すポインタをキーとして第1ハッシュ表から配列毎のプロファイル情報構造体を取得する。そして初期化部210は、その第1フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを読み出し、これを生成した配列毎のプロファイル情報構造体の第1フィールドに設定する。
【0054】
呼び出し設定部215は、マークを付されたポインタを介して配列へのアクセスがあるとプロファイラ130が呼び出されるように、プロファイラ130の呼び出しを設定する。該設定には、実行対象のプログラムのコード(中間コード)を書き換えて行う方法と、ページ保護機構を利用する方法とがある。呼び出し設定部215は後者を採用し、前者については、後述するコード書き換え部245が採用する。従って、調整装置200は、呼び出し設定部215と後述するコード書き換え部245のうち少なくとも一方を含めばよいことに留意されたい。
【0055】
ページ保護機構を利用する呼び出し設定部215は、より具体的には、プロファイル対象であることを示すマークを付されたポインタが指す先のページを読み書き禁止に設定し、該ポインタを介して配列がアクセスされるとシグナルハンドラが呼び出されるようにする。この場合、シグナルハンドラがプロファイラ130としてプロファイル情報の収集を行う。なお、呼び出し設定部215は、上記プロファイラ130の呼び出し設定を、例えば実行対象プログラムの実行開始前、又は直後に行う。
【0056】
プロファイル情報収集部225は、プロファイラ130又はシグナルハンドラの呼び出しに応答して、即ち、プロファイル対象に設定された配列へのアクセスを検出することに応答して、該アクセスに関するプロファイル情報の収集を行う。プロファイル情報収集部225は、収集したプロファイル情報を、対応する配列毎のプロファイル情報構造体に格納する。より具体的には、プロファイル情報収集部225は、アクセスされた配列の先頭を指すポインタをキーにして配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を得る。そしてプロファイル情報収集部225は、取得した配列毎のプロファイル情報構造体の第2フィールドの値を読み出し、上記配列の現在アクセスされた要素のインデックスと比較する。現在のインデックスのほうが大きい場合、プロファイル情報収集部225は、現在のインデックスで上記第2フィールドの値を更新する。
【0057】
集計部220は、ガーベジコレクションにおけるプロファイル対象の配列の破棄処理に応答して、対応する配列毎のオブジェクト情報構造体の記録を、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体に集計する。具体的には、集計部220はまず、破棄対象の配列のポインタをキーとして、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表から対応する配列毎のオブジェクト情報構造体を取得する。そして集計部220は、その第1フィールドのポインタ値から、割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体である表の中に、取得した配列毎のオブジェクト情報構造体の第2フィールドの値に対応するエントリが既に存在しているか否かを確認する。対応するエントリが既に存在する場合、集計部220は、該エントリの第2フィールドの頻度値を1増加する。対応するエントリが存在しない場合、集計部220は、取得した割付呼び出しコンテキスト毎のプロファイル情報構造体の表にエントリを1つ追加し、そのエントリの第1フィールドに、取得した配列毎のオブジェクト情報構造体の第2フィールドの値を設定し、そのエントリの第2フィールドに、頻度として値1を設定する。
【0058】
インライン展開部235は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、上記中間コードの部分に含まれる配列の割付呼び出しコンテキストについて十分なプロファイル情報が集まっていることを条件に、そのコンテキストをインライン展開する。例えばインライン展開部235は、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体の全エントリについての頻度の合計が予め定めた閾値よりも大きい場合に、該コンテキストについて十分なプロファイル情報が集まっていると判断してよい。インライン展開部235はインライン展開処理の後、後述するサイズ決定部240を呼び出す。
【0059】
サイズ決定部240は、インライン展開部235から呼び出されると、インライン展開された配列の割付呼び出しコンテキストに対し、該コンテキストに対して収集されたプロファイル情報に基づいて該コンテキストが割り付ける配列の初期サイズを決定する。なお、収集されたプロファイル情報とは、上記コンテキストをキーとしてコンテキスト毎のプロファイル情報格納部223に格納される第2ハッシュ表を引いて取得される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体である。好ましくは、サイズ決定部240は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を配列の割り付け初期サイズとする。これに代えて、サイズ決定部240は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を配列の割り付け初期サイズとしてもよい。
【0060】
ここで図5A〜図5C及び図6A〜図6Cを参照して、インライン展開部235のインライン展開処理と、サイズ決定部240のサイズ決定処理を具体的に説明する。上述したように図5Aに示すプログラムは、図4に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図5Bに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。なお、十分なプロファイルが集まっていると判断するための予め定められた閾値を20とする。
【0061】
すると、図5Bに示す表の頻度の合計は25であるため、インライン展開部235は、上記コンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部235は、図3Bに示すメソッドgetCharArrayOfBestSize(int)の定義を、図5Aに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図5Cに示すコードを得る。このときサイズ決定部240は、図5Bに示す表において最大のインデックス値が1であることから、配列のサイズは要素数2で十分であると判定し、配列の割り付け初期サイズを2に決定する。なお、図4に示すように、当初配列の初期サイズは16であったことに留意されたい。
【0062】
図6に示すプログラムもまた、図4に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキスト、MySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図6Bに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。図6Bに示す表の頻度の合計は24であるため、インライン展開部235は、上記コンテキストMySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部235は、図3Bに示すメソッドgetCharArrayOfBestSize(int)の定義を、図6Aに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図6Cに示すコードを得る。このときサイズ決定部240は、図6Bに示す表において最大のインデックス値が1659であることから、配列のサイズは要素数1660で十分であると判定し、配列の割り付け初期サイズを1660に決定する。なお、図4に示すように、当初配列の初期サイズは16であったことに留意されたい。
【0063】
コード書き換え部245は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、プロファイル対象であることを示すマークを付されたポインタを介して配列へのアクセスがあるとプロファイラ130が呼び出されるように、上記中間コードの部分に含まれるプロファイル対象の配列へのアクセス命令に対してプロファイラ130の呼び出しを設定する。上述したように、コード書き換え部235は上記プロファイラ130の呼び出しの設定をコードの書き換えによって行う。より具体的には、コード書き換え部235は、実行対象のプログラムに含まれる全てのポインタ経由の配列へのアクセス命令の前に、プロファイル対象であることを示すマークの有無を判定するコードと、マークが付されているとの判定結果に対してプロファイラ130を呼び出すコードとを挿入する。
【0064】
次に図7乃至図11を参照して、調整装置200の動作を説明する。図7は、本実施形態に係る調整装置200の動作フローの一例を示す。図8は、図7に示すステップ740の実行部120(初期化部210)による処理の詳細な動作フローの一例を示す。図9は、図7に示すステップ720のメモリ管理部125による処理の詳細な動作フローの一例を示す。図10は、図7に示すステップ750のプロファイラ130による処理の詳細な動作フローの一例を示す。図11は、図7に示すステップ760の動的コンパイラ135による処理の詳細な動作フローの一例を示す。
【0065】
図7に示す調整装置200の動作フローはステップ700から開始し、実行部120は、メモリ管理部120を呼び出して、プロファイラ130の呼び出しのためのページ保護機構を設定させる。続いて実行部120は、実行対象プログラム(中間コード)の実行を開始して、次に実行しようとする命令を取得する(ステップ705)。続いて実行部120は、実行しようとする現在の命令がオブジェクトを割り付けるか否かを判定する(ステップ710)。現在の命令がオブジェクトを割り付けると判定した場合(ステップ710:YES)、実行部120はガーベジコレクションが必要であるか否かを判定する(ステップ715)。ガーベジコレクションが必要であると判定した場合(ステップ715:YES)、実行部120は、メモリ管理部125を呼び出して処理を実行させる。メモリ管理部125による処理の詳細は、図9を参照して後述する。
【0066】
メモリ管理部125による処理の後、続いて実行部120は、実行する命令が所定サイズの配列を割り付ける第1のAPIによる配列割付の命令であり、かつ、該命令により割り付ける配列をサンプリング頻度に基づきサンプリング対象とすべきか否かを判定する(ステップ725)。第1のAPIによる配列割付の命令でない場合、又は第1のAPIによる配列割付の命令であるがサンプリング対象としないと決定した場合(ステップ725:NO)、処理はステップ730へ進み、続いて実行部120は、実行する命令が、第2引数で指定された元の配列を拡張する第2のAPIによる拡張配列の割付命令であり、かつ、第2引数で指定された元の配列の先頭を指すポインタにサンプリング対象であることを示すマークが付いているか否かを判定する。第2のAPIによる配列割付の命令でない場合、又は第2のAPIによる配列割付の命令であるが、受け取った上記ポインタにマークが付いてない場合(ステップ730:NO)、処理はステップ745へ進む。なお、ステップ725において少なくとも第1のAPIによる配列割付の命令であると判定した場合、又はステップ730において少なくとも第2のAPIによる拡張配列の割付命令であると判定した場合、実行部120はそれぞれ要求される配列を割り付ける。
【0067】
ステップ725またはステップ730において肯定的な判定結果が得られた場合(ステップ725:YESまたはステップ730:YES)、処理はステップ735へ進み、実行部120は、ステップ725またはステップ730で割り付けた配列の先頭を指すポインタに、プロファイル対象であることを示すマークを付ける。続いて実行部120は、プロファイル対象とした配列に対して初期化処理を行う(ステップ740)。初期化処理の詳細は図8を参照して後述する。
【0068】
ステップ740の後、ステップ710において現在の命令がオブジェクトを割り付けないと判定した場合(ステップ710:NO)、又はステップ730において否定的な判定結果が得られる場合(ステップ730:NO)、処理はステップ745へ進み、実行部11520は、現在の命令はサンプリングされた、即ちプロファイル対象の配列へのアクセス命令であるか否かを判定する。プロファイル対象の配列へのアクセス命令であると判定した場合(ステップ745:YES)、実行部120はプロファイラ130を呼び出して処理を実行させる(ステップ750)。プロファイラ130による処理の詳細は、図10を参照して後述する。
【0069】
ステップ750の後、又はステップ745において現在の命令がプロファイル対象の配列へのアクセス命令ではないと判定した場合(ステップ745:NO)、処理はステップ755へ進み、実行部120は、次に実行する中間コードの部分を動的にコンパイルする必要があるか否かを判定する。動的コンパイルが必要であると判定した場合(ステップ755:YES)、実行部120は動的コンパイラ135を呼び出して処理を実行させる(ステップ760)。動的コンパイラ135による処理の詳細は、図11を参照して後述する。
【0070】
ステップ760の後、又はステップ755において動的コンパイルが必要でないと判定した場合(ステップ755:NO)、処理はステップ765へ進み、実行部120は、実行対象プログラムの実行が終了したか否かを判定する。実行対象プログラムの実行がまだ終了していない場合(ステップ765:NO)、処理はステップ705へ戻る。一方、プログラムの実行が終了した場合(ステップ765:YES)、調整装置200の動作フローは終了する。
【0071】
図8に示す初期化210による処理の動作フローはステップ800から開始し、初期化210は、図7に示すステップ735においてそのポインタにマークを付けた配列に対して、配列毎のプロファイル情報構造体を生成し、その第2フィールドを値―1で初期化する。続いて初期化部210は、上記配列の割付が、第2引数で指定された元の配列を拡張する第2のAPIによる割付であったか否かを判定する(ステップ805)。第2のAPIによる割付でなかった場合(ステップ805:NO)、続いて初期化部210は、上記配列を割り付けたスレッドのスタックを辿って、上記配列を割り付けた割付呼び出しコンテキストを取得する(ステップ810)。続いて初期化部210は、上記配列を割り付けた割付呼び出しコンテキストをキーとして割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納される第2ハッシュ表を引き、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在するか否かを判定する(ステップ815)。
【0072】
対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在しない場合(ステップ815:NO)、初期化部210は、上記配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を新たに生成し、該コンテキストをキーとして第2ハッシュ表に登録する(ステップ820)。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在する場合(ステップ815:YES)、またステップ820の後、初期化部210は、ステップ800において生成した配列毎のプロファイル情報構造体の第1フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。
【0073】
一方ステップ805において、上記配列の割付が第2のAPIによる割付であった場合(ステップ805:YES)、初期化部210は、第2のAPIの第2引数で指定された拡張前の元の配列のポインタをキーとして配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する。そして初期化部210は、取得した配列毎のプロファイル情報構造体の第1フィールドに格納された割付呼び出しコンテキスト毎の構造体へのポインタを、ステップ800で生成した配列毎のプロファイル情報構造体の第1フィールドに設定する。ステップ825又はステップ835から処理はステップ830へ進み、初期化部210は、ステップ800で生成した配列毎のプロファイル情報構造体を、その配列の先頭を指すポインタをキーとして配列毎のプロファイル情報格納部230内の第1ハッシュ表に登録する。その後処理は終了する。
【0074】
図9に示すメモリ管理部125による処理の動作フローはステップ900から開始し、メモリ管理部125は、ヒープ領域に生成されている使用中の全オブジェクトを検出するために、オブジェクト間のポインタによる参照関係を示すツリー構造をスキャンし、使用中のオブジェクトを指す全ポインタについて以下の一連の処理を繰り返す。メモリ管理部125はまず、現在のポインタに対して、通常のガーベジコレクション処理を実行する(ステップ905)。通常のガーベジコレクション処理のアルゴリズムは周知の技術であり、本発明の要旨ではないので詳細な説明は省略する。
【0075】
続いてメモリ管理部125は、ステップ905におけるガーベジコレクション処理で配列オブジェクトを破棄すると決定し、かつ、破棄すると決定した配列オブジェクトに対応する配列毎のプロファイル情報構造体が、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表内に存在するか否かを判定する(ステップ910)。否定的な判定結果が得られた場合(ステップ910:NO)、現在のポインタについての処理は終わる。一方、肯定的な判定結果が得られた場合(ステップ910:YES)、メモリ管理部125は、破棄する配列に対応する配列毎のプロファイル情報構造体の第1フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを取得し(ステップ915)、ポインタが指す表に、破棄する配列に対応する配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値に対応するエントリが存在するか否かを判定する(ステップ920)。
【0076】
対応するエントリが存在すると判定した場合(ステップ920:YES)、メモリ管理部125は、
該エントリの第2フィールドの頻度値を1増やす(ステップ925)。一方、対応するエントリが存在しないと判定した場合(ステップ920:NO)、メモリ管理部125は、ステップ915で取得したポインタが指す表にエントリを1つ追加し、該エントリの第1フィールドに、破棄する配列に対応する配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値を、該エントリの第2フィールドに、頻度値1をそれぞれ設定する(ステップ930)。
【0077】
ステップ925又はステップ930の後、メモリ管理部125は、破棄する配列を割り付けた割付呼び出しコンテキストについて十分なプロファイルが集まったと判定することを条件に、動的コンパイラ135を呼び出して動的コンパイルを行わせる。動的コンパイラ135による動的コンパイル処理の詳細は図11を参照して後述する。続いてメモリ管理部125は、破棄する配列に対応する配列毎のプロファイル情報構造体を、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表から削除する(ステップ940)。使用中のオブジェクトを指す全ポインタについて上記一連の処理が行われると、処理は終了する。
【0078】
図10に示すプロファイラ130による処理の動作フローはステップ1000から開始し、プロファイラ130は、プロファイラ130呼び出しの要因となった現在のオブジェクト・アクセス命令における配列をアクセスする。続いてプロファイラ130は、アクセスした配列の先頭を指すポインタをキーとして、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する(ステップ1005)。続いてプロファイラ130は、現在のオブジェクト・アクセス命令によりアクセスされる配列の要素のインデックス値と、取得した配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値とを比較し、アクセスしようとする配列の要素のインデックス値が大きい場合、該インデックス値で上記第2フィールドの値を更新する(ステップ1010)。そして処理は終了する。
【0079】
図11に示す動的コンパイラ135による処理の動作フローはステップ1100から開始し、動的コンパイラ135は、次に実行しようとする実行対象プログラムのコード部分を、中間コード(バイトコード)格納部115から読み込む。続いて動的コンパイラ135は、コンパイル対象の上記コード部分に含まれる割付呼び出しコンテキストについて、十分なプロファイルがコンテキスト毎のプロファイル情報格納部223に収集されていることを条件に、上記コンテキストをインライン展開する(ステップ1105)。
【0080】
続いて動的コンパイラ135は、インライン展開された割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体に記録されたインデックスのうち最大のインデックスの値を、配列の割付初期サイズとしてインライン展開したコードに埋め込む(ステップ1110)。続いて動的コンパイラ135は、上記コード部分の上記割付呼び出しコンテキスト以外の部分について最適化処理を行う(ステップ1115)。最適化の種類は複数存在し、それぞれのアルゴリズムは既知の技術であり本発明の要旨でもないので、ここでは詳細な説明を省略する。
【0081】
続いて動的コンパイラ135は、コンパイル対象の上記コード部分に対し、プロファイラ130呼び出しのためのコードの書き換えを行う(ステップ1120)。続いて、動的コンパイラ135は、上記コード部分の上記割付呼び出しコンテキスト以外の部分をコンパイルし、ネイティブコードを生成する(ステップ1125)。そして処理は終了する。
【0082】
[実験]
1.実装
動作周波数最大4.7GHzのRISCプロセッサ(クアッドコア、2スレッドのSMTエンジン搭載のPOWER6(商標))と利用した各ベンチマークが必要とする最低のヒープメモリ量の2倍のヒープメモリ量をハードウエアとして備え、オペレーティング・システムとしてLinux(商標)2.6.18を用いるIBM社のJava(登録商標)仮想マシンに、本発明の実施形態に係る調整プログラムを実装した。なお、実装した調整プログラムでは、8MB割り付ける毎に1つの配列をサンプリングするサンプリング頻度を用いた。また、ベンチマークDaCapoの中からオブジェクトを多く割り付ける8つのベンチマークプログラム(fop、jython、lusearch、pmd、sunflow、tomcat、xalan、Geo.mean)を選択した。また、Java(登録商標)標準ライブラリのjava.lang.StringBuilder、java.io、BufferedReader、lusearchベンチマークの2つのクラス、xalaベンチマークの3つのクラスの各々におけるは配列の割付を、本発明で新たに導入したAPIを用いて行うように書き換えた。
【0083】
2.実験結果
図12は、速度向上率についての実験結果を示す。図12に示されるように、ベンチマークによっては最大300%以上(4倍以上)の性能向上が見られた。なお、性能低下は、最大でも2.2%であり、これはアクセスプロファイラのオーバーヘッドによるものである。
【0084】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【0085】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【技術分野】
【0001】
本発明は、配列の初期サイズを調整する技術に関し、より詳細には、配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法に関する。
【背景技術】
【0002】
従来、配列の適切なサイズが前もって分からない場合、最初は小さいサイズの配列を割り付け、必要に応じて拡張したサイズの配列を割り付けるプログラミングパターン(以下、「配列拡張パターン」という)が利用されている。配列拡張パターンの一例を図13に示す。図13に示すStringBuilderクラスでは、最初、コンストラクタにより要素数16の配列char[]が割り付けられる(図13の(a)を参照)。そして、メソッドappendにより配列char[]の要素に値が設定される際に、if文で配列の拡張が必要であるか否かが判定され、if文の条件が真となる場合に倍のサイズの配列newchar[]が新たに割り付けられる(図13の(b)を参照)。新たに割り付けた配列newchar[]の各要素には元の配列char[]の各要素の値がコピーされる。
【0003】
しかしながら上記プログラミングパターンの利用には、配列の初期サイズはしばしば大き過ぎたり小さ過ぎたりするため実行に無駄が生じるという問題がある。特に配列の寿命が短く頻繁に割り付けられる場合には、ゼロ初期化やコピーのオーバーヘッドが大きい。
【0004】
可変長オブジェクトの初期サイズの選択方法に関する従来技術として非特許文献1が存在する。非特許文献1は、可変長オブジェクトとしてコレクションオブジェクトに着目し、以下の初期サイズ選択方法を開示する。1.コレクションオブジェクトを割り付けるときに呼び出しコンテキストを取得してこれを割り付けたコレクションオブジェクトのオブジェクト情報構造体に記録する。2.コレクションオブジェクトに対するメソッド呼び出しの種別や回数を対応するオブジェクト情報構造体に記録する。3.コレクションオブジェクトを破棄する際に、対応するオブジェクト情報構造体の記録を割付呼び出しコンテキスト毎の情報構造体に集計する。4.プログラム実行終了後、集計結果に基づきコレクションオブジェクトの適切な初期サイズをプログラマに提案する。
【0005】
そこで上記非特許文献1の技術を配列の初期サイズの決定処理に適用することを考える。すると、図13に示す(a) 、(b)の2箇所で割り付けられた配列へのアクセス情報及び配列の割付呼び出しコンテキスト情報を、それぞれ対応するオブジェクト情報構造体に記録し、記録した情報を割付呼び出しコンテキスト毎の情報構造体に集計することで、(a) 、(b)の2箇所でそれぞれ割り付けられる配列について適切な初期サイズをプログラマに提案することが可能となる。しかしこの場合、プロファイル情報は割付呼び出しコンテキスト単位でしかまとめることができないので、 (b)で割り付けられた配列のプロファイル情報を(a)で割り付けられた配列の割付呼び出しコンテキストにフィードバックすることができない。結果、(a) 、(b)の2箇所で大きすぎるサイズの配列を割り付けることはなくなるが、配列の拡張処理をなくしたり、その回数を減らしたりすることはできない。
【0006】
以下、本発明の先行技術調査において見つかった他の文献について説明する。
【0007】
特許文献1は、インライン割付元の可変長インスタンスの大きさを、実行プロファイルを使うなどの方法により予測し、例えば、配列の大きさを4と予測した場合に、実行時に定まった配列の長さが4以下である場合には配列をインライン割付け先のインスタンスの中にインライン割付けし、4を超える場合には、配列をインライン割付け先のインスタンスとは別個に割付ける技術を開示する。しかしながら特許文献1の技術は、各割り付け場所で割り付けられる可変長オブジェクトのサイズをプロファイルしており、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたか否かについては全く考慮に入れておらず、従って、特許文献1の技術は配列拡張パターンを最適化することはできない。
【0008】
特許文献2は、プログラム実行時にメモリ容量変更の必要がある場合、環境設定ファイルを参照し、この環境設定ファイルの最大配列長、あるいは最小配列長と実行マシンの実メモリにより、プログラム中で必要とする配列長の最適な値を算出する手段と、次にソースプログラム中の配列長を変更し、再コンパイルして、実行する手段とを備えたことを特徴とする配列領域確保装置を開示する。しかしながら、
特許文献2の技術は、プログラム中で割り付ける配列のサイズを、実行するマシンが持つメモリの大きさに応じて調整するものであり、可変長オブジェクトの中のどの要素が実際に実行中にアクセスされたかに応じて調整するものではなく、従って、特許文献2の技術は配列拡張パターンを最適化することはできない。
【0009】
特許文献3は、配列のデータ領域の各行を指し示すデータ領域へのポインタを含むデータ領域へのポインタ配列の先頭を指すポインタ配列へのポインタを格納するメモリ管理テーブルおよび前記メモリ管理テーブルの大きさをそれぞれプライベートなメンバ変数として実装し、かつ、前記メモリ管理テーブルを初期化する初期化関数コンストラクタ、配列の領域の確保・割り当てを行うメモリ確保関数、領域の解放を行うためのメモリ解放関数、前記データ領域および前記データ領域へのポインタ配列を前記メモリ解放関数を使用して解放する解放関数デストラクタをそれぞれパブリックなメンバ関数として実装する、第1のC++言語における配列の領域の動的確保・解放方法を開示する。しかしながら、特許文献3の技術は、多次元配列で高次元のサイズをコンパイル時定数でなく実行時変数とするためのものであり、かかる手法では割り付けた配列が実行時に拡張されることはない。そのため、特許文献3の技術は配列拡張パターンを最適化することはできない。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開2003−0271393号公報
【特許文献2】特開1993−0204616号公報
【特許文献3】特開2000−0066900号公報
【非特許文献】
【0011】
【非特許文献1】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
【発明の概要】
【発明が解決しようとする課題】
【0012】
この発明は、上記の問題点を解決するためになされたものであって、配列拡張パターンにおいて配列の初期サイズを実行環境において動的に調整するための情報処理装置、調整プログラム及び調整方法を提供することを目的とする。
【課題を解決するための手段】
【0013】
本発明は、上記課題を解決するために、以下の特徴を有する配列の初期サイズを動的に調整する調整プログラムを提供する。該プログラムはコンピュータに、(a)実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、(b)前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、(c)前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、(d)各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、(e)前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップとを実行させる。
【0014】
好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む。
【0015】
また好ましくは、各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値である。そしてステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む。
【0016】
また好ましくは、配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられる。そしてステップ(b)は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む。
【0017】
また好ましくは、ステップ(d)の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる。
【0018】
以上、配列の初期サイズを動的に調整する調整プログラムとして本発明を説明した。しかし、本発明は、上記調整プログラムをインストールしたコンピュータにおいて実行される、配列の初期サイズを動的に調整する調整方法として把握することもできる。また、本発明は、上記調整プログラムをインストールすることにより実現される、配列の初期サイズを動的に調整するための情報処理装置(以下、「調整装置」という)として把握することもできる。
【発明の効果】
【0019】
本発明では、サイズ拡張後の配列のプロファイル情報を記録する際に、これをサイズ拡張後の配列の割付呼び出しコンテキストではなく、サイズ拡張前の元の配列の割付呼び出しコンテキストに関連付ける。結果、サイズ拡張後の配列についてのプロファイル情報を、拡張前の元の配列の割付呼び出しコンテキストにフィードバックすることが可能となり、拡張処理を減らすことのできる配列の適切な初期サイズを実行環境において動的に決定することが可能となった。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【0020】
【図1A】本発明の実施形態に係るコンピュータ50のハードウェア構成の一例を示す。
【図1B】本発明の実施形態に係るコンピュータ50のソフトウェア構成の一例を示す。
【図2】本発明の実施形態に係る調整装置200の機能構成を示す。
【図3A】標準ライブラリの一部として提供される新APIの一例を示す。
【図3B】getCharArrayOfBestSize()の実行時コンパイルされたコードの一例を示す。
【図3C】extendCharArray ()の実行時コンパイルされたコードの一例を示す。
【図4】図3Aに示す新APIを用いたStringBuilderの一例を示す。
【図5A】図4に示すStringBuilderを用いて配列を生成するプログラムの一例を示す。
【図5B】図5Aの3行目で割り付けられる配列についてのプロファイル結果の一例を示す。
【図5C】図5Bに示すプロファイル結果を参照してインライン展開されたコードを示す。
【図6A】図4に示すStringBuilderを用いて配列を生成するプログラムの他の例を示す。
【図6B】図6Aの3行目で割り付けられる配列についてのプロファイル結果の一例を示す。
【図6C】図6Bに示すプロファイル結果を参照してインライン展開されたコードを示す。
【図7】本実施形態に係る調整装置200の動作フローの一例を示す。
【図8】図7に示すステップ740の初期化部210による処理の詳細な動作フローの一例を示す。
【図9】図7に示すステップ720のメモリ管理部125の詳細な動作フローの一例を示す。
【図10】図7に示すステップ750のプロファイラ130による処理の詳細な動作フローの一例を示す。
【図11】図7に示すステップ760の動的コンパイラ135による他の処理の詳細な動作フローの一例を示す。
【図12】速度向上率に関する実験結果を示す。
【図13】従来の配列拡張パターンを示すプログラムの一例を示す。
【図14】アノテーションで割付場所を指定するAPIを用いたプログラムの一例を示す。
【図15】ネイティブライブラリとして提供される新たなAPIの一例を示す。
【発明を実施するための形態】
【0021】
以下、本発明の実施形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【0022】
図1は、本発明の実施形態による情報処理装置としてのコンピュータ50のハードウェア構成の一例を示した図である。コンピュータ50は、バス2に接続されたメインCPU(中央処理装置)1とメイン・メモリ4を含んでいる。CPU1は好ましくは、32ビット又は64ビットのアーキテクチャに基づくものであり、例えば、インテル社のCore i(商標)シリーズ、Core 2(商標)シリーズ、Atom(商標)シリーズ、Xeon(商標)シリーズ、Pentium(登録商標)シリーズ、Celeron(登録商標)シリーズ、AMD社のPhenom(商標)シリーズ、Athlon(商標)シリーズ、Turion(商標)シリーズ又はSempron(商標)が使用されうる。
【0023】
またハードディスク装置13、30、及びCD−ROM装置26、29、フレキシブル・ディスク装置20、MO装置28、DVD装置31のようなリムーバブル・ストレージ(記録メディアを交換可能な外部記憶システム)がフレキシブル・ディスクコントローラ19、IDEコントローラ25、SCSIコントローラ27などを経由してバス2へ接続されている。フレキシブル・ディスク、MO、CD−ROM、DVD−ROMのような記憶メディアが、リムーバブル・ストレージに挿入される。
【0024】
これら記憶メディアやハードディスク装置13、30、ROM14には、オペレーティング・システム、J2EEなどのJava(登録商標)処理環境、Java(登録商標)アプリケーション、Java(登録商標)仮想マシン(VM)、Java(登録商標)実行時(JIT)コンパイラを提供するプログラム、その他のプログラム及びデータが、メイン・メモリ4にロード可能に記憶されている。更に、上記記憶メディアやハードディスク装置13、30、ROM14には、オペレーティング・システムと協働してCPU1に命令を与え、本発明を実施するためのコンピュータ・プログラムを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ50にインストールされ、コンピュータ50を本発明の実施形態による調整装置200として機能させる調整プログラムやデータを記録することができる。
【0025】
上記調整プログラムは、配列生成モジュールと、拡張配列生成モジュールと、マーク設定モジュールと、初期化モジュールと、呼び出し設定モジュールと、集計モジュールと、プロファイル情報収集モジュールと、インライン展開モジュールと、サイズ決定モジュールと、コード書き換えモジュールとを含む。これらプログラム及びモジュールは、CPU1に働きかけて、コンピュータ50を、各々後述する配列生成部202と、拡張配列生成部203、設定部205と、初期化部210と、呼び出し設定部215と、集計220と、プロファイル情報収集部225と、インライン展開部235と、サイズ決定部240と、コード書き換え部245としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【0026】
コンピュータ50は、キーボード/マウス・コントローラ5を経由して、キーボード6やマウス7のような入力デバイスからの入力を受ける。コンピュータ50は、オーディオコントローラ21を経由して、マイク24からの入力を受け、またスピーカー23から音声を出力する。コンピュータ50は、視覚データをユーザに提示するための表示装置11に、グラフィックスコントローラ10を経由して接続される。コンピュータ50は、ネットワーク・アダプタ18(イーサネット(登録商標)・カードやトークンリング・カード)等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【0027】
以上の説明により、コンピュータ50は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【0028】
図1Bは、本発明を実現するソフトウェアの構成を示すブロック図である。同図において、オペレーティング・システム105は、CPUやメモリを資源として管理し、時分割によるマルチスレッドの機能を実現する。仮想マシン110は、アプリケーション140とオペレーティング・システム105とのインタフェースを行うソフトウェアであり、アプリケーション140から見て仮想マシン以下の階層全体を例えばJava(登録商標)仮想マシン(Virtual Machine)として作用させる。仮想マシン110は、プログラムがバイトコード等の中間コードで与えられるときこれを解釈する実行部(インタープリタ)120と、その解釈に応じて呼び出されるプロファイラ130と、メモリ管理部125とを含む。また、仮想マシン110はJITコンパイラ等の動的コンパイラ135を含み、バイトコードを実行時に動的に機械語にコンパイルしてネイティブコードを生成し、プログラムの実行を高速化する。なお、上記中間コードはAPIの記述を含みうる。実行部120は中間コード内にAPIの記述を検出すると、ライブラリからそのAPIの機能を呼び出して実行する。
【0029】
ところで本発明は、配列拡張パターンにおける配列の初期サイズをプロファイル結果に基づいて実行時に動的に調整することを目的とするが、配列の初期サイズをコンピュータの演算処理により勝手に変更するとプログラムの意味が変ってしまう場合がある。そのため、配列の初期サイズを変更してもプログラムの意味が変らない箇所を見つけ、当該箇所に対して最適化を行う必要ある。しかし、そのような箇所を動的コンパイラ135の解析のみで検出しようとすると、重い手続き間解析が必要となり現実的でない。そこで本発明では、そのような箇所をプログラマが最適化対象として簡単に指定できるように、配列を割り付けるためのAPIを新たに導入する。プログラマは、配列拡張パターンの配列割り付け箇所を実行環境(仮想マシン105)が特別扱いできるように、new演算子を用いて配列を割り付ける代わりに、新たに定義されたAPIを用いて配列を割り付ける。
【0030】
新たに導入するAPIは、標準ライブラリの一部として提供し、プリミティブ型の配列(Java(登録商標)言語の場合、boolean[]、byte[]、char[]、Object[]型などの配列)毎に、初期サイズの配列を割り付けるメソッド(特許請求の範囲における「第1のAPI」に対応)、サイズ拡張した配列を割り付けるメソッド(特許請求の範囲における「第2のAPI」に対応)の2種類を用意する。各メソッドの仕様は、「第1引数で指定されたサイズを参照して何らかのサイズの配列を返す」というものである。但し、サイズ拡張した配列を割り付けるメソッドに対しては、更に、サイズ拡張前の元の配列を指定する第2引数を用意し、サイズ拡張した配列についてのプロファイル結果を元の配列の割付呼び出しコンテキストにフィードバックできる仕組みを組み込む。フィードバックの仕組みの詳細は後述する。
【0031】
図3Aに、文字型の配列に対して新たに導入するAPIの例を示す。図3Aに示す例では、新たなAPIを、java.lang.Systemクラスにstaticメソッドとして追加している。図3Aにおいて、char[] getCharArryOfBestSize(int)は、初期サイズの配列を割り付けメソッドであり、char[] extendCharArry(int, char[])は、サイズ拡張した配列を割り付けるメソッドである。各メソッドは実行時に動的コンパイラ135によって動的コンパイルされない限りは単に指定されたサイズの配列を返す。
【0032】
そして、メソッドgetCharArryOfBestSizeは、実行時に動的コンパイラ135によって、図3Bに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドgetCharArryOfBestSizeは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。プロファイル情報格納領域には、割り付けた配列の割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。
【0033】
同様にメソッドextendCharArryは、実行時に動的コンパイラ135によって、図3Cに示すアクセス・プロファイラを用いるコードに変換される。即ち、メソッドextendCharArryは、実行時コンパイルによって、文字型配列の生成及び初期化に加えて、割り付けた配列をサンプリングするか否かを判定し、サンプリングすると決定した場合に該配列をアクセス・プロファイラによるプロファイルの対象とするコードに変換される。該コードは、プロファイル対象の配列にプロファイル対象であることを示すマークを付ける処理と、プロファイル情報格納領域を確保する処理とを含む。但し、拡張した配列を割り付けるメソッドextendCharArryでは、プロファイル情報格納領域には、第2引数で指定された元の配列を割り付けた割付呼び出しコンテキスト情報が記録され、該領域に後に格納されるプロファイル情報と関連付けられる。
【0034】
上記新たなAPIを用いるためには、プログラマはこれまで直接new演算子を用いて配列を生成した箇所を、新たなAPIのメソッドの呼び出しに書き換えるだけでよい。図4に示すプログラムは、図13に示すStringBuilderのプログラムを、新たなAPIを用いて書き換えたものである。図13に示すnew演算子を用いて初期サイズ16の配列を割り付ける箇所(a)は、図4に示すメソッドgetCharArryOfBestSizeの呼び出し箇所(a‘)に対応する。また、図13に示すnew演算子を用いて倍のサイズの配列を割り付ける箇所(b)は、図4に示すメソッドextendCharArryの呼び出し箇所(b’)に対応する。
【0035】
このように、新たに導入するAPIは、実行時に動的コンパイルされない限りは単に指定されたサイズの配列を返すだけのものとし、APIのユーザが実装に依存したコードを書かないように、APIのユーザからは各メソッドの実装が見えないようにしなければならない。例えば、配列の初期サイズを変更してもプログラムの意味が変らない箇所をAPIで指定する別のやり方として、new文にアノテーションをつけるだけのAPIを利用する方法が考えられる。しかしながら、このようなAPIでは本発明は正しく動作しない。この理由を、本発明が正しく動作するためにAPIに課される設計上の3つの要件と共に説明する。
【0036】
まず1つ目は、Java(登録商標)言語の意味を変えないという要件である。例えば図14に示すプログラムのように、アノテーションで割り付け場所を指定する手法はJava(登録商標)言語の意味を変えてしまう(Java(登録商標)言語では文にアノテーションを付けることはできないが、説明の便宜上付けられると仮定する。)。なぜならば、本発明を適用すると例えば図14の(a)ではプロファイル結果に基づき16要素より大きかったり小さかったりする配列charが生成されうるが、これはJava(登録商標)言語の仕様上正しくないからである。従って、図3Aを参照して説明した2つのAPIのように、配列をnewする部分をメソッド呼び出しでラップしてJava(登録商標)プログラマから見えなくするAPIを用意する必要がある。
【0037】
2つ目は、移植性が高いという要件である。例えば図15に示すように、ネイティブライブラリとしてAPIを提供する手法は、異なるCPUやJava(登録商標)VM間での移植性が低い。従って、図3Aを参照して説明した2つのAPIのように、単に指定されたサイズの配列を返すだけのデフォルトの実装を提供するAPIを用意する必要がある。
【0038】
3つ目は、配列を拡張した際に拡張した配列のプロファイル情報を拡張前の元の配列を割り付けた割付呼び出しコンテキストにフィードバックできるという要件である。上述したように、本実施例では、サイズ拡張した配列を割り付けるメソッドが、サイズ拡張前の元の配列を指定する第2引数を取るようにした。第2引数を手掛かりに元の配列の割付呼び出しコンテキストの情報を取得できるので、サイズ拡張した配列についてのプロファイル情報を元の配列の割付呼び出しコンテキストにフィードバックすることが可能となる。
【0039】
図1Bに戻って、本発明では、上記3つの要件を満たす所定のサイズの配列を割り付ける第1のAPIと、引数で指定された元の配列を拡張し、元の配列よりもサイズの大きい配列を割り付ける第2のAPIとを、標準ライブラリの一部としてかつstaticメソッドとしてライブラリ格納部117に用意する。中間コード格納部115は、上記第1及び第2のAPIを用いて書き換えられた配列拡張パターンを含む実行対象のプログラムである中間コードを格納する。実行部120は、中間コード格納部115から読み出したプログラムを解釈して、APIの記述を検出すると、対応するAPIの機能をライブラリ格納部117から呼び出して実行する。動的コンパイラ135は、第1のAPIと第2のAPIを実行時に変換し、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードとする。
【0040】
図2は、図1Aに示すコンピュータ50のハードウェア機能と図1Bに示すソフトウェア機能とを有する、本発明の実施形態に係る調整装置200の機能構成を示す。本発明の実施形態に係る調整装置200は、配列生成部202と、拡張配列生成部203と、マーク設定部205と、初期化部210と、呼び出し設定部215と、集計部220と、プロファイル情報収集部225と、インライン展開部235と、サイズ決定部240と、コード書き換え部245とを備える。更に調整装置200は、プロファイル情報収集部225により収集されたプロファイル情報を格納する配列毎のプロファイル情報格納部230と、集計部220により配列の割付呼び出しコンテキスト毎に収集されたプロファイル情報を格納するコンテキスト毎のプロファイル情報格納部223とを備える。なお、配列生成部202、拡張配列生成部203、マーク設定部205及び初期化部210の機能は、新たに導入したAPIを呼び出して実行する、図1Bに示す実行部120の機能として実装してよい。また、呼び出し設定部215、集計部220及びコンテキスト毎のプロファイル情報格納部223の機能は図1Bに示すメモリ管理部125の機能として実装してよい。また、プロファイル情報収集部225及び配列毎のプロファイル情報格納部230は、図1Bに示すプロファイラ130の機能として実装してよい。また、インライン展開部235、サイズ決定部240及びコード書き換え部245の機能は、図1Bに示す動的コンパイラ135の機能として実装してよい。
【0041】
配列生成部202は、実行対象プログラムからの配列の新規割り付け要求に応答して、所定のサイズの配列を生成する。また、拡張配列生成部203は、実行対象プログラムからの配列の拡張要求に応答して、所定のサイズよりも大きいサイズの配列を新規に生成し、生成した配列の各要素に元の配列の対応する要素の値をコピーする。配列生成部202及び拡張配列生成部203は配列を生成すると、後述するマーク設定部205を呼び出して生成した配列の先頭を指すポインタを渡す。このとき拡張配列生成部203は更に、配列の拡張要求と共に受け取った拡張すべき元の配列の情報をマーク設定部205へ渡す。本実施例では元の配列の情報は元の配列の先頭を指すポインタとする。
【0042】
マーク設定部205は、配列生成部202または拡張配列生成部203から呼び出されると、サンプリング頻度に基づき、生成された配列をプロファイル対象とするか否かを決定し、プロファイル対象とすると決定した場合に、該配列の先頭を指すポインタにプロファイル対象であることを示すマークを設定する。
【0043】
ここでサンプリング頻度とは、例えば1MB割り付けるたび1つオブジェクトをサンプリングするといったようなサンプリングを行う頻度である。また、上記マークの設定は、一例として、ポインタの空いている下1ビットをフラグとして利用したり、ポインタにオフセットを足してヒープ領域外を指すようにしたりして行ってよい。マーク設定部205はマークを設定すると、後述する初期化部210を呼び出して、マークを付けた配列の先頭を指すポインタと、該当する場合は拡張前の元の配列の先頭を指すポインタとを渡す。
【0044】
初期化部210は、マーク設定部205から呼び出されると、後述する集計部220やプロファイル情報収集部225が、収集したプロファイル情報を所定のデータ構造で所定の領域にそれぞれ格納できるように、予め所定のデータ構造のプロファイル情報を生成し初期化して所定の領域に格納しておく。ここで所定のデータ構造のプロファイル情報は、収集したプロファイル情報を効率よく格納するためのものであり、プロファイル情報収集部225によって利用される配列毎のプロファイル情報構造体と、集計部220によって利用される割付呼び出しコンテキスト毎のプロファイル情報構造体とを含む。
【0045】
初期化部210は、生成した配列毎のプロファイル情報構造体をその配列の先頭を指すポインタをキーとするハッシュ表(以下、「第1ハッシュ表」という)に登録できるように、実行対象のプログラムの実行直前又は直後に第1ハッシュ表を生成して配列毎のプロファイル情報格納部230に格納する。同様に、初期化部210は、生成した割付呼び出しコンテキスト毎のプロファイル情報構造体をその割付呼び出しコンテキストをキーとするハッシュ表(以下、「第2ハッシュ表」という)に登録できるように、実行対象のプログラムの実行直前又は直後に第2のハッシュ表を生成して割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納する。
【0046】
配列毎のプロファイル情報構造体は、その配列の割付呼び出しコンテキストに対応するコンテキスト毎のプロファイル情報構造体へのポインタを格納する第1フィールドと、その配列中でアクセスされた最後の要素のインデックスを格納する第2フィールドとを有する。ここでアクセスされた最後の要素とは、アクセスされた要素の中で配列中最も後ろに位置する要素を意味する。例えばある配列Tの各要素が、T[0」、T[3」、T[9]、T[0}、T[2}の順でアクセスされたとすると、配列中でアクセスされた最後の要素のインデックス値は9である。また、割り付けた配列の割付呼び出しコンテキストとは、配列を割り付けるに至るまでのメソッド間の呼び出し関係をいう。
【0047】
例えば、図5Aに示すプログラムは、図4に示すStringBuilderを呼び出して配列を割り付けるが、この場合の配列の割付呼び出しコンテキストは、1つは、該プログラムが実行され3行目で配列が割り付けられる時点におけるコンテキストである。即ち、図5Aに示すプログラムMySample1.method1は、3行目でStringBuilderのコンストラクタを呼び出し、該コンストラクタは図4に示すプログラムの4行目でメソッドgetCharArrayOfBestSizeを呼び出し、メソッドgetCharArrayOfBestSizeはそのメソッド内で配列を割り付ける。従って、この場合の配列の割付呼び出しコンテキストは、MySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)である。
【0048】
コンピュータは、配列の割付呼び出しコンテキストを任意の表現方法で保持してよい。例えば、配列の割付呼び出しコンテキストを、上記のようにメソッド名を呼び出し順に繋いだ文字列として保持してもよい。或いは、メソッドを示すメソッド情報構造体へのポインタを呼び出し順に繋いでポインタの配列として保持してもよい。
【0049】
割付呼び出しコンテキスト毎のプロファイル情報構造体は、配列毎のプロファイル情報構造体の第2フィールドの値を割付呼び出しコンテキスト毎に集計するためのデータ構造であり、必要に応じて拡張される表形式をとる。表の各エントリは、アクセスされた一番最後の要素のインデックスを格納する第1フィールドと、第1フィールドに格納された値をアクセスされた一番最後の要素のインデックスとし、かつ、その割付呼び出しコンテキストによって割り付けられた配列の数又は頻度を格納する第2フィールドとを含む。図5Bは、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)によって割り付けられた複数の配列についてのプロファイル結果をまとめた表の一例を示す。
【0050】
初期化部210は、マーク設定部205から呼び出されると、受け取ったポインタによりアクセスされる新規に割り付けられた配列に対して、配列毎のプロファイル情報構造体の生成及び初期化を行う。初期化部210は、配列毎のプロファイル情報構造体を生成すると、これをその配列の先頭を指すポインタをキーとして第1ハッシュ表に登録する。このとき初期化部210は、生成した配列毎のプロファイル情報構造体の第2フィールドを値−1で初期化する。初期化部210はまた、配列の生成要求元に応じて、生成した配列毎のプロファイル情報構造体の第1フィールドを初期化する。
【0051】
配列が、新規割り付け要求に応答して配列生成部202により生成されたものである場合、初期化部210は、まず、該配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在するか否かを確認する。対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在する場合、初期化部210は、生成した配列毎のプロファイル情報構造体の第1フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が存在しない場合、初期化部210は、新たに割付呼び出しコンテキスト毎のプロファイル情報構造体を生成し、これをその配列の割付呼び出しコンテキストをキーとして第2ハッシュ表に登録する。そして初期化部210は、生成した配列毎のプロファイル情報構造体の第1フィールドに、新たに生成した割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。
【0052】
なお、初期化部210は、配列の割付呼び出しコンテキストの情報を、配列を割り付けたスレッドのスタックを辿ることにより取得する。スタックは、完了していないメソッドにそれぞれ対応する1以上のフレームから構成されており、各フレームには対応するメソッドの状態情報(メソッド名を含む)が格納されている。スタックトップのフレームは現在実行中のメソッドのためのものであり、該メソッドを呼び出したメソッドのフレームがその下にある。このようにスタックには、1以上のフレームがそれぞれ対応するメソッドの呼び出し順に従って下から上へ積まれている。スタックを辿る際は、一番下のmainメソッドまで辿ってもよく、或いは、予め定めた段数(例えば20段)だけ辿ってもよい。初期化部210はコンテキスト情報を取得すると、これをキーとして第2ハッシュ表から割付呼び出しコンテキスト毎のプロファイル情報構造体を取得する。ヒットしない場合、生成した配列に対応するコンテキスト毎のプロファイル情報構造体は未だ生成されていないことを意味する。
【0053】
一方、配列が配列の拡張要求に応答して配列拡張生成部203により生成された場合、初期化部210は、マーク設定部205から受け取った拡張前の元の配列の先頭を指すポインタをキーとして第1ハッシュ表から配列毎のプロファイル情報構造体を取得する。そして初期化部210は、その第1フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを読み出し、これを生成した配列毎のプロファイル情報構造体の第1フィールドに設定する。
【0054】
呼び出し設定部215は、マークを付されたポインタを介して配列へのアクセスがあるとプロファイラ130が呼び出されるように、プロファイラ130の呼び出しを設定する。該設定には、実行対象のプログラムのコード(中間コード)を書き換えて行う方法と、ページ保護機構を利用する方法とがある。呼び出し設定部215は後者を採用し、前者については、後述するコード書き換え部245が採用する。従って、調整装置200は、呼び出し設定部215と後述するコード書き換え部245のうち少なくとも一方を含めばよいことに留意されたい。
【0055】
ページ保護機構を利用する呼び出し設定部215は、より具体的には、プロファイル対象であることを示すマークを付されたポインタが指す先のページを読み書き禁止に設定し、該ポインタを介して配列がアクセスされるとシグナルハンドラが呼び出されるようにする。この場合、シグナルハンドラがプロファイラ130としてプロファイル情報の収集を行う。なお、呼び出し設定部215は、上記プロファイラ130の呼び出し設定を、例えば実行対象プログラムの実行開始前、又は直後に行う。
【0056】
プロファイル情報収集部225は、プロファイラ130又はシグナルハンドラの呼び出しに応答して、即ち、プロファイル対象に設定された配列へのアクセスを検出することに応答して、該アクセスに関するプロファイル情報の収集を行う。プロファイル情報収集部225は、収集したプロファイル情報を、対応する配列毎のプロファイル情報構造体に格納する。より具体的には、プロファイル情報収集部225は、アクセスされた配列の先頭を指すポインタをキーにして配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を得る。そしてプロファイル情報収集部225は、取得した配列毎のプロファイル情報構造体の第2フィールドの値を読み出し、上記配列の現在アクセスされた要素のインデックスと比較する。現在のインデックスのほうが大きい場合、プロファイル情報収集部225は、現在のインデックスで上記第2フィールドの値を更新する。
【0057】
集計部220は、ガーベジコレクションにおけるプロファイル対象の配列の破棄処理に応答して、対応する配列毎のオブジェクト情報構造体の記録を、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体に集計する。具体的には、集計部220はまず、破棄対象の配列のポインタをキーとして、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表から対応する配列毎のオブジェクト情報構造体を取得する。そして集計部220は、その第1フィールドのポインタ値から、割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体である表の中に、取得した配列毎のオブジェクト情報構造体の第2フィールドの値に対応するエントリが既に存在しているか否かを確認する。対応するエントリが既に存在する場合、集計部220は、該エントリの第2フィールドの頻度値を1増加する。対応するエントリが存在しない場合、集計部220は、取得した割付呼び出しコンテキスト毎のプロファイル情報構造体の表にエントリを1つ追加し、そのエントリの第1フィールドに、取得した配列毎のオブジェクト情報構造体の第2フィールドの値を設定し、そのエントリの第2フィールドに、頻度として値1を設定する。
【0058】
インライン展開部235は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、上記中間コードの部分に含まれる配列の割付呼び出しコンテキストについて十分なプロファイル情報が集まっていることを条件に、そのコンテキストをインライン展開する。例えばインライン展開部235は、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体の全エントリについての頻度の合計が予め定めた閾値よりも大きい場合に、該コンテキストについて十分なプロファイル情報が集まっていると判断してよい。インライン展開部235はインライン展開処理の後、後述するサイズ決定部240を呼び出す。
【0059】
サイズ決定部240は、インライン展開部235から呼び出されると、インライン展開された配列の割付呼び出しコンテキストに対し、該コンテキストに対して収集されたプロファイル情報に基づいて該コンテキストが割り付ける配列の初期サイズを決定する。なお、収集されたプロファイル情報とは、上記コンテキストをキーとしてコンテキスト毎のプロファイル情報格納部223に格納される第2ハッシュ表を引いて取得される対応する割付呼び出しコンテキスト毎のプロファイル情報構造体である。好ましくは、サイズ決定部240は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を配列の割り付け初期サイズとする。これに代えて、サイズ決定部240は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を配列の割り付け初期サイズとしてもよい。
【0060】
ここで図5A〜図5C及び図6A〜図6Cを参照して、インライン展開部235のインライン展開処理と、サイズ決定部240のサイズ決定処理を具体的に説明する。上述したように図5Aに示すプログラムは、図4に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図5Bに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。なお、十分なプロファイルが集まっていると判断するための予め定められた閾値を20とする。
【0061】
すると、図5Bに示す表の頻度の合計は25であるため、インライン展開部235は、上記コンテキストMySample1.method1()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部235は、図3Bに示すメソッドgetCharArrayOfBestSize(int)の定義を、図5Aに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図5Cに示すコードを得る。このときサイズ決定部240は、図5Bに示す表において最大のインデックス値が1であることから、配列のサイズは要素数2で十分であると判定し、配列の割り付け初期サイズを2に決定する。なお、図4に示すように、当初配列の初期サイズは16であったことに留意されたい。
【0062】
図6に示すプログラムもまた、図4に示すStringBuilderを呼び出して配列を割り付けるものであり、割付呼び出しコンテキスト、MySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)に対し、図6Bに示す割付呼び出しコンテキスト毎のプロファイル情報構造体が得られたとする。図6Bに示す表の頻度の合計は24であるため、インライン展開部235は、上記コンテキストMySample2.method2()→java.lang.StringBuilder.<int>()→java.lang.System.getCharArrayOfBestSize(int)をインライン展開する。即ち、インライン展開部235は、図3Bに示すメソッドgetCharArrayOfBestSize(int)の定義を、図6Aに示すプログラムのコンストラクタStringBuilder()の呼び出し箇所に直接埋め込み、図6Cに示すコードを得る。このときサイズ決定部240は、図6Bに示す表において最大のインデックス値が1659であることから、配列のサイズは要素数1660で十分であると判定し、配列の割り付け初期サイズを1660に決定する。なお、図4に示すように、当初配列の初期サイズは16であったことに留意されたい。
【0063】
コード書き換え部245は、実行対象プログラムである中間コードの部分の動的コンパイル処理において呼び出され、プロファイル対象であることを示すマークを付されたポインタを介して配列へのアクセスがあるとプロファイラ130が呼び出されるように、上記中間コードの部分に含まれるプロファイル対象の配列へのアクセス命令に対してプロファイラ130の呼び出しを設定する。上述したように、コード書き換え部235は上記プロファイラ130の呼び出しの設定をコードの書き換えによって行う。より具体的には、コード書き換え部235は、実行対象のプログラムに含まれる全てのポインタ経由の配列へのアクセス命令の前に、プロファイル対象であることを示すマークの有無を判定するコードと、マークが付されているとの判定結果に対してプロファイラ130を呼び出すコードとを挿入する。
【0064】
次に図7乃至図11を参照して、調整装置200の動作を説明する。図7は、本実施形態に係る調整装置200の動作フローの一例を示す。図8は、図7に示すステップ740の実行部120(初期化部210)による処理の詳細な動作フローの一例を示す。図9は、図7に示すステップ720のメモリ管理部125による処理の詳細な動作フローの一例を示す。図10は、図7に示すステップ750のプロファイラ130による処理の詳細な動作フローの一例を示す。図11は、図7に示すステップ760の動的コンパイラ135による処理の詳細な動作フローの一例を示す。
【0065】
図7に示す調整装置200の動作フローはステップ700から開始し、実行部120は、メモリ管理部120を呼び出して、プロファイラ130の呼び出しのためのページ保護機構を設定させる。続いて実行部120は、実行対象プログラム(中間コード)の実行を開始して、次に実行しようとする命令を取得する(ステップ705)。続いて実行部120は、実行しようとする現在の命令がオブジェクトを割り付けるか否かを判定する(ステップ710)。現在の命令がオブジェクトを割り付けると判定した場合(ステップ710:YES)、実行部120はガーベジコレクションが必要であるか否かを判定する(ステップ715)。ガーベジコレクションが必要であると判定した場合(ステップ715:YES)、実行部120は、メモリ管理部125を呼び出して処理を実行させる。メモリ管理部125による処理の詳細は、図9を参照して後述する。
【0066】
メモリ管理部125による処理の後、続いて実行部120は、実行する命令が所定サイズの配列を割り付ける第1のAPIによる配列割付の命令であり、かつ、該命令により割り付ける配列をサンプリング頻度に基づきサンプリング対象とすべきか否かを判定する(ステップ725)。第1のAPIによる配列割付の命令でない場合、又は第1のAPIによる配列割付の命令であるがサンプリング対象としないと決定した場合(ステップ725:NO)、処理はステップ730へ進み、続いて実行部120は、実行する命令が、第2引数で指定された元の配列を拡張する第2のAPIによる拡張配列の割付命令であり、かつ、第2引数で指定された元の配列の先頭を指すポインタにサンプリング対象であることを示すマークが付いているか否かを判定する。第2のAPIによる配列割付の命令でない場合、又は第2のAPIによる配列割付の命令であるが、受け取った上記ポインタにマークが付いてない場合(ステップ730:NO)、処理はステップ745へ進む。なお、ステップ725において少なくとも第1のAPIによる配列割付の命令であると判定した場合、又はステップ730において少なくとも第2のAPIによる拡張配列の割付命令であると判定した場合、実行部120はそれぞれ要求される配列を割り付ける。
【0067】
ステップ725またはステップ730において肯定的な判定結果が得られた場合(ステップ725:YESまたはステップ730:YES)、処理はステップ735へ進み、実行部120は、ステップ725またはステップ730で割り付けた配列の先頭を指すポインタに、プロファイル対象であることを示すマークを付ける。続いて実行部120は、プロファイル対象とした配列に対して初期化処理を行う(ステップ740)。初期化処理の詳細は図8を参照して後述する。
【0068】
ステップ740の後、ステップ710において現在の命令がオブジェクトを割り付けないと判定した場合(ステップ710:NO)、又はステップ730において否定的な判定結果が得られる場合(ステップ730:NO)、処理はステップ745へ進み、実行部11520は、現在の命令はサンプリングされた、即ちプロファイル対象の配列へのアクセス命令であるか否かを判定する。プロファイル対象の配列へのアクセス命令であると判定した場合(ステップ745:YES)、実行部120はプロファイラ130を呼び出して処理を実行させる(ステップ750)。プロファイラ130による処理の詳細は、図10を参照して後述する。
【0069】
ステップ750の後、又はステップ745において現在の命令がプロファイル対象の配列へのアクセス命令ではないと判定した場合(ステップ745:NO)、処理はステップ755へ進み、実行部120は、次に実行する中間コードの部分を動的にコンパイルする必要があるか否かを判定する。動的コンパイルが必要であると判定した場合(ステップ755:YES)、実行部120は動的コンパイラ135を呼び出して処理を実行させる(ステップ760)。動的コンパイラ135による処理の詳細は、図11を参照して後述する。
【0070】
ステップ760の後、又はステップ755において動的コンパイルが必要でないと判定した場合(ステップ755:NO)、処理はステップ765へ進み、実行部120は、実行対象プログラムの実行が終了したか否かを判定する。実行対象プログラムの実行がまだ終了していない場合(ステップ765:NO)、処理はステップ705へ戻る。一方、プログラムの実行が終了した場合(ステップ765:YES)、調整装置200の動作フローは終了する。
【0071】
図8に示す初期化210による処理の動作フローはステップ800から開始し、初期化210は、図7に示すステップ735においてそのポインタにマークを付けた配列に対して、配列毎のプロファイル情報構造体を生成し、その第2フィールドを値―1で初期化する。続いて初期化部210は、上記配列の割付が、第2引数で指定された元の配列を拡張する第2のAPIによる割付であったか否かを判定する(ステップ805)。第2のAPIによる割付でなかった場合(ステップ805:NO)、続いて初期化部210は、上記配列を割り付けたスレッドのスタックを辿って、上記配列を割り付けた割付呼び出しコンテキストを取得する(ステップ810)。続いて初期化部210は、上記配列を割り付けた割付呼び出しコンテキストをキーとして割付呼び出しコンテキスト毎のプロファイル情報格納部223に格納される第2ハッシュ表を引き、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在するか否かを判定する(ステップ815)。
【0072】
対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在しない場合(ステップ815:NO)、初期化部210は、上記配列の割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を新たに生成し、該コンテキストをキーとして第2ハッシュ表に登録する(ステップ820)。一方、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体が第2ハッシュ表に存在する場合(ステップ815:YES)、またステップ820の後、初期化部210は、ステップ800において生成した配列毎のプロファイル情報構造体の第1フィールドに、対応する割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを設定する。
【0073】
一方ステップ805において、上記配列の割付が第2のAPIによる割付であった場合(ステップ805:YES)、初期化部210は、第2のAPIの第2引数で指定された拡張前の元の配列のポインタをキーとして配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する。そして初期化部210は、取得した配列毎のプロファイル情報構造体の第1フィールドに格納された割付呼び出しコンテキスト毎の構造体へのポインタを、ステップ800で生成した配列毎のプロファイル情報構造体の第1フィールドに設定する。ステップ825又はステップ835から処理はステップ830へ進み、初期化部210は、ステップ800で生成した配列毎のプロファイル情報構造体を、その配列の先頭を指すポインタをキーとして配列毎のプロファイル情報格納部230内の第1ハッシュ表に登録する。その後処理は終了する。
【0074】
図9に示すメモリ管理部125による処理の動作フローはステップ900から開始し、メモリ管理部125は、ヒープ領域に生成されている使用中の全オブジェクトを検出するために、オブジェクト間のポインタによる参照関係を示すツリー構造をスキャンし、使用中のオブジェクトを指す全ポインタについて以下の一連の処理を繰り返す。メモリ管理部125はまず、現在のポインタに対して、通常のガーベジコレクション処理を実行する(ステップ905)。通常のガーベジコレクション処理のアルゴリズムは周知の技術であり、本発明の要旨ではないので詳細な説明は省略する。
【0075】
続いてメモリ管理部125は、ステップ905におけるガーベジコレクション処理で配列オブジェクトを破棄すると決定し、かつ、破棄すると決定した配列オブジェクトに対応する配列毎のプロファイル情報構造体が、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表内に存在するか否かを判定する(ステップ910)。否定的な判定結果が得られた場合(ステップ910:NO)、現在のポインタについての処理は終わる。一方、肯定的な判定結果が得られた場合(ステップ910:YES)、メモリ管理部125は、破棄する配列に対応する配列毎のプロファイル情報構造体の第1フィールドから割付呼び出しコンテキスト毎のプロファイル情報構造体へのポインタを取得し(ステップ915)、ポインタが指す表に、破棄する配列に対応する配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値に対応するエントリが存在するか否かを判定する(ステップ920)。
【0076】
対応するエントリが存在すると判定した場合(ステップ920:YES)、メモリ管理部125は、
該エントリの第2フィールドの頻度値を1増やす(ステップ925)。一方、対応するエントリが存在しないと判定した場合(ステップ920:NO)、メモリ管理部125は、ステップ915で取得したポインタが指す表にエントリを1つ追加し、該エントリの第1フィールドに、破棄する配列に対応する配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値を、該エントリの第2フィールドに、頻度値1をそれぞれ設定する(ステップ930)。
【0077】
ステップ925又はステップ930の後、メモリ管理部125は、破棄する配列を割り付けた割付呼び出しコンテキストについて十分なプロファイルが集まったと判定することを条件に、動的コンパイラ135を呼び出して動的コンパイルを行わせる。動的コンパイラ135による動的コンパイル処理の詳細は図11を参照して後述する。続いてメモリ管理部125は、破棄する配列に対応する配列毎のプロファイル情報構造体を、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表から削除する(ステップ940)。使用中のオブジェクトを指す全ポインタについて上記一連の処理が行われると、処理は終了する。
【0078】
図10に示すプロファイラ130による処理の動作フローはステップ1000から開始し、プロファイラ130は、プロファイラ130呼び出しの要因となった現在のオブジェクト・アクセス命令における配列をアクセスする。続いてプロファイラ130は、アクセスした配列の先頭を指すポインタをキーとして、配列毎のプロファイル情報格納部230に格納される第1ハッシュ表を引き、対応する配列毎のプロファイル情報構造体を取得する(ステップ1005)。続いてプロファイラ130は、現在のオブジェクト・アクセス命令によりアクセスされる配列の要素のインデックス値と、取得した配列毎のプロファイル情報構造体の第2フィールドに格納されるインデックス値とを比較し、アクセスしようとする配列の要素のインデックス値が大きい場合、該インデックス値で上記第2フィールドの値を更新する(ステップ1010)。そして処理は終了する。
【0079】
図11に示す動的コンパイラ135による処理の動作フローはステップ1100から開始し、動的コンパイラ135は、次に実行しようとする実行対象プログラムのコード部分を、中間コード(バイトコード)格納部115から読み込む。続いて動的コンパイラ135は、コンパイル対象の上記コード部分に含まれる割付呼び出しコンテキストについて、十分なプロファイルがコンテキスト毎のプロファイル情報格納部223に収集されていることを条件に、上記コンテキストをインライン展開する(ステップ1105)。
【0080】
続いて動的コンパイラ135は、インライン展開された割付呼び出しコンテキストに対応する割付呼び出しコンテキスト毎のプロファイル情報構造体を取得し、該構造体に記録されたインデックスのうち最大のインデックスの値を、配列の割付初期サイズとしてインライン展開したコードに埋め込む(ステップ1110)。続いて動的コンパイラ135は、上記コード部分の上記割付呼び出しコンテキスト以外の部分について最適化処理を行う(ステップ1115)。最適化の種類は複数存在し、それぞれのアルゴリズムは既知の技術であり本発明の要旨でもないので、ここでは詳細な説明を省略する。
【0081】
続いて動的コンパイラ135は、コンパイル対象の上記コード部分に対し、プロファイラ130呼び出しのためのコードの書き換えを行う(ステップ1120)。続いて、動的コンパイラ135は、上記コード部分の上記割付呼び出しコンテキスト以外の部分をコンパイルし、ネイティブコードを生成する(ステップ1125)。そして処理は終了する。
【0082】
[実験]
1.実装
動作周波数最大4.7GHzのRISCプロセッサ(クアッドコア、2スレッドのSMTエンジン搭載のPOWER6(商標))と利用した各ベンチマークが必要とする最低のヒープメモリ量の2倍のヒープメモリ量をハードウエアとして備え、オペレーティング・システムとしてLinux(商標)2.6.18を用いるIBM社のJava(登録商標)仮想マシンに、本発明の実施形態に係る調整プログラムを実装した。なお、実装した調整プログラムでは、8MB割り付ける毎に1つの配列をサンプリングするサンプリング頻度を用いた。また、ベンチマークDaCapoの中からオブジェクトを多く割り付ける8つのベンチマークプログラム(fop、jython、lusearch、pmd、sunflow、tomcat、xalan、Geo.mean)を選択した。また、Java(登録商標)標準ライブラリのjava.lang.StringBuilder、java.io、BufferedReader、lusearchベンチマークの2つのクラス、xalaベンチマークの3つのクラスの各々におけるは配列の割付を、本発明で新たに導入したAPIを用いて行うように書き換えた。
【0083】
2.実験結果
図12は、速度向上率についての実験結果を示す。図12に示されるように、ベンチマークによっては最大300%以上(4倍以上)の性能向上が見られた。なお、性能低下は、最大でも2.2%であり、これはアクセスプロファイラのオーバーヘッドによるものである。
【0084】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【0085】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【特許請求の範囲】
【請求項1】
配列の初期サイズを動的に調整する調整プログラムであって、該プログラムはコンピュータに、
(a)実行対象プログラムからの配列の割り付け要求に応答して、所定サイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(b)前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(c)前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、
(d)各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
(e)前記プ実行対象ログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
を実行させる前記調整プログラム。
【請求項2】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項1に記載の調整プログラム。
【請求項3】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む、請求項1に記載の調整プログラム。
【請求項4】
配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられており、ステップ(b)は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む、請求項1に記載の調整プログラム。
【請求項5】
ステップ(d)の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる、請求項1に記載の調整プログラム。
【請求項6】
情報処理装置おいて配列の初期サイズを動的に調整する調整方法であって、
(a)前記情報処理装置が、実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(b)前記情報処理装置が、前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(c)前記情報処理装置が、前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、
(d)前記情報処理装置が、各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
(e)前記情報処理装置が、前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
を含む調整方法。
【請求項7】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項6に記載の調整方法。
【請求項8】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項6に記載の調整方法。
【請求項9】
配列の初期サイズを動的に調整する情報処理装置であって、
記憶装置と、
前記記憶装置に格納された実行対象プログラムと、
前記実行対象プログラムを解釈して、APIの記述を検出することに応答して、対応するAPIの機能を呼び出して実行する実行手段と、
前記実行手段によって呼び出され得る、所定のサイズの配列を割り付ける第1のAPIと、引数として拡張すべき配列の情報を受け取り、該配列よりもサイズの大きい配列を割り付ける第2のAPIであって、前記第1及び第2のAPIは、実行時に、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードに変換される、前記第1及び第2のAPIと、
プロファイル対象の配列へのアクセスの検出に応答して前記実行手段によって呼び出され得る、アクセスを検出された前記配列に対応するプロファイル情報格納領域に前記配列へのアクセス情報を格納するプロファイラと、
次に実行すべき実行対象プログラムのコード部分を動的にコンパイルする動的コンパイラであって、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに関連づけられた全アクセス情報に基づき決定される配列のサイズを前記配列の割り付け初期サイズとして前記コード部分に埋め込む前記動的コンパイラと、
を含む情報処理装置。
【請求項10】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとする、請求項9に記載の情報処理装置。
【請求項11】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとする、請求項9に記載の情報処理装置。
【請求項12】
前記第2のAPIは、引数として受け取った拡張すべき配列の情報を用いて、該配列に対応するプロファイル情報格納領域から前記拡張前の配列の割付呼び出しコンテキスト情報を取得する、請求項9に記載の情報処理装置。
【請求項13】
前記第1及び第2のAPIは、プリミティブ型の配列ごとに用意される、請求項9に記載の情報処理装置。
【請求項14】
前記第1及び第2のAPIは、標準ライブラリの一部としてかつstaticメソッドとして用意される、請求項9に記載の情報処理装置。
【請求項1】
配列の初期サイズを動的に調整する調整プログラムであって、該プログラムはコンピュータに、
(a)実行対象プログラムからの配列の割り付け要求に応答して、所定サイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(b)前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に拡張前の元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(c)前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、
(d)各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
(e)前記プ実行対象ログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
を実行させる前記調整プログラム。
【請求項2】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項1に記載の調整プログラム。
【請求項3】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとするステップを含む、請求項1に記載の調整プログラム。
【請求項4】
配列毎のプロファイル情報格納領域は、該配列の先頭を指すポインタに関連付けられており、ステップ(b)は、前記配列のサイズ拡張の要求とともに該配列の先頭を指すポインタを受取り、受け取った前記ポインタを用いて前記元の配列のプロファイル情報格納領域に格納される前記元の配列の割付呼び出しコンテキスト情報を取得するステップを含む、請求項1に記載の調整プログラム。
【請求項5】
ステップ(d)の収集は、ガーベジコレクション処理において破棄されるプロファイル対象の配列について行われる、請求項1に記載の調整プログラム。
【請求項6】
情報処理装置おいて配列の初期サイズを動的に調整する調整方法であって、
(a)前記情報処理装置が、実行対象プログラムからの配列の割り付け要求に応答して、所定のサイズの配列を割り付けると共に、該配列のプロファイル情報格納領域に、前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(b)前記情報処理装置が、前記実行対象プログラムからの割り付けた前記配列のサイズ拡張の要求に応答して、より大きなサイズの配列を拡張配列として新たに割り付けると共に、前記拡張配列のプロファイル情報格納領域に元の前記配列の割付呼び出しコンテキスト情報を格納するステップと、
(c)前記情報処理装置が、前記実行対象プログラムの実行中におけるプロファイル対象の配列へのアクセスに応答して、該配列のプロファイル情報格納領域にアクセス情報を格納するステップと、
(d)前記情報処理装置が、各配列のプロファイル情報格納領域に格納されるアクセス情報を、配列の割付呼び出しコンテキスト毎に収集するステップと、
(e)前記情報処理装置が、前記実行対象プログラムの次に実行するコード部分の動的コンパイルに応答して、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに対して収集されたアクセス情報に基づき決定される配列のサイズを前記配列の割付初期サイズとしてインライン展開したコードに埋め込むステップと、
を含む調整方法。
【請求項7】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項6に記載の調整方法。
【請求項8】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、ステップ(e)は、前記情報処理装置が、収集されたアクセス情報である複数のインデックス値の中で頻度が最大のインデックス値を前記配列の割付初期サイズとするステップを含む、請求項6に記載の調整方法。
【請求項9】
配列の初期サイズを動的に調整する情報処理装置であって、
記憶装置と、
前記記憶装置に格納された実行対象プログラムと、
前記実行対象プログラムを解釈して、APIの記述を検出することに応答して、対応するAPIの機能を呼び出して実行する実行手段と、
前記実行手段によって呼び出され得る、所定のサイズの配列を割り付ける第1のAPIと、引数として拡張すべき配列の情報を受け取り、該配列よりもサイズの大きい配列を割り付ける第2のAPIであって、前記第1及び第2のAPIは、実行時に、それぞれ割り付けた配列をサンプリング頻度に基づきプロファイル対象とすると共に、割り付けた配列のプロファイル情報格納領域に、拡張前の配列の割付呼び出しコンテキストを格納するコードに変換される、前記第1及び第2のAPIと、
プロファイル対象の配列へのアクセスの検出に応答して前記実行手段によって呼び出され得る、アクセスを検出された前記配列に対応するプロファイル情報格納領域に前記配列へのアクセス情報を格納するプロファイラと、
次に実行すべき実行対象プログラムのコード部分を動的にコンパイルする動的コンパイラであって、前記コード部分に含まれる配列の割付呼び出しコンテキストをインライン展開し、該コンテキストに関連づけられた全アクセス情報に基づき決定される配列のサイズを前記配列の割り付け初期サイズとして前記コード部分に埋め込む前記動的コンパイラと、
を含む情報処理装置。
【請求項10】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で最大のインデックス値を前記配列の割付初期サイズとする、請求項9に記載の情報処理装置。
【請求項11】
各配列のプロファイル情報格納領域に格納されるアクセス情報は、アクセスされた前記配列の要素中で最後に位置する要素のインデックス値であり、前記動的コンパイラは、インライン展開された前記コンテキストに関連づけられた全アクセス情報である複数のインデックス値の中で頻度が最大のインデックスの値を前記配列の割付初期サイズとする、請求項9に記載の情報処理装置。
【請求項12】
前記第2のAPIは、引数として受け取った拡張すべき配列の情報を用いて、該配列に対応するプロファイル情報格納領域から前記拡張前の配列の割付呼び出しコンテキスト情報を取得する、請求項9に記載の情報処理装置。
【請求項13】
前記第1及び第2のAPIは、プリミティブ型の配列ごとに用意される、請求項9に記載の情報処理装置。
【請求項14】
前記第1及び第2のAPIは、標準ライブラリの一部としてかつstaticメソッドとして用意される、請求項9に記載の情報処理装置。
【図1A】
【図1B】
【図2】
【図3A】
【図3B】
【図3C】
【図4】
【図5A】
【図5B】
【図5C】
【図6A】
【図6B】
【図6C】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図1B】
【図2】
【図3A】
【図3B】
【図3C】
【図4】
【図5A】
【図5B】
【図5C】
【図6A】
【図6B】
【図6C】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【公開番号】特開2013−114552(P2013−114552A)
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願番号】特願2011−261775(P2011−261775)
【出願日】平成23年11月30日(2011.11.30)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MACHINES CORPORATION
【Fターム(参考)】
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願日】平成23年11月30日(2011.11.30)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MACHINES CORPORATION
【Fターム(参考)】
[ Back to top ]