(57)【要約】  【課題】  呼び出しコンテキストによって一意にKeyの値が決定されるMap.get処理を最適化する技法を提供する。  【解決手段】  サンプリング結果から呼び出しコンテキストの起点メソッドを特定し、特定したメソッドのクラスのフィールドにget返値情報を保持し、呼び出しコンテキスト内のメソッド引数にget返値情報を追加し、Mapのget処理内にget処理内にget返値情報の妥当性を検証後、値を返す、という処理を、ソフトウェアで実行することにより自動的に達成する。【選択図】  図３
2014238770.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、呼び出しコンテキストに従って、Mapからデータを取り出す処理(以下getと称する)によってメソッド中で返されるオブジェクトを処理する方法であって、
前記呼び出しコンテキストの起点メソッドを特定するステップと、
前記特定した起点メソッドのクラスのフィールドにget返り値、および、get返り値の妥当性検証に必要な情報を保持するステップと、
前記呼び出しコンテキスト内のメソッド引数にget返り値を追加するステップと、
Mapのget返り値情報の妥当性を検証するステップと、
前記Mapのget返り値情報が妥当であるとの判定に応答して、前記Mapのget返り値を返すステップと、
前記Mapのget返り値情報が妥当でないとの判定に応答して、前記Mapのget返り値を最新に更新するステップを有する、
方法。
【請求項２】
前記起点メソッドを特定するステップが、
Mapのget返り値のサンプルを取得するステップと、
前記Mapのget返り値のサンプルに基づき、コンテキスト中のメソッドをノードとし、各ノードを経由してMapのgetが返し得る値とノードをマッピングするステップと、
前記マッピングにおいて、Mapのgetの返り値と一対一対応となっているノードに該当するメソッドを起点メソッドを特定するステップを有する、
請求項１に記載の方法。
【請求項３】
前記一連のステップがＪＶＭ上で実行される、請求項１に記載の方法。
【請求項４】
前記Mapのget返り値情報の妥当性を検証するステップが、ConcurrentHashMapのクラスで実装される、請求項３に記載の方法。
【請求項５】
コンピュータの処理によって、呼び出しコンテキストに従って、Mapからデータを取り出す処理(以下getと称する)によってメソッド中で返されるオブジェクトを処理するプログラムであって、
前記コンピュータに、
前記呼び出しコンテキストの起点メソッドを特定するステップと、
前記特定した起点メソッドのクラスのフィールドにget返り値、および、get返り値の妥当性検証に必要な情報を保持するステップと、
前記呼び出しコンテキスト内のメソッド引数にget返り値を追加するステップと、
Mapのget返り値情報の妥当性を検証するステップと、
前記Mapのget返り値情報が妥当であるとの判定に応答して、前記Mapのget返り値を返すステップと、
前記Mapのget返り値情報が妥当でないとの判定に応答して、前記Mapのget返り値を最新に更新するステップを実行させる、
プログラム。
【請求項６】
前記起点メソッドを特定するステップが、
Mapのget返り値のサンプルを取得するステップと、
前記Mapのget返り値のサンプルに基づき、コンテキスト中のメソッドをノードとし、各ノードを経由してMapのgetが返し得る値とノードをマッピングするステップと、
前記マッピングにおいて、Mapのgetの返り値と一対一対応となっているノードに該当するメソッドを起点メソッドを特定するステップを有する、
請求項５に記載のプログラム。
【請求項７】
前記一連のステップがＪＶＭ上で実行される、請求項５に記載のプログラム。
【請求項８】
前記Mapのget返り値情報の妥当性を検証するステップが、ConcurrentHashMapのクラスで実装される、請求項７に記載のプログラム。
【請求項９】
コンピュータの処理によって、呼び出しコンテキストに従って、Mapからデータを取り出す処理(以下getと称する)によってメソッド中で返されるオブジェクトを処理するシステムであって、
前記呼び出しコンテキストの起点メソッドを特定する手段と、
前記特定した起点メソッドのクラスのフィールドにget返り値、および、get返り値の妥当性検証に必要な情報を保持する手段と、
前記呼び出しコンテキスト内のメソッド引数にget返り値を追加する手段と、
Mapのget返り値情報の妥当性を検証する手段と、
前記Mapのget返り値情報が妥当であるとの判定に応答して、前記Mapのget返り値を返す手段と、
前記Mapのget返り値情報が妥当でないとの判定に応答して、前記Mapのget返り値を最新に更新する手段を有する、
システム。
【請求項１０】
前記起点メソッドを特定する手段が、
Mapのget返り値のサンプルを取得する処理と、
前記Mapのget返り値のサンプルに基づき、コンテキスト中のメソッドをノードとし、各ノードを経由してMapのgetが返し得る値とノードをマッピングする処理と、
前記マッピングにおいて、Mapのgetの返り値と一対一対応となっているノードに該当するメソッドを起点メソッドを特定する処理を行う、
請求項９に記載のシステム。
【請求項１１】
前記システムは、ＪＶＭ及びミドルウェア上で実装される、請求項９に記載のシステム。
【請求項１２】
前記Mapのget返り値情報の妥当性を検証する手段が、ConcurrentHashMapのクラスで実装される、請求項１１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータにおけるオブジェクトの処理技法に関し、より詳しくは、連想配列（マップ、Map）に格納されたオブジェクトの取得処理（Map.get処理、Keyを指定してオブジェクトを取得する）を最適化する技法に関する。
【背景技術】
【０００２】
従来より、インターナショナル・ビジネス・マシーンズ・コーポレーションにより提供されているWebSphere(R)などの大規模なソフトウェアでは、呼び出しコンテキスト(Calling Context)によって一意的にKeyの値が決定されるMap.getが頻繁に処理されている。
【０００３】
特に、eコーマス向けのあるアプリケーションでは、数%のＣＰＵ能力が、Map.get処理に費やされ、その数十%が呼び出しコンテキストによって一意的にKeyの値が決定されることが分かっている。
【０００４】
このようなMap.get処理は、呼び出しコンテキストから返す値を決定する処理を最適化することが可能である。この処理は、例えば、特定の呼び出しコンテキストには、特定の値を返す、などである。
【０００５】
しかし、このような最適化処理は、ＪＩＴなどのコンパイラでは、対応できない。というのは、バイトコード・レベルでは、Mapセマンティックスが認識できないからである。
【０００６】
また、一般的なJITコンパイラでは、最適化の対象はメソッド単位であり、多段のメソッド呼び出しから特定の値が導くことが可能な呼び出しコンテキストには対応できない。通常、JITコンパイラでは、インライン可能なメソッド呼び出しの段数が制限されている。上記eコマース向けのアプリケーションの場合は、10段以上のメソッドをインラインする必要があり、制限によりインラインされることはない。
【０００７】
これに関する従来技術として、特開２０１０−２０５１７０号公報は、マルチスレッド上で動作するプログラムのプログラム・コードをロック衝突が少ないプログラム・コードに変換する技法を開示する。
【０００８】
特開２０１１−２５３４３７号公報は、ＰＨＰのプロパティ名pから一意に決まるＪａｖａのインターフェース・クラスI(p)を必要に応じて生成してロードするＪａｖａのクラスローダを用意し、ＰＨＰのクラスの階層に対応してＪａｖａのクラスを生成してキャッシュすることにより、動的に作られるＰＨＰ上のクラス階層と同じＪａｖａ上のクラス階層が準備するステップを実行し、上記インターフェース・クラスI(p)を実装するようにＪａｖａのクラスを宣言して、当該インターフェースに備わったメソッドの実装として、Ｊａｖａのフィールドへのアクセスとしてプロパティ・アクセスのコードを備えさせることにより、インターフェースを通じたプロパティアクセスを可能にするステップを開示する。
【０００９】
しかし、これら従来技術は、Map.get処理の最適化には適用できない。なお、背景技術として、http://www.ibm.com/developerworks/jp/java/library/j-jtp07233/あるいは、http://docs.oracle.com/javase/jp/6/api/java/util/concurrent/ConcurrentHashMap.htmlに、ConcurrentHashMapに関する解説がある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１０−２０５１７０号公報
【特許文献２】特開２０１１−２５３４３７号公報
【００１１】
【非特許文献１】http://www.ibm.com/developerworks/jp/java/library/j-jtp07233/
【非特許文献２】http://docs.oracle.com/javase/jp/6/api/java/util/concurrent/ConcurrentHashMap.html
【発明の概要】
【発明が解決しようとする課題】
【００１２】
この発明の目的は、ＪＶＭなどの処理系の許容する範囲で、呼び出しコンテキストによって一意にKeyの値が決定されるMap.get処理を最適化する技法を提供することにある。
【課題を解決するための手段】
【００１３】
本発明は、上記課題を、
(1) サンプリング結果から呼び出しコンテキストの起点メソッドを特定し、
(2) 特定したメソッドのクラスのフィールドにget返値情報を保持し、
(3) 呼び出しコンテキスト内のメソッド引数にget返値情報を追加し、
(4) Mapのget処理内にget処理内にget返値情報の妥当性を検証後、値を返す、
という処理を、ソフトウェアで実行することにより自動的に達成する。
【００１４】
起点クラスの特定方法は、頻繁にgetが呼ばれているMapに対して、スタック・トレースのサンプルを取得し、ノードと値のマッピングをとり、ノードと値のマッピングをとり、一対一対応となっているメソッドを起点と特定する処理を行う。なお、１コンテキスト内で複数のノードが起点となる場合は、一方を選択する。
【００１５】
get返値情報には、Map.Entryとして、Map、Key、Valueを格納する。なお、Map.Entryは、Mapを構成する要素である。一般的なMap.get処理では、Map.Entry中のKeyの値を比較して要求されたKeyを持つMap.Entryを特定し、そのValueを返す処理がなされる。
【００１６】
get処理においては、get返値の妥当性のチェックが成功した場合は、get返値情報のValueを返し、それ以外の場合は通常のget処理を行い、get返値情報の初期化を行う。
【発明の効果】
【００１７】
この発明によれば、呼び出しコンテキストによって一意にKeyの値が決定されるMap.get処理を最適化する技法が提供される。
【図面の簡単な説明】
【００１８】
【図１】本発明を実施するための一例のハードウェア構成のブロック図である。
【図２】本発明を実施するための一例のソフトウェア構成の階層を示す図である。
【図３】本発明の処理のフローチャートを示す図である。
【図４】複数のプログラム間のMap.getの呼び出しを示す図である。
【図５】Map.getの呼び出しの階層を示す図である。
【図６】本発明により修正された複数のプログラム間のMap.getの呼び出しを示す図である。
【発明を実施するための形態】
【００１９】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２０】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・バス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のCore(商標) i3、Core(商標) i5、Core(商標) i7、Xeon(R)、AMD社のAthlon(商標)、Phenom(商標)、Sempron(商標)などを使用することができる。主記憶１０６は、好適には、８ＧＢ以上の容量、より好ましくは、３２ＧＢ以上の容量をもつものである。
【００２１】
ハードディスク・ドライブ１０８には、オペレーティング・システム（ＯＳ）が格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows(商標)2008サーバなどの、ＣＰＵ１０４に適合する任意のものでよい。オペレーティング・システム（ＯＳ）は、後述する図２では、参照番号２０２で示される。
【００２２】
ハードディスク・ドライブ１０８にはさらに、Java(R)仮想マシン（ＪＶＭ）２０４（図２）を実現するためのJava(R) Runtime Environmentプログラムが格納されている。
【００２３】
ハードディスク・ドライブ１０８にはさらに、ＪＶＭ上で動作する、インターナショナル・ビジネス・マシーンズ・コーポレーションから提供されるミドルウェアである、WebSphere(R) Commerceが導入されている。ミドルウェアは、後述する図２では、参照番号２０６で示される。
【００２４】
ハードディスク・ドライブ１０８にはさらに、ミドルウェア上で動作する、プログラム群２０８が導入されている。プログラム群には、この発明に従い、バイトコード・レベルでプログラムを変更する変換プログラムが含まれる。変換プログラムは、後述する図２では、参照番号２１０で示される。
【００２５】
ハードディスク・ドライブ１０８にはまた、Apacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存されている。
【００２６】
キーボード１１０及びマウス１１２は、オペレーティング・システムが提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ１１４に表示されたアイコン、タスクバー、テキストボックスなどのグラフィック・オブジェクトを操作するために使用される。
【００２７】
ディスプレイ１１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。ディスプレイ１１４は例えば、ＪＶＭ上で実行されるアプリケーション・プログラムによる動作の結果を表示するために使用される。
【００２８】
通信インターフェース１１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース１１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、その処理結果を、クライアント・コンピュータ（図示しない）に返す。
【００２９】
次に図２を参照して、本発明を実施するためのソフトウェアの階層を説明する。図２において、オペレーティング・システム２０２上でＪＶＭ２０４が動作し、ＪＶＭ２０４上で、WebSphere(R) Commerceであるミドルウェア２０６が動作し、ミドルウェア２０６の管理の下に、Map.get処理を含むようなプログラム群２０８が配置され、変換プログラム２１０は、本発明の特徴に従い、バイトコード・レベルでプログラム群２０８のMap.get処理を最適化する処理を実行する。
【００３０】
次に、図３を参照して、変換プログラム２１０の処理について説明する。図３において、ステップ３０２では、変換プログラム２１０は、jprofあるいは、IBM(R) Health Centerなどのプロファイラ・ツールを使って、Mapのgetメソッドを頻繁に呼んでいる呼び出し元(caller)プログラムを特定する。図４に、複数のプログラム間の呼び出し関係の例を示す。
【００３１】
呼び出し元プログラムを特定すると、変換プログラム２１０はステップ３０４で、呼び出し元プログラムの呼び出し後に、Key、Value、スタック・トレース(StackTrace)をサンプリングするコードを挿入する。そのコードは例えば、次のようなものである。このコードは、ソースコード・レベルで挿入してもよいし、バイトコード・レベルで挿入してもよい。
String value = map.get(key);
try {
throw new Exception();
} catch (Exception ex) {
StackTraceElement[] cc = ex.getStackTrace();
profile(cc, key, value);
}
【００３２】
そのようにしてサンプリングした結果の例の一部を以下に示す。
X.m0 → A.m1 → B.m2→ Cache.get:“AAA”,“VA”
Y.m0 → C.m1 → B.m2 → Cache.get:“CCC”,“CA”
X.m0 → A.m1 → B.m2 → Cache.get:“AAA”,“VA”
AA.m1 → B.m2 → Cache.get:“AAA”,“VA”
X.m0 → A.m1 → B.m2 → Cache.get:“AAA”,“VA”
X.m0 → A.m1 → B.m2 → Cache.get:“AAA”,“VA”
AA.m1 → B.m2 → Cache.get “AAA”,“VA”
Y.m0 → C.m1 → B.m2 → Cache.get:“CCC”,“CA”
【００３３】
次に、変換プログラム２１０はステップ３０６で、上記サンプリングした結果から、同一のサンプルを特定する。それは以下のとおりである。
X.m0 → A.m1 → B.m2→ Cache.get:“AAA”,“VA”
AA.m1 → B.m2 → Cache.get:“AAA”,“VA”
Y.m0 → C.m1 → B.m2 → Cache.get:“CCC”,“CA”
【００３４】
次に、変換プログラム２１０はステップ３０８で、各メソッドと、そのメソッドがgetする値の対応をつける。それは以下の表のようになる。
【表１】
2014238770.tif 000003
【００３５】
次に、変換プログラム２１０はステップ３１０で、１対１で対応されているメソッドを特定する。それは以下の表の陰をつけた部分である。
【表２】
2014238770.tif 000004
【００３６】
次に、変換プログラム２１０はステップ３１２で、特定したメソッドのうち、最もMapのgetに近いメソッドのクラスを、get返値情報を保持するクラスと特定する。それは、図５の例では、太線で囲ったクラスである。なお、このようなクラスの階層関係は、上記スタック・トレースから呼び出しコンテキストを取得し、呼び出しコンテキストを利用することで知ることができる。
【００３７】
次に、変換プログラム２１０はステップ３１４で、特定したメソッドからgetまでの全メソッドに対し、get返値情報を引数として追加されたメソッドを生成する。これは例えば、Memを引数にとることであり、
B.m2(A.class.GetName(),...); を
B.m2(A.class.GetName(),...,mem); に修正することである。
【００３８】
次に、変換プログラム２１０はステップ３１６で、特定したメソッドからgetまで、get返値情報を引数として追加されたメソッドを呼び出すように修正する。図６は、修正されたコードの呼び出しを示す。
【００３９】
特に図６において、class ConcurrentHashMap<K,V> {...}における、
Object m = mem.validate(map,key,mem);
return m != null ? m : mem.initialize(map.getEntry(key));
というコードは、get返値memの妥当性をvalidate(map,key,mem)でチェックし、妥当であればmを返し、そうでないなら、get返値情報の初期化を行うことを示す。
【００４０】
下記はConcurrentHashMap.getのコードのより具体的な実装例を示す。
public V get(Object key, Mem<K, V> memo) {
HashEntry<K, V> memoEntry =
memo.validate(this, key);
if (memoEntry != null)
return memoEntry.value;
int hash = hash(key);
HashEntry<K, V> ret =
segmentFor(hash).getEntry(key, hash);
memo.initialize(ret);
if (ret == null)
return null;
else
return ret.value;
}
【００４１】
また、上記ConcurrentHashMap.getのコードの中で使用されているMemというクラスのコードの例を示す。ここには、initialize()とvalidate()というメソッドの実装も示されている。
public static class Mem<K, V> {
ConcurrentHashMap.HashEntry<K, V> value;
V initialize(HashEntry<K, V> value) {
this.value = value;
return value.value;
}
V  validate(
ConcurrentHashMap<K, V> map, 
Object key) {
HashEntry<K, V> memoEntry = value;
if (memoEntry != null //
// 1. HashEntry.delete is volatile
&& !memoEntry.delete
// 2. HashEntry.parent is final
&& memoEntry.parent == map
// 3. HashEntry.key is final 
&& key.equals(memoEntry.key))
return memoEntry.value;
else
return null;
}
}
【００４２】
以上、本発明を、ＪＶＭ上に導入したミドルウェアであるWebSphere(R) Commerce上でMap.getを実装する例において説明したきたが、このような構成は一例に過ぎず、Map.getの実装を可能ならしめる任意の構成において本発明を実施可能であることを理解されたい。
【符号の説明】
【００４３】
１０４      ＣＰＵ
１０６      ＲＡＭ
１０８      ハードディスク・ドライブ
２０２      ＯＳ
２０４      ＪＶＭ
２０６      ミドルウェア
２１０      変換プログラム
【図１】
2014238770.tif 000005
【図２】
2014238770.tif 000006
【図３】
2014238770.tif 000007
【図４】
2014238770.tif 000008
【図５】
2014238770.tif 000009
【図６】
2014238770.tif 000010