(57)【要約】【課題】ガービッジコレクションのベンチマーキング方法及びガービッジコレクションワークロードを提供する。【解決手段】本発明はＪＡＶＡ（登録商標）仮想マシンのガービッジコレクションの性能を測定するためのＪＡＶＡ（登録商標）ガービッジコレクションワークロード、これを利用したベンチマーキング方法及び前記ベンチマーキング方法を実現させるためのプログラムを記録したコンピュータで読み出し可能な記録媒体に関するものである。ベンチマーキング方法は、ベンチマークファイルを生成し、前記ファイルをＪＡＶＡ（登録商標）仮想マシン上で実行することを含む。ベンチマークファイルを生成することは二進ツリーのデータ構造を有する客体を生成し、前記客体がこれ以上参照されないようにして、ガービッジコレクションを任意に発生するようにして、客体の繰り返しの再生成を通じてガービッジコレクションの負荷を高め、ベンチマークの結果を報告することを含む。【選択図】図７
2005071375.tif 000002
【特許請求の範囲】
【請求項１】
ベンチマークファイルを生成し、
前記ファイルはガービッジコレクションを支援するデータ処理装置で実行されることを含み、
前記ベンチマークファイルの生成は、
二進ツリーのデータ構造を有する客体を生成し、
前記客体がこれ以上参照されないようにして、新しい客体を再生成し、
ベンチマークの結果を報告することを含むことを特徴とするガービッジコレクションのベンチマーキング方法。
【請求項２】
前記データ処理装置は、ＪＡＶＡ（登録商標）仮想マシンであることを特徴とする請求項１に記載のガービッジコレクションのベンチマーキング方法。
【請求項３】
前記二進ツリーのデータ構造を有する客体の生成は、
境界客体をルートノードとして、前記境界客体と同一、または境界客体より小さい第１サイズの客体は左側ノードに分岐し、前記境界客体より大きい第２サイズの客体は右側に分岐し、各ノードでそのノードの客体のサイズと同一、またはそのノードの客体より小さい客体は左側ノードに分岐し、大きい客体は右側ノードに分岐するようにすることを特徴とする請求項１または請求項２に記載のガービッジコレクションのベンチマーキング方法。
【請求項４】
前記客体がこれ以上参照されないようにして、新しい客体を再生成するに際し、
同一の二進ツリー構造を維持するように、同一のサイズの客体を再生成し、前記第１サイズの客体ノード、前記ルーツノードおよび前記第２サイズの客体ノードの手順に客体を再生成することを特徴とする請求項３に記載のガービッジコレクションベンチマーキング方法。
【請求項５】
前記客体がこれ以上参照されないようにして、新しい客体を再生成するに際し、
前記二進ツリーの最上位の深さのノードから初めて、下位深さのノードに移動しながら客体を再生成し、特定深さのノードに対する客体の再生成はその特定の深さの下のすべての上位深さのノードに対する客体の再生成することを特徴とする請求項４に記載のガービッジコレクションベンチマーキング方法。
【請求項６】
前記二進ツリーデータ構造を有する客体を生成するに際し、客体の個数は同一であり、互いに違う構造を有する多数の二進ツリー構造を生成することを含み、
前記客体がこれ以上参照されないようにして、新しい客体を再生成するに際し、同時に多数の二進ツリー構造で進行されることを特徴とする請求項１または請求項２に記載のガービッジコレクションのベンチマーキング方法。
【請求項７】
前記二進ツリーのデータ構造を有する客体を生成するに際し、客体の個数は同一であり、互いに違う構造を有する多数の二進ツリー構造を生成することを含み、
前記客体がこれ以上参照されないようにして、新しい客体を再生成するに際し、同時に多数の二進ツリー構造で進行されることを特徴とする請求項５に記載のガービッジコレクションのベンチマーキング方法。
【請求項８】
前記各二進ツリー構造は互いに違う個数の第１サイズの客体および第２サイズの客体を含み、互いに違うサイズの境界客体を有することを特徴とする請求項６に記載のガービッジコレクションのベンチマーキング方法。
【請求項９】
前記各二進ツリー構造は互いに違う個数の前記第１サイズの客体および第２サイズの客体を含み、互いに違うサイズの境界客体を有することを特徴とする請求項７に記載のガービッジコレクションのベンチマーキング方法。
【請求項１０】
二進ツリーのデータ構造を有する客体を生成する前に、プログラムの実行の間に常にメモリを占める生存客体を生成することをさらに含むことを特徴とする請求項１または請求項２に記載のガービッジコレクションのベンチマーキング方法。
【請求項１１】
ベンチマークの結果を報告するに際し、全体メモリ、現在割り当てられたメモリおよび使用可能なメモリに対するサイズとベンチマーキングにかかる時間を報告することを含むことを特徴とする請求項１または請求項２に記載のガービッジコレクションのベンチマーキング方法。
【請求項１２】
前記ベンチマークファイルを生成する前に、実際の客体志向プログラムで生成される客体を分析して客体の個数、客数のサイズ、中間サイズの客体、よく生成される客体のサイズ、最大サイズの客体、最小サイズの客体を把握することをさらに含み、
前記二進ツリーのデータ構造を有する客体を生成するに際し、前記客体分析に基づいて前記中間サイズの客体をルートノードにして、前記ルートノードの客体と同一、またはルートノードの客体より小さい第１サイズの客体は左側ノードに分岐し、前記ルートノードの客体より大きい第２サイズの客体は右側ノードに分岐し、各ノードでそのノードの客体のサイズと同一、またはそのノードの客体より小さい客体は左側ノードに分岐し、そのノードの客体より大きい客体は右側ノードに分岐するようにすることを特徴とする請求項１または請求項２に記載のガービッジコレクションのベンチマーキング方法。
【請求項１３】
ガービッジコレクションをベンチマーキングするガービッジコレクションワークロードにおいて、
二進ツリーデータ構造を有する客体を生成する客体生成手段と、
生成された二進ツリーデータ構造の客体がこれ以上参照されないようにして、新しい客体を再生成する客体再生成手段と、
ベンチマーキングの結果を出力する報告手段とを含むことを特徴とするガービッジコレクションワークロード。
【請求項１４】
前記客体生成手段は境界客体をルートノードとして、前記境界客体と同一、または境界客体より小さい第１サイズの客体は前記ルートノードから左側ノードに分岐し、前記境界客体より大きい第２サイズの客体は前記ルートノードから右側ノードに分岐し、各ノードでそのノードの客体のサイズより小さい客体は左側ノードに分岐し、大きい客体は右側ノードに分岐するようにすることを特徴とする請求項１３に記載のガービッジコレクションワークロード。
【請求項１５】
前記客体再生成手段は、前記第１サイズの客体ノード、前記ルートノードおよび前記第２サイズの客体ノードの手順により客体に接近して以前の客体を除去し、同一の二進ツリー構造を有するように除去された客体と同一のサイズの客体を再生成することを特徴とする請求項１４に記載のガービッジコレクションワークロード。
【請求項１６】
前記客体再生成手段は、前記二進ツリーの最上位深さのノードから初めて下位深さのノードに移動しながら、客体を再生成し、特定深さの客体ノードに対する客体再生成はその特定深さの下のすべての上位深さのノードに対する客体に対する再生成を含むことを特徴とする請求項１５に記載のガービッジコレクションワークロード。
【請求項１７】
前記客体生成手段は互いに違う構造を有する多数の二進ツリー構造を生成することを特徴とする請求項１３乃至請求項１６のうちのいずれか一項に記載のガービッジコレクションワークロード。
【請求項１８】
プログラム実行の間にメモリを常に占めている客体を生成する生存客体生成手段をさらに含むことを特徴とする請求項１３に記載のガービッジコレクションワークロード。
【請求項１９】
ガービッジコレクションをベンチマーキングするためにガービッジコレクションを支援するデータ処理装置において、
二進ツリー構造の客体を生成する機能と、
生成された客体がこれ以上参照されないようにして、新しい客体を再生成する機能と、
ベンチマーキングの結果を報告する報告機能を実現させるためのプログラムを記録することを特徴とするコンピュータで読み出すことができる記録媒体。
【請求項２０】
前記データ処理装置はＪＡＶＡ（登録商標）仮想マシンであることを特徴とする請求項１９に記載のコンピュータで読み出すことができる記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＪＡＶＡ（登録商標）仮想マシンベンチマーキングに係り、さらに詳細には、ＪＡＶＡ（登録商標）仮想マシンのガービッジコレクションを公正に評価することができるＪＡＶＡ（登録商標）ガービッジコレクションベンチマーク及びその方法に関する。
【背景技術】
【０００２】
ＪＡＶＡ（登録商標）（Ｊａｖａ（登録商標））はプラットホーム中立的なプログラミング言語及び環境である。ＪＡＶＡ（登録商標）ソースコードはコンファイルされてＪＡＶＡ（登録商標）仮想マシン（Ｊａｖａ（登録商標） Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ:ＪＶＭ）上で実行される。ＪＡＶＡ（登録商標）仮想マシンが設けられたどのようなプラットホームもＪＡＶＡ（登録商標）アプリケーションを実行しうる。すなわち、ＪＡＶＡ（登録商標）ソースコードはバイトコードでコンファイルされ、ＪＡＶＡ（登録商標）仮想機械がＪＡＶＡ（登録商標）バイトコードを解釈して、それが設けられているプラットホーム上で実行される。ＪＡＶＡ（登録商標）バイトコードはＪＡＶＡ（登録商標）仮想マシンのマシン言語であると見なすことができる。ＪＡＶＡ（登録商標）仮想マシン側で見れば、バイトコードのストリームはインストラクションシーケンスである。
【０００３】
ＪＡＶＡ（登録商標）仮想マシンは、実際のハードウエアプラットホーム及びオペレーティングシステム上に設けられた仮想コンピュータとして、コンファイルされたＪＡＶＡ（登録商標）プログラムを実行する。このようなＪＡＶＡ（登録商標）仮想マシンによってＪＡＶＡ（登録商標）言語で作成されたプログラムは、他のコンピュータ上で実行するために再作成する必要はない。
【０００４】
ＪＡＶＡ（登録商標）仮想マシンの仮想ハードウエアはレジスタと、スタックと、ガービッジ−コレクトヒップと、メソッド領域の四つの部分で分けることができる。メソッド領域は、ＪＡＶＡ（登録商標）バイトコードが常在する領域である。ＪＡＶＡ（登録商標）スタックはバイトコード命令のためのパラメータ及びバイトコード命令の結果を貯蔵し、メソッドでパラメータを伝達するか、メソッドから値を受け、各メソッドの呼び出し状態を維持する。ＪＡＶＡ（登録商標）ガービッジ−コレクトヒップはＪＡＶＡ（登録商標）プログラムの客体がある自由貯蔵場所である。“ｎｅｗ”演算子供を使ってメモリを割り当てれば、ヒップからメモリが生成される。ＪＡＶＡ（登録商標）ランタイム環境はヒップ上の各客体に対する参照を追跡する。
【０００５】
ＪＡＶＡ（登録商標）システムで、ガービッジコレクションを通じてすべての客体はヒップから動的に割り当てられ、割り当てられた客体が放出(ｒｅｌｅａｓｅ)(割り当てられたメモリがシステムに返還)される。ガービッジコレクションアルゴリズムは、一般的に参照から到達可能な客体を決める。客体がこれ以上到逹することができない時(客体がこれ以上参照されない時)、プログラムによって明示的に割り当て解除(ｄｅａｌｌｏｃａｔｉｏｎ)されなくても、その客体が占めるメモリはシステムに返還され、再要求(ｒｅｃｌａｉｍ)されて再使用（ｒｅｕｓｅ）される。
【０００６】
ランタイムの間絶えず客体が生成され、ガービッジコレクションが実行されるので、ガービッジコレクションはＪＡＶＡ（登録商標）仮想マシンで時間を最も多く消費する構成（ｃｏｍｐｏｎｅｎｔ）のうちの一つである。したがって、ＪＡＶＡ（登録商標）仮想マシンの性能はＪＡＶＡ（登録商標）ガービッジコレクションによって大きく左右される。互いに違うＪＡＶＡ（登録商標）仮想マシンは互いに違うガービッジコレクション行動を示す。しかし、大部分のＪＡＶＡ（登録商標）ベンチマーク（ｂｅｎｃｈｍａｒｋ）は中央処理装置、またはサーバ及びクライアントの間のトランザクションの性能測定に合わせられている。したがって、互いに違うＪＡＶＡ（登録商標）仮想マシンのガービッジコレクションに対する公正で正確な評価はし難い。例えば、ＪＡＶＡ（登録商標）ガービッジコレクションの性能以外の他の構成の性能が向上しても、全体的なＪＡＶＡ（登録商標）仮想マシンの性能は良い結果を示す。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、互いに違うＪＡＶＡ（登録商標）仮想マシンのガービッジコレクションを公正で相対的な評価を可能にするＪＡＶＡ（登録商標）ガービッジコレクションベンチマーク及びその方法を提供するものである。
【課題を解決するための手段】
【０００８】
ガービッジコレクションをベンチマーキングするための本発明のガービッジコレクションワークロード（ｊａｖａ（登録商標） ｇａｒｂａｇｅ ｃｏｌｌｅｃｔｉｏｎ ｗｏｒｋｌｏａｄ）は、ガービッジコレクションを支援するデータ処理装置の客体割り当て及び自由客体の再要求の実行時間、メモリ状態(ヒップサイズ、割り当てられた空間、自由空間など)などを測定する。例えば、ガービッジコレクションを支援するデータ処理装置としてはＪＡＶＡ（登録商標）仮想マシンを挙げることができる。
【０００９】
本発明のガービッジコレクションワークロードは、互いに違うデータ処理装置のガービッジコレクションを公正で相対的に評価してガービッジコレクションのホットスポット（ｈｏｔ ｓｐｏｔ）を確認し、ＪＡＶＡ（登録商標）のための理想的なガービッジコレクション戦略を立てるようにする。
【００１０】
本発明のガービッジコレクションワークロードは、またマルチスレッド環境を提供してマルチプロセッサシステムにおけるガービッジコレクション性能の比例拡大（ｓｃａｌａｂｉｌｉｔｙ）を測定するようにする。
【００１１】
本発明の一実施例によるガービッジコレクションをベンチマーキングする方法では、ベンチマークファイルを生成し、前記ファイルをガービッジコレクションを支援するデータ処理装置上で実行することを含む。前記ベンチマークファイルを生成することは、二進ツリーのデータ構造を有する客体を生成し、前記客体がこれ以上参照されないようにして新しい客体を再生成し、ベンチマーク結果を報告することを含む。
【００１２】
一実施例において、前記二進ツリーのデータ構造を有する客体を生成することは、境界客体をルートノードとして、前記境界客体は同一、または境界客体より小さい第１サイズの客体は前記ルートノードから左側ノードに分岐し、大きい第２サイズの客体は前記ルートノードから右側ノードに分岐し、各ノードでそのノードの客体のサイズと同一、または客体のサイズより小さい客体は左側ノードに分岐し、大きい客体は右側ノードに分岐するようにする。
【００１３】
境界客体のサイズは任意に決めることができ、例えば、最も小さい客体及び最大の客体の中間値、またはその近所のサイズを有することができる。また、第１客体及び第２ 客体の個数を適切に調節して実際のプログラムの状況を反映することができる。例えば、実際客体志向プログラム(例えば、ＪＡＶＡ（登録商標）プログラム)で小さいサイズの客体が大きいサイズの客体より相対的にたくさん生成されれば、これを反映した二進ツリー構造の客体を形成することができる。
【００１４】
実際客体志向プログラムを分析して生成される客体の個数及びサイズを分析して中間サイズの客体、よく生成される客体のサイズ、最大サイズの客体、最小サイズの客体などを把握した後、ここに基づいて二進ツリー構造を形成することができる。例えば、客体の個数、サイズ、最小サイズの客体、最大サイズの客体の平均を利用して二進ツリー構造を生成することができる。
【００１５】
一実施例において、前記客体がこれ以上参照されないようにして、新しい客体を再生成することは、二進ツリーのデータ構造で先にいずれか一方の客体(例えば、第１サイズの客体)に接近した後、境界客体を接近し、他方の客体(第２サイズの客体)に接近する。したがって、第２サイズの客体が第１サイズの客体に比べて長く生きている。実際のＪＡＶＡ（登録商標）プログラムで大きいサイズの客体が小さいサイズの客体より長く生きているので、小さいサイズの客体を第１サイズの客体とし、大きいサイズの客体を第２サイズとすることが望ましい。
【００１６】
具体的に、前記第１サイズの客体ノードに接近して現在リンクを切断し(これ以上参照されないようにし)、新しい第１サイズの客体を生成し、前記境界客体ノードに接近して現在リンクを切断し、新しい境界客体を生成し、前記第２サイズの客体ノードに接近して現在リンクを切断し、新しい第２サイズの客体を生成する。この時、各々のサイズの客体ノードに対する接近は前記二進ツリーの最上位深さの客体ノードから始めて下位深さの客体ノードに向ける。また、以前の二進ツリーと同一の構造を有するように客体を生成する。すなわち、除去した客体と同一のサイズの客体を再生成する。
【００１７】
望ましくは、前記二進ツリーの最上位深さの客体ノードから始めて下位深さの客体ノードに客体再生成がなされる時、特定深さの客体ノードに対する客体再生成はその特定深さの直前になされた客体の再生成を繰り返した後になされる。
【００１８】
一実施例において、前記二進ツリーのデータ構造を有する客体を生成することは、客体の個数は同一な互いに違う構造の二進ツリー構造を形成することを含む。これはマルチスレッド環境を提供して実際のＪＡＶＡ（登録商標）プログラム環境を反映するためである。この時、各二進ツリー構造は互いに違う個数の前記第１サイズの客体及び第２サイズの客体を含ことが望ましい。
【００１９】
一実施例において、前記メモリに二進ツリーのデータ構造を有する客体を生成する前に、あらかじめ割り当てられた客体を生成することをさらに含むことができる。このようにあらかじめ割り当てられた客体はプログラム実行のうちに除去されず、プログラム実行が終わるまでメモリを占める。
【００２０】
本発明の一実施例によるガービッジコレクションをベンチマーキングするガービッジコレクションワークロードは、二進ツリーデータ構造を有する客体を生成する客体生成手段と、生成された二進ツリーデータ構造の客体がこれ以上参照されないようにして、新しい客体を再生成する客体再生成手段と、ベンチマーキング結果を出力する報告手段とを含む。
【００２１】
本発明はまた、ガービッジコレクションをベンチマーキングするためにデータ処理装置に、二進ツリー構造の客体ノードを生成する機能と、生成された客体ノードの全部に接近して現在のリンクを切ってしまい、新しい客体を再生成する機能と、テスト結果を報告する機能を実現させるためのプログラムを記録したコンピュータで読み出すことができる記録媒体とを提供する。
【発明の効果】
【００２２】
本発明によれば、互いに違うＪＡＶＡ（登録商標）仮想マシンのＪＡＶＡ（登録商標）ガービッジコレクション性能を公正で、相対的に評価してガービッジコレクションアルゴリズム上のホットスポット(ｈｏｔ ｓｐｏｔ)を確認してＪＡＶＡ（登録商標）のための理想的なガービッジコレクション戦略を立てることができる。
【発明を実施するための最良の形態】
【００２３】
以下、添付の図面を参照して本発明の実施例を詳細に説明する。
【００２４】
本発明は、ガービッジコレクションを測定するためのガービッジコレクションワークロード及びＪＡＶＡ（登録商標）ガービッジコレクションのベンチマーキング方法、そして前記ガービッジコレクションのベンチマーキング方法を実現させるためのプログラムを記録したコンピュータで読み出すことができる記録媒体を提供する。
【００２５】
本発明に対するより明確な理解のため、ＪＡＶＡ（登録商標）仮想マシンとこれに関連して本発明のガービッジコレクションワークロード及びガービッジコレクションのベンチマーキングを詳細に説明する。しかし、本発明は他のプログラム言語コンテクストでも実行することができることは当業者において自明である。また、本発明はここで説明される実施例に限定されず、他の形態で具体化すこともできる。むしろ、ここで紹介される実施例は開示された内容が徹底で、完全になれるように、そして、当業者に本発明の思想が十分に伝達されるようにするために提供されるものである。
【００２６】
本発明でツリーの最上位深さとは、ルートノードから最も遠くある子供ノードの深さを意味する。すなわち、ルートノードは深さ１であり、ルートノードの二子供ノードは深さ２である。
【００２７】
図１は本発明の一実施例によるＪＡＶＡ（登録商標）ガービッジコレクションのベンチマーキング方法を説明するための流れ図である。段階Ｓ１００で、実際のＪＡＶＡ（登録商標）プログラムを分析する。特に、客体に対する分析、例えば、客体（Ｏｂｊｅｃｔ）のサイズ、客体の寿命、最大客体のサイズ、最小サイズの客体、客体の個数、よく発生される客体のサイズなどを分析する。
【００２８】
段階Ｓ２００で、ＪＡＶＡ（登録商標）ガービッジコレクションをベンチマーキングするためのベンチマークファイルを生成する。ベンチマークファイルは段階Ｓ１００の客体に対する分析結果を反映して、客体の生成、生成された客体の除去及び再生成することを含む。通常、実際のＪＡＶＡ（登録商標）プログラムでサイズが小さい客体が相対的に大きい客体に比べて多く生成される。また、サイズが小さい客体は寿命が短くて(頻繁に生成されてから消滅して)、サイズが大きい客体は寿命が長い。したがって、このような状況を反映して客体を生成し、生成された客体を除去して再生成する。客体の生成、除去及び再生成に対しては後述する。
【００２９】
段階３００で、ＪＡＶＡ（登録商標）仮想マシンのガービッジコレクションを測定するため、ベンチマークファイルを多数個のＪＡＶＡ（登録商標）仮想マシン上で実行する。ベンチマークファイル（＊。ｊａｖａ（登録商標）ファイル）をＪＡＶＡ（登録商標）バイトコードに変換した後（＊。ｃｌａｓｓファイル）、これをＪＡＶＡ（登録商標）仮想マシン上で実行する。
【００３０】
図２は図１のベンチマークファイル生成段階Ｓ２００をより詳細に説明するための流れ図である。段階Ｓ２０１で、二進ツリーのデータ構造を有する客体を生成する。二進ツリー構造の客体の生成において、ルートノードは例えば、客体分析から得た客体の平均サイズで決めることができる。また、ルートノードは最小サイズの客体及び最大サイズの客体の平均値で決めることができる。ルートノードで分岐する子供ノードは最小サイズの客体と最大サイズの客体との間のサイズを有する。ルートノードの客体(境界客体)と同一、または客体（境界客体）より小さいサイズの客体は左に分岐し、大きいサイズの客体は右側に分岐する。また、各ノード(親ノード)で分岐するノード(子供ノード)も親ノードの客体と同一、または親ノードの客体より小さければ、親ノードから左に分岐し、親ノードの客体より大きければ、親ノードから右側に分岐する。また、ルートノードの左側にある小さいサイズの客体及び右側にある大きいサイズの客体の個数の比率は適切に調節することができる。
【００３１】
図３は本発明の一実施例によるツリー構造の客体生成を説明するための流れ図である。
【００３２】
段階Ｓ３０１で、境界客体のサイズ、最大客体のサイズ、最小客体のサイズ、客体の個数(ノードの個数)などを決める。このような決定は実際ＪＡＶＡ（登録商標）プログラムを分析することによって求めることができる。
【００３３】
段階Ｓ３０３で、境界客体を使ってルートノードを生成する。境界客体のサイズはあらかじめ固定された値として、ルートノードを形成する。
【００３４】
段階Ｓ３０５で、最小サイズの客体と最大サイズの客体との間の範囲を有する客体を無作為（ｒａｎｄｏｍ）で生成する。ここで、境界客体を中心に、それより小さいサイズの客体及び大きいサイズの客体の比率を調節することができる。大きいサイズの客体より小さいサイズの客体を相対的に多く生成する。
【００３５】
段階Ｓ３０７で生成された客体がルートノードの客体(境界客体)のサイズと同一であるか、または客体(境界客体)のサイズより小さいかを比較する。
【００３６】
その結果、生成された客体のサイズがルートノードの客体より小さければ、ルートノード(または親ノード)の左に分岐し(段階Ｓ３０９Ａ)、ルートノードの客体が生成された客体より大きければ、ルートノードの右側に分岐する(段階３０９Ｂ)。
【００３７】
段階Ｓ３１１で、分岐した方にノードが存在するか否かを判断する。もし分岐した方にノードが既に存在すれば、段階Ｓ３１３に進んで存在するノードの客体と新たに生成された客体とのサイズを比較する。その結果、新しい客体のサイズが既に存在するノードの客体と同一、またはより小さければ、段階Ｓ３０９Ａに移動し、新しい客体のサイズが既に存在するノードの客体より大きければ、段階Ｓ３０９Ｂに移動し、分岐した方に新しいノードが示されなくなるまで繰り返す。
【００３８】
もし段階Ｓ３１１で、分岐した方にノードが存在しなければ、段階Ｓ３１５に移動して分岐した方に新しいノードを生成する。
【００３９】
段階３１７で、生成された客体が存在するか否かを判断して、存在すれば、再び段階Ｓ３０７に移動し、存在しなければ、（すべての客体に対して処理が完了すれば）段階Ｓ３１９に進んで段階Ｓ３０５で生成された客体に対する二進ツリーが完成する。
【００４０】
再び図２を参照して、二進ツリー構造の客体を生成した後、段階２０３で生成された客体を除去し、新しい客体を再生成する。客体の除去及び再生成はルートノード(境界客体)を基準にして、その左側の子供ノード、すなわち、小さい客体のノードに対して先に客体の除去及び再生成する。続いて、ルートノードの客体を除去及び再生成した後、ルートノードの右側子供ノードに対して客体の除去及び再生成する。また、同一の深さのノードで、先ず、右側の兄弟ノードに対して客体の除去及び再生成し、左側の兄弟ノードに対して客体の除去及び再生成する。また、客体の除去及び再生成は二進ツリー構造の最上位の深さから始めて下位の深さに移動する。
【００４１】
例えば、二進ツリーが深さ４のノードからなる場合を考えてみれば、先ず、ルートノードの左側のノードで(すなわち、ルートノードの客体と同一、またはより小さいサイズの客体に対して)深さ４の兄弟ノード（ｓｉｂｌｉｎｇ ｎｏｄｅ）、深さ３の兄弟ノード、深さ２の兄弟ノードの手順で客体に対する除去及び再生成を進行した後、深さ１のノード(ルートノード)の境界客体に対して客体の除去及び再生成する。続いて、ルートノードの右側ノードで(すなわち、ルートノードの客体より大きいサイズの客体に対して)、深さ４の兄弟ノード、深さ３の兄弟ノード、深さ２の兄弟ノードの手順で客体に対する除去及び再生成を進行する。
【００４２】
すなわち、客体に対する除去及び再生成は４Ｌ、３Ｌ、２Ｌ、１、４Ｒ、３Ｒ、２Ｒの手順からなる(ここで、数字はノードの深さを表示し(１はルートノード表示)、数字の下添字Ｒはルートノードを基準にして、右側ノードを(ルートノードの客体より大きいサイズの客体)を、下添字Ｌは左側ノード(ルートノードの客体より小さいサイズの客体)を示す。また各深さのノードは二つの兄弟ノードからなることができ、この時、右側の兄弟ノードの客体に対して、先ず除去及び再生成を進行した後、左側の兄弟ノードの客体に対して除去及び再生成を進行する。また左側の兄弟ノードの客体に対して先に進行した後、右側の兄弟ノードの客体に対して進行することができる)。
【００４３】
この時、同一の二進ツリー構造を維持するため、除去された客体のサイズと同一のサイズの客体を再生成する。
【００４４】
望ましくは、特定深さのノードでの客体に対する除去及び再生成は、その特定深さのすぐ直前になされた客体に対する除去及び再生成を繰り返した後になされる。すなわち、各深さでの客体の除去及び再生成は、その深さを含んで、その深さの下にあるすべての深さのノード(子供ノード)に対して客体の除去及び再生成がなされる。また、ルートノードの右側のノードに対する客体の除去及び再生成はルートノードの左側の客体に対する除去及び再生成を進行した後になされる。
【００４５】
例えば、上の深さ４(ルートノード：深さ１)からなる二進ツリー構造の例の場合、４Ｌ、（４Ｌ、３Ｌ）、（４Ｌ、３Ｌ、２Ｌ）、（４Ｌ、３Ｌ、２Ｌ、１）、(４L、３Ｌ、２Ｌ、１、４Ｒ)、（４Ｌ、３Ｌ、２Ｌ、１、４Ｒ、３Ｒ）、（４Ｌ、３Ｌ、２Ｌ、１、４Ｒ、３Ｒ、２Ｒ）の手順で客体の除去及び再生成がなされる。したがって、小さいサイズの客体は頻繁に除去及び再生成がなされ、大きいサイズの客体は非常にまれに除去及び再生成がなされる。これは実際のＪＡＶＡ（登録商標）プログラム環境を非常に適切に代弁する。二進ツリーを構成するすべてのノードが少なくとも一度は訪問され、客体を除去して再生成する。既存のツリー構造と同一の構造を維持するために既存の子供ノードと同一のサイズの子供ノードを生成する。
【００４６】
図４Ａ及び図４Ｂは本発明の一実施例によるツリー構造の客体除去及び再生成を説明するための流れ図である。
【００４７】
図４Ａは客体除去及び再生成手順を示す流れ図であり、図４Ｂは客体除去及び再生成アルゴリズムを示す流れ図である。
【００４８】
先ず、図４Ａを参照して、段階Ｓ４０１から始めて、段階Ｓ４０３でルートノードの左側の子供ノード(小さい客体)に対する客体の除去及び再生成がなされ、段階Ｓ４０５でルートノードに対する客体の除去及び再生成がなされ、段階Ｓ４０７でルートノードの右側の子供ノード(大きい客体)に対する客体の除去及び再生成がなされる。
【００４９】
図４Ｂは再生成関数を説明するための流れ図で、これによれば、現在ツリー深さから最後のノード(最上位深さのノード)まで客体除去及び再生成が繰り返し進行される。
【００５０】
段階Ｓ４１１から始めて再生成関数が始まる。段階Ｓ４１３で、右側のノードがｎｕｌｌであるか (右側の子供ノードが存在するか)否かを判断する。判断の結果、ｎｕｌｌであれば(右側の子供ノードがなければ)段階Ｓ４２１に進行して、今度は左側のノードがｎｕｌｌであるか (左側の子供ノードが存在するか)否かを判断する。判断の結果、左側ノードがｎｕｌｌであれば(左側の子供ノードがなければ)再生成関数の実行が終わって、段階Ｓ４２９で終了する。
【００５１】
段階Ｓ４１３で右側の子供ノードがあれば、段階Ｓ４１５に進行して、その右側の子供ノードを現在の右側ノードにして、段階Ｓ４１６で再生成関数を呼び出す(再帰呼び出し)。再帰呼び出された関数の実行が完了すれば(すなわち、段階Ｓ４１１から始めて段階Ｓ４２９まで実行されて、再帰呼び出しされた関数の実行が終われば)段階Ｓ４１７に進行する。段階Ｓ４１７で右側の子供ノードがｎｕｌｌであるか否かを判断する。その結果、ｎｕｌｌであれば、新しい客体を生成し、ｎｕｌｌではなければ、段階Ｓ４２１に進行する。
【００５２】
段階Ｓ４２１で左側の子供ノードがあれば、段階Ｓ４２３に進行して、その左側の子供ノードを現在の左側ノードにして、段階Ｓ４２４で再生成関数を呼び出し(再帰呼び出し)、再帰呼び出された関数の実行が完了すれば(すなわち、段階Ｓ４１１から始めて段階Ｓ４２９まで実行されて再帰呼び出された関数の実行が終われば)段階Ｓ４２５に進行する。段階 Ｓ４２５で左側の子供ノードがｎｕｌｌであるか否かを判断する。その結果、ｎｕｌｌであれば、新しい客体を生成し、ｎｕｌｌではなければ、段階Ｓ４１９に進行して再帰呼び出された関数の実行が終わる。
【００５３】
これによって、現在の親ノードの上位深さにあるすべての子供ノードに対する客体の除去及び再生成がなされる。この時、客体の除去及び再生成は最上位深さの子供ノードから上位深さのノードに移動しながら、そして右側の子供ノードが左側の子供ノードより先に除去されて再生成される。
【００５４】
図４Ｂの流れ図で、子供ノードのうちの左側の兄弟ノードが先に除去及び再生成され、続いて、右側の兄弟ノードが除去及び再生成されうる。
【００５５】
以上の説明の二進ツリーデータ構造及びそれに対する客体の除去及び再生成に対する説明からプログラマは所定のプログラム言語を使って実現しうる。
【００５６】
このような二進ツリー構造の形成、客体の除去及び再生成を含むベンチマークプログラムの一例を説明する。
【００５７】
ベンチマークプログラムは実在的なノードの生成、ノードの除去及び再生成を担当する ＯｂｊＢＴｒｅｅクラスと、ＯｂｊＢＴｒｅｅクラスのメソッド（ｍｅｔｈｏｄ）を利用して所望する二進ツリー構造を生成し、生成された二進ツリー構造に対する客体の除去及び再生成を担当するＭＴＢｉｎＴｒｅｅクラス、ベンチマーク結果を出力するＪＧＣＷクラス、新しい客体生成のためにランダムに数を発生させるＲａｎＧｅｎクラスを含む。
【００５８】
ＯｂｊＢＴｒｅｅクラスはａｄｄメソッド、ｔｒａｖｅｒｓｅ メソッド、ｇｅｔＤｅｐｔｈメソッド、ｇｅｔｄｅｐｔｈメソッド、ｒｅｇｅｎＮｏｄｅメソッドなどを含む。Ｏｂｊ  ＢＴｒｅｅ  ａｄｄ(ＯｂｊＢＴｒｅｅ ｒ、Ｉｎｔｅｇｅｒ ｎ、ｉｎｔ ｏｂｊｓｉｚｅ)メソッドは新しいノードの生成要求が入ってきた時、既存のツリー構造に新しいサイズのノードを生成し、親ノードより大きいノードは右側の兄弟ノードに、同一、または小さいノードは左側の兄弟ノードになる。ＯｂｊＢＴｒｅｅ  ｔｒａｖｅｒｓｅ(ＯｂｊＢＴｒｅｅ  ｒ) メソッドは、生成されたすべてのノードを一回以上訪問（ｖｉｓｉｔｉｎｇ）する。ＯｂｊＢＴｒｅｅ  ｇｅｔＤｅｐｔｈ(ＯｂｊＢＴｒｅｅ ｒ)メソッドは現在のツリー構造の深さを知らせ、ツリーの深さを返還するＯｂｊＢＴｒｅｅ  ｇｅｔｄｅｐｔｈ（ＯｂｊＢＴｒｅｅ ｒ）メソッドから呼び出される。ＯｂｊＢＴｒｅｅ  Ｒｅｇｅｎｎｏｄｅ（ＢｂｊＢＴｒｅｅ ｒ、 ｉｎｔ ｄｅｐｔｈ）は各ノードを訪問して既存の客体リンクを除いてしまい(既存客体をガービッジ化し)、同一のサイズの客体ノードを生成して同一のツリー構造を維持するようにする。
【００５９】
例えば、客体生成メソッドａｄｄ（）のソースコードは次の通りである。
-----------------------------------------------------------------------
1．   public static ObjBTree add(ObjBTree r,Integer n, int objsize){
2．      if(r == null){
3．         r = new ObjBTree();
4．         r．left = r．right=null;
5．         r．idata = n;
6．         r．sdata = new StringBuffer();
7．         r．sdata．setLength(objsize);
8．      }else if(r．idata。compareTo(n) < 0)
9．       r．right=add(r．right、n、objsize);
10．     else
11.        r．left=add(r．left、n、 objsize);
12.        return r;
13.        }
-----------------------------------------------------------------------
【００６０】
上のソースコードで左側の数字は説明の便宜のためのライン（ｌｉｎｅ）を表示することとして、実際のソースコードには含まれない。
【００６１】
このようなソースコードは一例に過ぎず、同一のＪＡＶＡ（登録商標）言語を使っても異なって実現しうる。
【００６２】
上のａｄｄメソッドソースコードで、ライン２〜７で、客体ノードがｎｕｌｌであれば、左側及び右側の子供ノードがｎｕｌｌであるｏｂｊｓｉｚｅのサイズを有する新しい客体ノードを形成する。ライン８で、客体ノードがｎｕｌｌではなければ、そのノードの客体のサイズと新たに生成される客体のサイズ(ｏｂｊｓｉｚｅのサイズ)とを比較する。新たに生成される客体のサイズが現在ノードの客体よりさらに大きければ、そのノードから右側に分岐して子供ノード客体が形成され(ライン９)、そうではなければ(新たに生成される客体のサイズが現在ノードの客体と同一、またはより小さければ)、そのノードから左側に分岐して子供ノード客体が形成される(ライン１１)。
【００６３】
ツリーの全体に対する深さを知らせるｇｅｔＤｅｐｔｈメソッドのソースコードは次の通りである。
-----------------------------------------------------------------------
1． public void getDepth(ObjBTree r){
2．   if(r != null){
3．        curr_depth++;
4．        if(curr_depth > tree_depth)
5．              tree_depth = curr_depth;
6．        getDepth(r．left);
7．        getDepth(r．right);
8．        curr_depth--;
9． ｝
10．｝
-----------------------------------------------------------------------
【００６４】
６〜７ラインで、ｇｅｔＤｅｐｔｈ（ｒ。ｌｅｆｔ）及びｇｅｔＤｅｐｔｈ（ｒ。ｒｉｇｈｔ）メソッドを再帰呼び出すことによって、ツリーの全体に対する深さを知らせる。
【００６５】
図４Ｂで説明した客体除去及び再生成メソッドであるＲｅｇｅｎｎｏｄｅ[ＯｂｊＢＴｒｅｅ ｒ、 ｉｎｔ ｄｅｐｔｈ)は特定深さの下にあるすべての上位深さのノードを訪問して、現在のリンクを切ってしまって新しい客体を作る。このようなメソッドＲｅｇｅｎｎｏｄｅに対するソースコードは次の通りである。
-----------------------------------------------------------------------
1． public ObjBTree regenNode(ObjBTree r、 int depth) {
2．    ObjBTree tmpleft = null、 tmpright=null;
3．   int tmpidata = 0;
4．  curr_depth++;
5．  if (r．right != null) {
6．   tmpidata = r．right．idata．intValue();
7．   tmpleft  = r．right．left;
8．   tmpright = r．right．right;
9．   r．right=regenNode(r．right、 depth);
10． if (r．right==null) {
11．    r．right = new ObjBTree();
12．    Integer tmpIdata = new Integer(tmpidata);
13．    r．right．idata = tmpIdata;
14．    r．right．sdata = new StringBuffer();
15．    r．left．sdata．setLength(tmpidata);
16．        r．right．right= tmpright;
17．        r．right．left= tmpleft;
18． ｝
19．｝
20．  if (r．left != null) {
21．  tmpidata = r．left．idata．intValue();
22．  tmpleft  = r．left．left;
23．  tmpright = r．left．right;
24．   r．left=regenNode(r．left、 depth);
25．  if (r．left==null) {
26．     r．left = new ObjBTree();
27       Integer tmpIdata = new Integer(tmpidata);
28．     r．left．idata = tmpIdata;
29．     r．left．sdata = new StringBuffer();
30．     r．left．sdata．setLength(tmpidata);
31．        r．left．right = tmpright;
32．         r．left．left = tmpleft;
33． ｝
34．｝
-----------------------------------------------------------------------
【００６６】
メソッドＲｅｇｅｎｎｏｄｅ（ＯｂｊＢＴｒｅｅ ｒ、ｉｎｔ ｄｅｐｔｈ）は右側ノード及び左側ノードがｎｕｌｌであるか否かを各々判断する条件文(５ライン、２０ライン)を有している。また、各条件文はその内部でｒｅｇｅｎＮｏｄｅメソッドを呼び出す文(９ライン及び２４ラインのメソッドｒ。ｒｉｇｈｔ＝ｒｅｇｅｎＮｏｄｅ(ｒ。ｒｉｇｈｔ、ｄｅｐｔｈ)及びｒ。ｌｅｆｔ＝ｒｅｇｅｎＮｏｄｅ(r。ｌｅｆｔ、ｄｅｐｔｈ)) 及び右側ノードまたは左側ノードがｎｕｌｌであるか否かを判断するネスト条件文(１０ライン及び２５ライン)を含んでいる。左側ノードまたは右側ノードがｎｕｌｌであれば、新しい客体ノードが生成される。したがって、特定深さのノードに対する客体の除去及び再生成はその下にある上位深さのすべてのノードに対する客体を除去して再生成するようになる。
【００６７】
ＭＴＢｉｎＴｒｅｅクラスはａｄｄ メソッド、ｒｅｇｅｎメソッド、ｇｅｔｄｅｐｔｈメソッド、ｒｕｎメソッドを含む。ＭＴＢｉｎＴｒｅｅ。ａｄｄ()メソッドは所望する個数のノードに到逹するまでノードを生成する。ＭＴＢｉｎｔｒｅｅ。ｇｅｔｄｅｐｔｈ()メソッドは形成されたツリー構造で最も深い深さを計算する。ＭＴＢｉｎＴｒｅｅ。ｒｅｇｅｎ（）メソッドは生成されたツリー構造の各ノードを訪問して客体を除去して再生成する。ＭＴＢｉｎＴｒｅｅクラスはまたスレッド（Ｔｈｒｅａｄ）クラスを相続して同時に多数個のツリー構造を生成することができる。ＭＴＢｉｎＴｒｅｅ。ｒｕｎ（）メソッドは客体の個数、最大サイズの客体、最小サイズの客体、境界客体(ルートノード)、境界客体を基準にして、それより小さいサイズの客体及びそれより大きいサイズの客体の比率などを決める制御文を含み、制御文内でＭＴＢｉｎＴｒｅｅ。ａｄｄ（）、ＭＴＢｉｎＴｒｅｅ。ｇｅｔｄｅｐｔｈ()、ＭＴＢｉｎＴｒｅｅ。ｒｅｇｅｎ()メソッドを呼び出す。
【００６８】
一方、クラスＯｂｊＢＴｒｅｅのソースコードは次の通りである。
-----------------------------------------------------------------------
1．class MTBinTree extends Thread｛
2．protected ObjBTree bnode = null;
3．protected ObjBTree rnode = null;
4．protected ObjBTree rnode_l = null;
5．protected ObjBTree rnode_r = null;
6．protected Integer obji = null;
7．protected int currdepth =0;
8．protected static int bmaxsize=0;
9．protected static int bnodes=0;
10．protected static int bweight=0;
11．protected static int bsizebound=0;
12．MTBinTree()｛｝
13．public void add()｛
14． bnode = bnode．add(bnode、obji、obji．intValue());
15．｝
16．public void regen(ObjBTree node)｛
17    bnode=bnode．regenNode(node、currdepth);
18．｝
19．public int getdepth(ObjBTree node)｛
20． return bnode．getdepth(node);
21．｝
22．public void run() {
23． int stringsize=0;
24． int removedobjs=0;
25． int objsize[];
26． int largeobj=1;
27． int smallobj=1;
28． int treedepth_l=0、 treedepth_r=0;
29． RanGen r;
30． JGCW jgcw_bin = new JGCW();
31． bmaxsize=jgcw_bin．bmaxsize;
32． bnodes=jgcw_bin．bnodes;
33． bweight=jgcw_bin．bweight;
34． bsizebound=jgcw_bin．bsizebound;
35． objsize = new int[bnodes];
36． r = new RanGen(bmaxsize);
37． for(int i=0; i<bnodes; i++)｛
38．  if ((largeobj*bweight) > (smallobj*(10-bweight)))｛
39．    stringsize=r。RInt();
40．    while (stringsize > bsizebound)｛
41．    stringsize=r．RInt();
42．    ｝
43．    objsize[i]=stringsize;
44．    smallobj++;
45．  ｝
46．  else｛
47．    stringsize=r．RInt();
48．   while (stringsize <= bsizebound)｛
49．    stringsize=r。RInt();
50．    ｝
51．    objsize[i]=stringsize;
52．    largeobj++;
53．  ｝
54． ｝
55． Integer objbound = new Integer(bsizebound);
56． obji=objbound;
57． add();
58． rnode = bnode;
59． for (int i=1; i<bnodes; i++)｛
60．    Integer objint= new Integer(objsize[i]);
61．    obji=objint;
62．    add();
63． ｝
64． jgcw_bin．MemWaterMark();
65． rnode_l = rnode．left;
66． rnode_r = rnode．right;
67． treedepth_l = getdepth(rnode_l);
68． treedepth_r = getdepth(rnode_r);
69．  for(int i=treedepth_l; i > 1; i--)｛
70．   currdepth = i;
71．   regen(rnode_l);
72．   jgcw_bin．MemWaterMark();
73． ｝
74．  for(int i=treedepth_r; i > 1; i--)｛
75．   currdepth = 2;
76．   regen(rnode_l);
77．   currdepth=i;
78．   regen(rnode_r);
79．   jgcw_bin．MemWaterMark();
80．    ｝
81． ｝
82．｝
【００６９】
上記ソースコードで左側の数字は説明の便宜のためのライン（ｌｉｎｅ）を表示することとし、実際のソースコードには含まれない。
【００７０】
このようなソースコードは一例に過ぎず、同一のＪＡＶＡ（登録商標）言語を使っても異なって実現しうる。
【００７１】
１３〜１５ラインでＯｂｊＢＴｒｅｅクラスのａｄｄ（ＯｂｊＢＴｒｅｅ ｒ、 Ｉｎｔｅｇｅｒ ｎ、 ｉｎｔ ｏｂｊｓｉｚｅ）に接近するａｄｄメソッドが宣言され、１６〜１８ラインでＯｂｊＢＴｒｅｅクラスのｒｅｇｅｎＮｏｄｅ（ＯｂｊＢＴｒｅｅ ｒ、 ｉｎｔ ｄｅｐｔｈ）に接近するｒｅｇｅｎメソッドが宣言され、１９〜２１ラインでＯｂｊＢＴｒｅｅクラスのｇｅｔｄｅｐｔｈ（ＯｂｊＢＴｒｅｅ ｒ）に接近するｇｅｔｄｅｐｔｈメソッドが宣言される。
【００７２】
２２ラインからｒｕｎメソッドが始まる。３６〜５４ラインで新しい客体ノード形成のためのランダム数を発生させる。ランダム数は最小サイズの客体及び最大サイズの客体の間の値を有する。ここで、境界客体を基準にして、それより小さい客体及びそれより大きい客体を一定の比率で生成する。
【００７３】
３４ラインで境界客体のサイズが与えられ、これを利用して５５〜５８ラインでルートノードを生成する。
【００７４】
５９〜６３ラインで、ランダム数を利用してラインで残りのノードを形成する。
【００７５】
６５〜６８ラインで、ルートノードの左側の子供ノード及びこれらの深さ、そしてルートノードの右側の子供ノード及びこれらの深さが定義される。６９〜７３でルートノード左側の子供ノード及びルートノードの客体に対して除去及び再生成を進行する。ｆｏｒルーフ構文を利用して上位深さから下位深さに行きながら、繰り返して客体の除去及び再生成を進行する。
【００７６】
７４〜７８ラインで、ルートノードの右側の子供ノードに対する客体の除去及び再生成がなされる。この時、ライン７６で、左側ノードに対する客体を除去及び再生成するメソッドｒｅｇｅｎ(ｒｎｏｄｅ_ｌ)が呼び出された後、ルートノードの右側ノードに対する客体を除去及び再生成するメソッドｒｅｇｅｎ(ｒｎｏｄｅ_ｒ)が呼び出される。したがって、ルートノードの右側の子供ノードに対する客体の除去及び再生成はルートノードの左側の子供ノードに対する客体の除去及び再生成を進行した後になされる。
【００７７】
再び、図２を参照して、二進ツリー構造を構成する客体に対して少なくとも一度以上の除去及び再生成を進行した後、段階Ｓ２０５でベンチマーク結果を報告する。ベンチマークの結果は例えば、客体割り当て及び自由客体の再要求の実行時間、メモリ状態(ヒップサイズ、割り当てられた空間、自由空間など)などを含むことができる。
【００７８】
実行時間はプログラム実行の前と実行の後とに各々の時間スタンプ(ｓｔａｍｐ)を取ってその差で求めることができ、メモリ状態はＪＡＶＡ（登録商標）ライブラリファンクションを利用することができる。
【００７９】
図５Ａおよび図５Ｂは本発明による二進ツリー構造の客体ノードを形成する方法を説明するための模式図である。境界客体サイズを１２８(ｂｙｔｅ)、最大サイズの客体を５１２(ｂｙｔｅ)、最小サイズの客体を１(ｂｙｔｅ)と仮定し、客体個数は境界客体を含んで９個であると仮定する。境界客体を除いた客体は任意的に(ｒａｎｄｏｍ) 生成され、図５Ａ及び図５Ｂでは、その生成手順に差があり、同一のサイズの客体と仮定した。これは同一のサイズの客体であっても生成手順の差によって、他のツリー構造を形成することを示すためである。図５Ａでは、２５６、６４、７２、３２、５１２、２３４、１０２、６７の手順によって生成され、図５Ｂでは、７２、１０２、５１２、６７、６４、２５６、２３４、３２の手順によって生成される。
【００８０】
先ず、図５Ａを参照して、境界客体でルートノードが形成される。一番目で生成された客体は２５６バイトとしてルートノードの客体より大きく、ルートノードから右側に分岐して、深さ２の右側の子供ノードを形成する。二番目で形成された客体は６４バイトとしてルートノードの客体より小さく、左に分岐して深さ２の左側の子供ノードを形成する。三番目で形成された客体は７２バイトとしてルートノードの客体より小さく、深さ２の左側の子供ノードに分岐し、その所の客体(６４バイト)より大きく、右側に分岐して深さ３の右側の子供ノードを形成する。四番目で生成された客体は３２バイトとしてルートノードの客体より小さくて左に分岐して、深さ２の左側の子供ノードに分岐し、その所の客体(６４バイト)より小さくて左に分岐して、深さ３の左側の子供ノードを形成する。五番目で生成された客体は５１２バイトとしてルートノードの客体より大きくて、右側に分岐して深さ２の右側の子供ノードを形成する。このような方法で二進ツリー構造が形成される。
【００８１】
次の図５Ｂを参照して、一番目で生成された客体は７２バイトとしてルートノードの客体より小さく、左に分岐して深さ２の左側の子供ノードを形成する。二番目で生成された客体は１０２バイトとしてルートノードの客体より小さくて左に分岐し、分岐した所の子供ノードより大きくて、深さ２の左側の子供ノードから右側に分岐して深さ３の右側の子供ノードを構成する。このような方法で、二進ツリー構造が形成され、図５Ａとは完全に違う構造を有することが分かる。
【００８２】
図６Ａおよび図６Ｂは各々図５Ａ及び図５Ｂの二進ツリー構造での客体の除去及び再生成手順を示す。上述のように、本発明による客体の除去及び再生成はルートノードの左側にある左側の子供ノード、ルートノード及びルートノードの右側の子供ノードの手順からなる。また、最下位の深さのノードから始めて上位の深さに移動しながらなされ、各深さでの客体の除去及び再生成はすぐ直前になされた客体の除去及び再生成を繰り返した後に進行される。
【００８３】
まず、図６Ａを参照して、一番目の実行で、左側ノードのうちの最下位の深さである深さ４の客体１０２、６７に対する除去及び再生成がなされ、右側の兄弟ノードが左側の兄弟ノードに比べて先に除去及び再生成される。またはその反対の手順で進行されうる。
【００８４】
二番目の実行で、左側ノードのうちの深さ３のノードに対する客体の除去及び再生がなされる。左側ノードの深さ３のノードに対する客体の除去及び再生成は先に、深さ４に対する客体の除去及び再生成を繰り返した後になされる。すなわち、左側ノードの深さ４のノード１０２、６７に対する客体の除去及び再生成を進行した後(一番目の実行を繰り返した後)深さ３のノード７２、３２に対する客体の除去及び再生成を進行する。
【００８５】
三番目の実行で、左側ノードのうちの深さ２のノード６７に対する客体の除去及び再生成がなされる。すなわち、左側ノードの深さ４のノード１０２、６７の深さ３のノード ７２、３２に対する客体の除去及び再生成を進行した後(二番目の実行を繰り返した後) 深さ２のノード６７に対する客体の除去及び再生成を進行する。
【００８６】
四番目の実行で左側ノードの深さ４、深さ３、深さ２のノードに対する客体の除去及び再生成を進行した後(三番目の実行を繰り返した後)、深さ１のノードに対する客体の除去及び再生成を進行する。これによって、ルートノードの左側の子供ノードに対する客体の除去及び再生成が終わる。
【００８７】
次は、ルートノードの右側の子供ノードに対する客体の除去及び再生成がなされる。五番目の実行で、ルートノードの左側ノードの深さ４、深さ３、深さ２のノード及びルートノードに対する客体の除去及び再生成を進行した後(四番目の実行を繰り返した後)、ルートノードの右側ノードの深さ３のノード５１２、２３４に対する客体の除去及び再生成を進行する。
【００８８】
六番目の実行で、五番目の実行を進行した後、ノード２５６に対する客体の除去及び再生成を進行する。
【００８９】
図６Ｂを参照して、一番目の実行でノード３２に対して、二番目の実行でノード３２、６４に対して、．．．、八番目の実行でノード３２、６４、１０２、６７、７２、１２８、 ２３４、２５６、５１２に対して客体除去及び再生成が実行されることが分かる。
【００９０】
図６Ａおよび図６Ｂから分かるように、大きいサイズの客体はプログラム進行中に長い間生きている一方、小さいサイズの客体は頻繁に除去及び再生成されることが分かる。これは実際のＪＡＶＡ（登録商標）プログラムの特性と一致する。
【００９１】
ＪＡＶＡ（登録商標）環境はマルチスレッドを支援する。したがって、上述の二進ツリー構造を多数個形成してマルチスレッド環境を反映する。また、プログラム進行中に除去されない生存客体をあらかじめ形成することができる。各スレッドは同一の客体個数を有し、かつ互いに違うツリー構造を有する。また、各スレッドの境界客体は互いに同一、または違うこともできる。
【００９２】
図７は本発明の他の実施例によるベンチマークファイルを生成する方法を説明するための流れ図である。
【００９３】
段階Ｓ７０１から始めて、段階Ｓ７０３で、事前に生存客体を生成するか否かを判断する。生存客体はプログラム実行の間除去されず、続いてメモリを占有する客体である。生存客体を生成すれば、段階Ｓ７０５で生存客体を生成する。生存客体は多様なデータ構造を有することができる。上述のツリー構造を有するだけではなく、リンクリスト構造、アレイ構造などを有することができる。ＪＡＶＡ（登録商標）ガービッジコレクションはプログラム実行中に、このような生存客体を絶えず訪問しなければならなくて、生存客体はＪＡＶＡ（登録商標）ガービッジコレクションに追加的な負担(ｓｔｒｅｓｓ、 ｂｕｒｄｅｎ)を提供する。
【００９４】
段階Ｓ７０７で、スレッドの個数、境界客体、最大サイズの客体、境界客体を基準にして、それより大きい客体及びそれより小さい客体の生成の比率などを決める。境界客体はあらかじめ決められた値である。境界客体の以外の客体はランダムに生成し、あらかじめ決めた条件を満足させなければ(最大サイズの客体より大きいランダム数が発生するか、最小サイズの客体より小さいランダム数が発生すれば)、再びランダムに生成する。
【００９５】
段階Ｓ７０９で多数個のスレッドを形成する。各スレッドは客体で構成された固有の二進ツリーデータ構造を有する。各スレッドは客体個数は同一であるが、互いに違うツリー構造を有する。
【００９６】
段階Ｓ７１１で、各スレッドで同時に上述したような方法で客体除去及び再生成がなされる。
【００９７】
段階Ｓ７１３で各スレッドに対するガービッジコレクションに対する評価が報告される。
【００９８】
以上では、本発明に対してその望ましい実施例を中心に示した。本発明が属する技術分野で通常の知識を持つ者は本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態で実現されることができることを理解することができる。したがって、本開示された実施例は限定的な観点ではなく、説明的な観点で考慮されなければならない。本発明の範囲は上述の説明ではなく、特許請求の範囲に示しており、それと同等な範囲内にあるすべての差は本発明に含まれると解釈されなければならないであろう。
【図面の簡単な説明】
【００９９】
【図１】本発明の一実施例によるＪＡＶＡ（登録商標）ガービッジコレクションベンチマーキング方法を説明するための流れ図である。
【図２】図１のベンチマークファイル生成段階Ｓ２００をより詳細に説明するための流れ図である。
【図３】本発明の一実施例によるツリー構造の客体生成を説明するための流れ図である。
【図４Ａ】客体除去及び再生成の手順を示す流れ図である。
【図４Ｂ】客体除去及び再生成アルゴリズムを示した流れ図である。
【図５Ａ】本発明による二進ツリー構造の客体ノードを形成する方法を説明するための模式図である。
【図５Ｂ】本発明による二進ツリー構造の客体ノードを形成する方法を説明するための模式図である。
【図６Ａ】図５Ａの二進ツリー構造で客体の除去及び再生成の手順を示す。
【図６Ｂ】図５Ｂの二進ツリー構造で客体の除去および再生成の手順を示す。
【図７】本発明の他の実施例によるベンチマークファイルを生成する方法を説明するための流れ図である。
【図１】
2005071375.tif 000003
【図２】
2005071375.tif 000004
【図３】
2005071375.tif 000005
【図４Ａ】
2005071375.tif 000006
【図４Ｂ】
2005071375.tif 000007
【図５Ａ】
2005071375.tif 000008
【図５Ｂ】
2005071375.tif 000009
【図６Ａ】
2005071375.tif 000010
【図６Ｂ】
2005071375.tif 000011
【図７】
2005071375.tif 000012