(57)【要約】  【課題】  ヒープメモリ中の文字列オブジェクトを各ゲストＶＭ間で共有することを可能ならしめることにより、メモリ使用効率を向上させること。  【解決手段】  本発明に係るシステムは、同じメモリイメージのオブジェクトを複数ＪＶＭ間で利用するために、複数ゲストＶＭで共通して用いられる文字列オブジェクトを抽出してファイルにまとめ、実行開始時にそのファイルをメモリ上の予め決められたアドレスにマップし、実行時に文字列オブジェクトを生成しようとするとき、マップされたファイル中の文字列オブジェクトを検索して、同じものがあればそれを利用できるようにする。アプリケーションやコンポーネント毎に共有する文字列データセットが抽出しまとめられる。そのような共有する文字列データセットを用意するため、本発明に係るシステムは、複数ゲストＶＭ上の複数ＪＶＭ上で、一つ、もしくは複数のJava(R)プログラムを実行する。【選択図】  図６
2014174966.tif 000002
【特許請求の範囲】
【請求項１】
複数のゲストＶＭの各々で、アプリケーション・プログラムが実行されているコンピュータ・システムにおいて、
前記各ゲストＶＭで、前記各アプリケーション・プログラムが使用している各々のヒープ領域から、共通に存在する文字列を抽出するステップと、
前記抽出された共通に存在する文字列を、前記各アプリケーション・プログラムがアクセス可能に、前記システムのメモリに配置するステップを有する、
方法。
【請求項２】
前記ゲストＶＭが複数のＪＶＭを含み、前記アプリケーション・プログラムがJavaプログラムであり、前記抽出された共通に存在する文字列は、前記ＪＶＭが、クラス定義を毎回同じアドレスで行うようになされ、以って前記抽出された共通に存在する文字列のオブジェクトが、クラス・ポインタが前記複数のゲストＶＭ間で同一になるようになされる、請求項１に記載の方法。
【請求項３】
前記文字列のオブジェクトは、DLLとしてメモリにロードされる、請求項２に記載の方法。
【請求項４】
前記抽出された共通に存在する文字列を、文字列の長さ、または作られ方の特性でグループ分けするステップと、
前記グループ分けされた文字列のグループ毎に、対象文字列の検索を行うためのハッシュインデックスを構築するステップを更に有する、
請求項１に記載の方法。
【請求項５】
前記ハッシュインデックスを構築するステップは、
文字列において、情報エントロピーの高さの観点から、インデックスに使う位置を見つけるステップと、
前記見つけたインデックスのところで、複数のハッシュ関数を計算し、該複数のハッシュ関数のうち最も衝突が少ないハッシュ関数を選ぶステップと、
前記文字列をビットシフトして、最も衝突の少ないシフト位置を選ぶステップを有する、
請求項４に記載の方法。
【請求項６】
複数のゲストＶＭの各々で、アプリケーション・プログラムが実行されているコンピュータ・システムにおいて、
前記コンピュータ・システムに、
前記各ゲストＶＭで、前記各アプリケーション・プログラムが使用している各々のヒープ領域から、共通に存在する文字列を抽出するステップと、
前記抽出された共通に存在する文字列を、前記各アプリケーション・プログラムがアクセス可能に、前記システムのメモリに配置するステップを実行させる、
プログラム。
【請求項７】
前記ゲストＶＭが複数のＪＶＭを含み、前記アプリケーション・プログラムがJavaプログラムであり、前記抽出された共通に存在する文字列は、前記ＪＶＭが、クラス定義を毎回同じアドレスで行うようになされ、以って前記抽出された共通に存在する文字列のオブジェクトが、クラス・ポインタが前記複数のゲストＶＭ間で同一になるようになされる、請求項６に記載のプログラム。
【請求項８】
前記文字列のオブジェクトは、DLLとしてメモリにロードされる、請求項７に記載のプログラム。
【請求項９】
前記コンピュータ・システムに、
前記抽出された共通に存在する文字列を、文字列の長さ、または作られ方の特性でグループ分けするステップと、
前記グループ分けされた文字列のグループ毎に、対象文字列の検索を行うためのハッシュインデックスを構築するステップを更に実行させる、
請求項６  に記載のプログラム。
【請求項１０】
前記ハッシュインデックスを構築するステップは、
文字列において、情報エントロピーの高さの観点から、インデックスに使う位置を見つけるステップと、
前記見つけたインデックスのところで、複数のハッシュ関数を計算し、該複数のハッシュ関数のうち最も衝突が少ないハッシュ関数を選ぶステップと、
前記文字列をビットシフトして、最も衝突の少ないシフト位置を選ぶステップを有する、
請求項９に記載のプログラム。
【請求項１１】
複数のゲストＶＭの各々で、アプリケーション・プログラムが実行されているコンピュータ・システムにおいて、
前記各ゲストＶＭで、前記各アプリケーション・プログラムが使用している各々のヒープ領域から、共通に存在する文字列を抽出する手段と、
前記抽出された共通に存在する文字列を、前記各アプリケーション・プログラムがアクセス可能に、前記システムのメモリに配置する手段を有する、
コンピュータ・システム。
【請求項１２】
前記ゲストＶＭが複数のＪＶＭを含み、前記アプリケーション・プログラムがJavaプログラムであり、前記抽出された共通に存在する文字列は、前記ＪＶＭが、クラス定義を毎回同じアドレスで行うようになされ、以って前記抽出された共通に存在する文字列のオブジェクトが、クラス・ポインタが前記複数のゲストＶＭ間で同一になるようになされる、請求項１１に記載のコンピュータ・システム。
【請求項１３】
前記文字列のオブジェクトは、DLLとしてメモリにロードされる、請求項１２に記載のコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、１つのコンピュータ・システムの上で複数のゲスト環境（オペレーティング・システムやJava(R) VM）が動作する環境において、文字列データを処理する技法に関するものである。
【背景技術】
【０００２】
従来より、１つのコンピュータ・システム（マシンとも呼ばれる）複数のゲスト環境が動作する環境において、物理メモリの使用効率を上げることは重要な課題である。その際、ほぼ同一のソフトウェア群が、複数のゲストＶＭで動作する環境では、各ゲストＶＭが同じ文字列データを生成するので、無駄がある。
【０００３】
これを解消するための１つの従来技法として、ＪＶＭのClass sharing機能を拡張して、ＪＶＭのクラスデータ等を複数ゲストＶＭ間で共有する手法が知られている。これに関するより詳しい情報は、http://www.ibm.com/developerworks/jp/java/library/j-shared/などを参照されたい。
【０００４】
また、ＪＶＭ起動時に生成される文字列オブジェクトのキャッシュファイルを作成し、各ゲストＶＭで共有する手法も知られている。しかしこのとき、キャッシュファイルが共有されるだけで、オブジェクトそのものは各ＪＶＭ内で作り直さなくてはならず、共有できない。
【０００５】
特開２００２−２２９７９３号公報は、Ｊａｖａ(R)プログラムにおいて、各変数名および各メソッド名として文字または文字列を割り当てるに際して、変数名グループと、引数型別のメソッド名グループからなる複数のグループについて、１つのグループ内では個別の対象に対してそれぞれ固有の文字または文字列を割り当てるとともに、複数のグループ間では個別の対象に対して適宜に共通の文字または文字列を割り当てることを開示する。しかし、この先行技術には、割り当てた文字列を検索する技法についての記述はない。
【０００６】
米国特許公開第２０１２／００１７２０４号明細書は、ＪＶＭ起動時に生成される文字列オブジェクトをキャッシュファイルに入れ、次回起動時以降は、キャッシュファイルから文字列オブジェクトを生成することで、ＪＶＭ起動時に重複して生成される文字列オブジェクトを削減することを開示する。この技法においては、ＪＶＭが起動するまでに重複して生成される文字列しか対象にされない。また、キャッシュファイルをロードした後で、インターン・テーブルに文字列オブジェクトを格納し直さなくてはならない。
【０００７】
米国特許第７７０７５８３号明細書は、ランタイム・システムにおいてオブジェクトを共有し、スケーラブル・マネジャにおけるユーザ・セッション間を隔離する技法を開示する。この技法において、ユーザ・セッションに対応するユーザ・コンテキストが、共有メモリ領域にストアされる。そして、当該ユーザ・セッションに対応するリクエストを受領すると、一組のオペレーティング・システム・プロセスから１つのプロセスが選択され、一組のランタイム・システムから、１つのランタイム・システムが選択される。この技法においては、複数仮想マシン間でクラスやオブジェクトを共有することで、物理メモリ使用量が削減される。また、クラス単位で共有可能なオブジェクトを分類し、どんな型のオブジェクトを共有するかユーザーが判断することが可能ならしめられる。しかし、この先行技術には、高速に共有オブジェクトを検索する技法についての記述はない。
【０００８】
米国特許公開第２００４／００４９４９３号明細書は、バケットペイロードのＡＳＣＩＩ文字列に基づいてルーティングを行うための文字列検索手法を開示する。この手法において、登録文字列は、一つのハッシュテーブルに登録される。検索時、ハッシュテーブルから検索文字列を探す前に、配列に部分文字列を検索しに行き、登録されている可能性がない文字列検索は即座に打ち切られる。さらに、配列は２つ用意され、ハッシュテーブルとともに階層的に構成される。この技法は、検索の早い段階で該当しない文字列の検索を打ち切ることは示すものの、検索を高速化するための文字列の格納の工夫については示唆するものではない。
【０００９】
米国特許第７４１８５０５号明細書は、ＩＰアドレスのプリフィックス長毎にハッシュテーブルを分け、ハッシュテーブル中の値の衝突を減らすことで、ルーティングを高速に行うための手法を開示する。しかし、この技法においては、ハッシュテーブル中の値の衝突をできるだけ回避する準備を限定的にしか行うことができない。
【００１０】
Kiyokuni Kawachiya, Kazunori Ogata, Tamiya Onodera. "Analysis and Reduction of Memory Inefficiencies in Java Strings,", In Proceedings of the 23rd Annual ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '08), pp. 385-401 (Oct. 2008).は、Java(R)ヒープにおいて、重複した文字列と使用されていないリテラルに着目することにより、メモリの使用効率を向上することを開示する。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−２２９７９３号公報
【特許文献２】米国特許公開第２０１２／００１７２０４号明細書
【特許文献３】米国特許第７７０７５８３号明細書
【特許文献４】米国特許公開第２００４／００４９４９３号明細書
【特許文献５】米国特許第７４１８５０５号明細書
【非特許文献】
【００１２】
【非特許文献１】http://www.ibm.com/developerworks/jp/java/library/j-shared/
【非特許文献２】Kiyokuni Kawachiya, Kazunori Ogata, Tamiya Onodera. "Analysis and Reduction of Memory Inefficiencies in Java Strings,", In Proceedings of the 23rd Annual ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '08), pp. 385-401 (Oct. 2008).
【発明の概要】
【発明が解決しようとする課題】
【００１３】
この発明の目的は、ヒープメモリ中の文字列オブジェクトを各ゲストＶＭ間で共有することを可能ならしめることにより、メモリ使用効率を向上させることにある。
【００１４】
この発明の他の目的は、共有されたヒープメモリ中の文字列オブジェクトを高速で検索できる技法を提供することにある。
【課題を解決するための手段】
【００１５】
この発明は、複数ゲストＶＭ間で共有可能な文字列オブジェクトを直接参照可能な形式で保存しておき、実行時に効率よく探索することを可能ならしめることにより、上記課題を解決するものである。
【００１６】
この発明は、これには限定されないが、好適な実装は、Java(R)による実装である。
【００１７】
Java(R)による実装の場合、本発明に係るシステムは、同じメモリイメージのオブジェクトを複数ＪＶＭ間で利用するために、複数ゲストＶＭで共通して用いられる文字列オブジェクトを抽出してファイルにまとめ、実行開始時にそのファイルをメモリ上の予め決められたアドレスにマップし、実行時に文字列オブジェクトを生成しようとするとき、マップされたファイル中の文字列オブジェクトを検索して、同じものがあればそれを利用できるようにする。
【００１８】
その際、アプリケーションやコンポーネント毎に共有する文字列データセットが抽出しまとめられる。そのような共有する文字列データセットを用意するため、本発明に係るシステムは、複数ゲストＶＭ上の複数ＪＶＭ上で、一つ、もしくは複数のJava(R)プログラムを実行する。そのJava(R)プログラムは、各ＪＶＭのJava(R)ヒープ内に存在する文字列データをそれぞれ抽出し、異なるマシン上のＪＶＭから共通して出現した文字列データを共有対象文字列データとする。このとき、ＪＶＭプロセスのアドレス空間にマップするだけで、共有対象文字列データをJava(R)オブジェクトとして直接参照可能である。
【００１９】
この発明の１つの側面においては、文字列オブジェクトの高速検索を可能ならしめるため、対象データの特性に基づきグループ分けし、対象オブジェクトの検索が一番高速になるデータ構造をグループ毎に使用するようにする。ここでいう対象データの特性とは、文字列の長さ、文字列オブジェクトが生成されるクラスファイル、jarファイルなどのことである。このようなグループ分けされた文字列毎にハッシュテーブルが作成され、後で、ハッシュテーブルを用いて文字列が高速検索される。
【発明の効果】
【００２０】
この発明によれば、ヒープメモリ中の文字列オブジェクトを各ゲストＶＭ間で共有することにより、メモリ使用効率を向上させるという効果が得られる。
【００２１】
また、好適には文字列オブジェクトを対象データの特性に基づきグループ分けし、対象オブジェクトの検索が一番高速になるデータ構造をグループ毎に使用するようにしたことにより、文字列検索の効率が向上する。
【図面の簡単な説明】
【００２２】
【図１】本発明を実施するためのハードウェア構成の一例のブロック図である。
【図２】複数仮想マシン環境を示す図である。
【図３】１つのゲストＶＭ中に複数のＪＶＭが起動されている状態を示す図である。
【図４】複数のゲストＶＭから、共通対象文字列を集める処理のフローチャートを示す図である。
【図５】共通対象文字列から文字列を検索するためのハッシュ関数とビットシフト量を決定する処理のフローチャートを示す図である。
【図６】グループ分けした文字列において、ハッシュ関数とビットシフト量を決定する処理を図式的に示す図である。
【図７】グループ内の文字列データから、ハッシュ関数で使用するインデックスを求める処理のフローチャートを示す図である。
【図８】ハッシュの衝突が最も少なかったハッシュ関数を決定する処理のフローチャートを示す図である。
【図９】ハッシュテーブルインデックス値の衝突が最も少なかったシフト演算を求める処理のフローチャートを示す図である。
【図１０】ハッシュテーブルインデックスと、ビットシフトの関係を示す図である。
【図１１】DLLにおける共有文字列データを格納するための構造体を示す図である。
【図１２】DLLにおける共有文字列データを具体的に格納した状態を示す図である。
【図１３】複数のＪＶＭが起動されている状態におけるメモリマップを示す図である。
【図１４】Stringコンストラクタ呼び出し処理のフローチャートを示す図である。
【図１５】String.intern()呼び出し処理のフローチャートを示す図である。
【発明を実施するための形態】
【００２３】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２４】
図１を参照すると、参照番号１００で総称される、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・バス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のCore(商標) i3、Core(商標) i5、Core(商標) i7、Xeon(R)、AMD社のAthlon(商標)、Phenom(商標)、Sempron(商標)などを使用することができる。主記憶１０６は、好適には、８ＧＢ以上の容量、より好ましくは、１６ＧＢ以上の容量をもつものである。
【００２５】
ハードディスク・ドライブ１０８には、図２に示すように、複数の仮想マシン（ＶＭ）を実現するためのハイパーバイザ２０２が導入されている。ハイパーバイザ２０２として利用可能なプログラムとして、これには限定されないが、VMWare(R)、Xenなどがある。ここでは、Xenを用いるものとして説明する。
【００２６】
ハイパーバイザ２０２上には、ホストＶＭ２０４及び、複数のゲストＶＭ２０６ａ、２０６、・・・、２０６ｎが構成される。ホストＶＭ２０４は、Xenではドメイン０とも呼ばれ、ハイパーバイザ２０２を介してハードウェア１００とインターフェースするデバイス・ドライバが含まれている。これにより、ゲストＶＭ２０６ａ、２０６ｂ、・・・、２０６ｎは、ホストＶＭ２０４を介して、ハードウェア１００とインターフェースすることになる。
【００２７】
ハードディスク・ドライブ１０８には、オペレーティング・システム（ＯＳ）が格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows(商標)2008サーバなどの、ＣＰＵ１０４に適合する任意のものでよい。オペレーティング・システム（ＯＳ）は、後述する図３では、参照番号３０２で示される。
【００２８】
ハードディスク・ドライブ１０８にはさらに、Java(R)仮想マシン（ＪＶＭ）２０４（図２）を実現するためのJava(R) Runtime Environmentプログラムが格納されている。ＪＶＭは、後述する図３では、参照番号３０６ａ、３０６ｂ、・・・、３０６ｍで示される。
【００２９】
ハードディスク・ドライブ１０８にはさらに、ＪＶＭ上で動作するJava(R)アプリケーション・プログラムが格納されている。この実施例では、Java(R)アプリケーション・プログラムは、インターナショナル・ビジネス・マシーンズ・コーポレーションから提供される、WebSphere(R) Application Serverを含む。Java(R)アプリケーション・プログラムは、後述する図３では、参照番号３０８ａ、３０８ｂ、・・・、３０８ｍで示される。
【００３０】
ハードディスク・ドライブ１０８にはまた、Apacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存されている。
【００３１】
キーボード１１０及びマウス１１２は、オペレーティング・システムが提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ１１４に表示されたアイコン、タスクバー、テキストボックスなどのグラフィック・オブジェクトを操作するために使用される。
【００３２】
ディスプレイ１１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。ディスプレイ１１４は例えば、ＪＶＭ上で実行されるアプリケーション・プログラムによる動作の結果を表示するために使用される。
【００３３】
通信インターフェース１１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース１１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、ホストＶＭ２０４がその処理リクエストを指定されたゲストＶＭに送り、その処理結果をゲストＶＭから受け取って、クライアント・コンピュータ（図示しない）に返す。
【００３４】
次に図３を参照して、ゲストＶＭについて説明する。ゲストＶＭ２０６ａ、２０６ｂ、・・・、２０６ｎはどれも機能的に同一であるので、ここでは代表的に、ゲストＶＭ２０６ａとして説明する。
【００３５】
すると、図３に示すように、ゲストＶＭ２０６ａは、ＯＳ３０２上に、各々ＪＶＭ３０６ａ、３０６ｂ、・・・、３０６ｍとアプリケーション・プログラムを含む、複数の仮想マシン３０４ａ、３０４ｂ、・・・、３０４ｍを含みえる。
【００３６】
このような前提で、図４以下のフローチャートを参照して、本発明の処理について説明する。図４に示す処理は、各々のゲストＶＭにおけるJava(R)プログラム毎に実行されるので、複数のゲストＶＭに亘る処理として、ホストＶＭ２０４に、全体の処理を制御するプログラムを配置することができる。
【００３７】
図４において、本発明のプログラムは、ステップ４０２で、あるゲストＶＭにおけるJava(R)プログラムを実行する。次にステップ４０４で、本発明のプログラムは、そのゲストＶＭにcoreファイルを出力させる。なお、ここでいうcoreファイルとは、ＪＶＭにおけるシステム・ダンプファイルのことである。システム・ダンプファイルは好適には、ハードディスク・ドライブ１０８の所定のディレクトリに書き出される。
【００３８】
次にステップ４０６で、本発明のプログラムは、coreファイルから文字列オブジェクトの情報を取り出す。
【００３９】
こうして、すべてのゲストＶＭにおいて、Java(R)プログラムの実行結果のcoreファイルから文字列オブジェクトの情報を取り出すと、本発明のプログラムは、ステップ４０８で、複数のゲストＶＭから情報を集め、ステップ４１０で、複数のcoreファイルに出現する文字列データを共通対象文字列とする。
【００４０】
このように複数のゲストＶＭから情報を集められた共通対象文字列の集合データのままでは、文字列の検索に時間がかかるので、本発明のプログラムは、図５のフローチャートで示す処理により、共通対象文字列の集合データに対して、検索キーをつける。
【００４１】
すなわち、ステップ５０２で、本発明のプログラムは、文字列対象データを特性に基づきグループ分けする。ここでいう対象データの特性とは、文字列の長さ、文字列オブジェクトが生成されるクラスファイル、jarファイルなどのことである。このうち一番典型的な特性は文字列の長さである。
【００４２】
本発明のプログラムは、ステップ５０４で、このようにしてグループ分けした全ての文字列を使い、何番目の文字がグループ内で文字の種類が多いかを調べ、種類の多い上位数個の文字インデックスをハッシュ計算に用いる。なお、ステップ５０４の詳細は、図７のフローチャートを参照して後で説明する。
【００４３】
図６は、文字列の長さでグループ分けされた文字列に対する処理を図式的に示す図である。図示されているのは、長さ９の文字列の処理と、長さ１０の文字列の処理と、長さ１２の文字列の処理の場合である。ここでは、文字列を並べた列の範囲で情報エントロピーの高い３個から４個のインデックスが選ばれる。
【００４４】
本発明のプログラムは、ステップ５０６で、予め用意しておいたハッシュ関数の中から、ハッシュ値の衝突が最も少なかったものを選ぶ。ここで、予め用意しておいたハッシュ関数とは、図６ではhashFn1、hashFn2、・・・、hashFn10のように示されているものである。予め用意しておいたハッシュ関数の例としては次のようなものがある。下記の式で、ch1、ch2、ch3、ch4は、選ばれたインデックスにおける文字列の値である。なお、これらのハッシュ関数は一例であって、当業者が思いつく様々な他のハッシュ関数も使用可能である。また、ステップ５０６の詳細は、図８のフローチャートを参照して後で説明する。
【００４５】
int hash = ch1 * ch2 + ch3;
return (hash * hash);
【００４６】
int hash = ch1 * ch2 * ch3;
return (hash * hash);
【００４７】
int hash = ch1 * ch2 * ch3 + ch4;
return (hash * hash);
【００４８】
本発明のプログラムは、ステップ５０８で、インデックスを求めるときに、全てのシフト演算を試して衝突が最も少なかった計算方法を選ぶ。これは、図６では、1ビット・シフト、・・・、nビット・シフトとして示されている。ステップ５０８の詳細は、図９のフローチャートを参照して後で説明する。
【００４９】
次に、図７のフローチャートを参照して、ステップ５０４の詳細を説明する。図７のフローチャートは、グループ内の文字列の処理に関するものであって、ステップ７０２で、本発明のプログラムは、ｉ番目の文字が何種類あるか数える。このとき、文字列の長さがｉ未満のものは数え上げの対象から外す。
【００５０】
ステップ７０４で、本発明のプログラムは、種類の多かった上位数個のインデックスを求める。こうしてステップ７０６で、ハッシュ関数で使用する、複数個の文字列インデックスが得られる。
【００５１】
次に、図８のフローチャートを参照して、ステップ５０６の詳細を説明する。図８のフローチャートは、グループ内の文字列データと文字列インデックス、すなわち何番目の文字を計算に使用するかを用いるものであって、本発明のプログラムは、ステップ８０２で、与えられた文字列インデックスを使って、上述したような予め用意したハッシュ関数でハッシュ値を計算し、これをグループ内の全ての文字列に対して繰り返す。ステップ８０４で本発明のプログラムは、ハッシュ値の衝突した回数を数える。
【００５２】
本発明のプログラムは、ステップ８０２とステップ８０４を、予め用意しておいた全てのハッシュ関数について繰り返し、ステップ８０６で、ハッシュ値の衝突が最も少なかったハッシュ関数を選ぶ。
【００５３】
次に、図９のフローチャートを参照して、ステップ５０８の詳細を説明する。図９のフローチャートは、グループ内の文字列データそれぞれに対してハッシュ関数を適用したときのハッシュ値を用いるものであって、本発明のプログラムは、ステップ９０４で、図１０に示すように、nビットだけ右シフトして、Lビットをハッシュテーブルインデックスと計算する。ここでLは、ハッシュテーブルのサイズに依存する定数である。次に本発明のプログラムはステップ９０６で、ハッシュテーブルインデックス値の衝突した回数を数え、ステップ９０４とステップ９０６を、右シフト可能なビット数分だけ繰り返し、ステップ９０８で、ハッシュテーブルインデックス値の衝突が最も少なかったシフト演算が選ばれる。
【００５４】
この結果、例えば、情報エントロピーが高いインデックスが、3、4、6であり、ハッシュ値の衝突が最も少なかったハッシュ関数がhashFn3であり、2ビット分だけ右シフトした演算のハッシュテーブルインデックスの衝突が最も少なかったとすると、長さ9の文字を見出すために使用されるインデックスindexは、以下のようにして計算されることになる。
int hc = hashFn3(char, offset,3,4,6);
int index = (hc >> 2 & ((1 << 12) - 1);
【００５５】
ここで、ハッシュテーブルインデックスについて補足する。この実施例では、共有文字列を格納するためにグループごとにハッシュテーブルを用意している。すると、共有文字列をハッシュテーブルに格納するためには、ハッシュテーブルのどの位置（インデックス）に格納するかを決める必要がある。
【００５６】
文字列を入力としてハッシュ関数で計算されるが、その計算結果がハッシュテーブルのインデックスに必ずしも一対一対応するわけではない。そこで、計算結果を補正してハッシュテーブルのインデックスの範囲内に収める必要がある。その補正をするのが「nビット分だけ右シフトして、Lビットをハッシュテーブルインデックスとして使用する」処理である。
【００５７】
ハッシュテーブルを利用する際にポイントとなるのが、ハッシュテーブルの同じインデックスにはできるだけひとつの文字列しか格納しない、という方針である。となると、グループ内の文字列を用いて得る結果：
(1) ハッシュ関数での計算の結果
(2) インデックス計算での結果
で(2)が可能な限りばらけるように工夫する必要がある。(2)がばらけるためには、(1)の値がそもそもばらけていることが望ましい。それが「予め用意しておいたハッシュ関数の中からハッシュ値の衝突が最も少なかったものを選ぶ」処理である。
【００５８】
さらに、(1)を得るために入力として文字列を使うわけであるが、文字列のすべての情報を使う必要はない。そこで、グループ内の文字列を調べて、必要そうな場所だけを取り出して使う。例えば、"ISOLATION"、"ASSERTION","ASSOCIATE"という３つの文字列があるグループに属するとする。このとき、以下のように並べてみると、
"ISOLATION"
"ASSERTION"
"ASSOCIATE"
グループ内の文字列の中で最も違いが出るインデックス3,4だけを使えば十分であることが分かる。
【００５９】
本発明のプログラムは、共有文字列を保存したDLLを作成し、JVMがそのDLLを、毎回同じアドレスにロードするようにする。これは、Linux(商標)の場合、prelinkコマンドを使用して達成できる。
【００６０】
そして、JVM起動時、Stringとchar[]のClassだけDLLの書き込み可能な場所に置く。図１１は、このための、共有文字列テータとしてのjava.lang.Stringとchar[]の構造体string_len3の定義を示す。このような構造体は、java.lang.Stringとchar[]を一組として文字列の長さごとに定義される。図１２は、string_len3に実際に値が格納された様子を示す。なお、図１２には、java.lang.Stringとchar[]の組が２つしか示されていないが、実際はもっと多数含まれることを理解されたい。
【００６１】
図１３は、単一のゲストＶＭ中の複数のＪＶＭに亘って、共有文字列を保存したDLLが同一アドレスでロードされている様子を示す図である。これにより、各ＪＶＭは同様に且つ独立にDLL中に定義された共有文字列を検索することができる。その検索の際に、共有文字列テータのグループ毎に選ばれたハッシュ関数とインデックスが使用される。なお、共有文字列は好適には、ヒープ外(off-heap)に配置される。なお、ＪＶＭからヒープ外メモリへのアクセスは、JNI(Java(R) Native Interface)などの技法を用いて達成することができる。
【００６２】
図１４は、Java(R)プログラムにおける、Stringコンストラクタの呼び出し処理のフローチャートを示す図である。ステップ１４０２ではプログラムは、引数のchar[]が表す文字列の特性（長さ）などをチェックする。
【００６３】
そして、ステップ１４０４で特性に対するグループがあるかどうか判断し、もしないならプログラムは、ステップ１４０６でStringオブジェクトをnewする。もし特性に対するグループがあるなら、プログラムは、引数のchar[]が表す文字と同じものがグループ内にあるかどうか、上記したDLLにアクセスして検索する。
【００６４】
そして、プログラムは、ステップ１４１０で文字列が見つからなかったと判断すると、ステップ１４１２でStringオブジェクトをnewする。プログラムは、ステップ１４１０で文字列が見つかったと判断すると、ステップ１４１４で、StringをnewしてDLL内のchar[]を参照する。
【００６５】
図１５は、Java(R)プログラムにおける、String.intern()の呼び出し処理のフローチャートを示す図である。ステップ１５０２ではプログラムは、引数のchar[]が表す文字列の特性（長さ）などをチェックする。
【００６６】
そして、ステップ１５０４で特性に対するグループがあるかどうか判断し、もしないならプログラムは、ステップ１５０６でString.intern()を実行する。もし特性に対するグループがあるなら、プログラムは、引数のchar[]が表す文字と同じものがグループ内にあるかどうか、上記したDLLにアクセスして検索する。
【００６７】
そして、プログラムは、ステップ１５１０で文字列が見つからなかったと判断すると、ステップ１５１２でString.intern()を実行する。プログラムは、ステップ１５１０で文字列が見つかったと判断すると、ステップ１５１４で、DLL内のStringオブジェクトを返す。
【００６８】
以上、ゲストＶＭにおけるＪＶＭでの実装の上で本発明の実施例を説明してきたが、これには限定されず、複数のＶＭ環境から使用文字列を取り出して、数のＶＭ環境に対して共通文字列をアクセス可能ならしめることができるような任意の環境に、この発明は適用可能であることを理解されたい。すなわち、本発明は特定の言語環境やプラットフォームに限定されないで実施可能である。
【００６９】
また、複数のＶＭ環境から、共通文字列をアクセス可能ならしめる仕組みとして、上記実施例ではDLLが使用されたが、これは一例に過ぎず、ヒープ外メモリなど、個別のＪＶＭの管理外のメモリ配置するなら、任意の方法でメモリを配置してよい。
【符号の説明】
【００７０】
１０４                                ＣＰＵ
１０６                                ＲＡＭ
１０８                                ハードディスク・ドライブ
２０４                                ホストＶＭ
２０６ａ、２０６ｂ、・・・２０６ｎ    ゲストＶＭ
３０６ａ、３０６ｂ、・・・３０６ｍ    ＪＶＭ
【図１】
2014174966.tif 000003
【図２】
2014174966.tif 000004
【図３】
2014174966.tif 000005
【図４】
2014174966.tif 000006
【図５】
2014174966.tif 000007
【図６】
2014174966.tif 000008
【図７】
2014174966.tif 000009
【図８】
2014174966.tif 000010
【図９】
2014174966.tif 000011
【図１０】
2014174966.tif 000012
【図１１】
2014174966.tif 000013
【図１２】
2014174966.tif 000014
【図１３】
2014174966.tif 000015
【図１４】
2014174966.tif 000016
【図１５】
2014174966.tif 000017