(57)【要約】      （修正有）【課題】バーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定することを容易にするシステムを提供すること。【解決手段】システムは、コンパイルされたメソッドが実行されるとき、決定することによって始まる。その場合、システムは、コンパイルされたメソッドに対応するフラグをセットすることにより、コンパイルされたメソッドが実行していることを示す。システムは、フラグを定期的にスキャンし、フラグがセットされているとき、対応するカウンターの値を増加させて、それから、フラグをリセットする。最終的に、システムは、カウンターの値を解析することにより、コンパイルされたメソッド実行の頻度を決定する。【選択図】図３
2005251208.tif 000002
【特許請求の範囲】
【請求項１】
バーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定する方法であって、
コンパイルされたメソッドが実行されるとき、該コンパイルされたメソッドに対応するコンパイルされたフラグをセットすることにより、該コンパイルされたメソッドが実行していることを示すことと、
該フラグを定期的にスキャンし、該フラグがセットされているとき、対応するカウンターの値を増加させて、それから、該フラグをリセットすることと、
該カウンターの該値を解析することによって、該コンパイルされたメソッドの実行の頻度を決定することと
を包含する、方法。
【請求項２】
前記カウンターの増加の間の時間間隔を調整することをさらに包含する、請求項１に記載の方法。
【請求項３】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドが、第２のコンパイルされたメソッドを呼び出すとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項４】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドが、第２のコンパイルされたメソッドによって呼び出されるとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項５】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドから第２のコンパイルされたメソッドへ戻るとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項６】
前記コンパイルされたメソッドが実行されるとき、決定することは、第２のコンパイルされたメソッドから該コンパイルされたメソッドへ戻るとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項７】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッド内でバックワードブランチを開始するとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項８】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッド内でバックワードブランチに対してターゲットで、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１に記載の方法。
【請求項９】
前記コンパイルされたメソッドの実行の頻度が、所定のしきい値を下回るとき、該コンパイルされたメソッドをイヴィクトし、その結果、前記方法は、該コンパイルされたメソッドが再び実行されるとき、続いてリコンパイルもしくはインタープリットされなければならないことをさらに包含する、請求項１に記載の方法。
【請求項１０】
所定のしきい値を調整することにより、前記コンパイルされたメソッドの数を制御することをさらに包含する、請求項９に記載の方法。
【請求項１１】
前記カウンターを定期的に減少させることにより、デケイを導入して、それによって、前記コンパイルされたメソッドの過去の実行の関連性を自然にフェードすることをさらに包含する、請求項１に記載の方法。
【請求項１２】
いずれかのメソッドに関連付けられたいずれかのカウンターが、所定のしきい値に達するとき、前記カウンターを定期的に減少させることをさらに包含する、請求項１１に記載の方法。
【請求項１３】
前記フラグに割り当てられた重量値を定期的に増加させ、その結果、前記コンパイルされたメソッドの後の実行は、該コンパイルされたメソッドの前の実行より多くカウントすることをさらに包含する、請求項１に記載の方法。
【請求項１４】
コンピュータによって実行されるとき、該コンピュータに方法を実行させる命令を格納するコンピュータ読み取り可能格納媒体であって、該命令がコンピュータによって実行されるとき、該命令が該コンピュータにバーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定させ、
該方法は、
コンパイルされたメソッドが実行されるとき、該コンパイルされたメソッドに対応するフラグをセットすることにより、該コンパイルされたメソッドが実行していることを示すことと、
該フラグを定期的にスキャンし、該フラグがセットされているとき、対応するカウンターの値を増加させて、それから、該フラグをリセットすることと、
該カウンターの該値を解析することによって、該コンパイルされたメソッドの実行の頻度を決定することと
を包含する、コンピュータ読み取り可能格納媒体。
【請求項１５】
前記方法は、前記カウンターの増加の間の時間間隔を調整することをさらに包含する、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項１６】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドが、第２のコンパイルされたメソッドを呼び出すとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項１７】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドが、第２のコンパイルされたメソッドによって呼び出されるとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項１８】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッドから第２のコンパイルされたメソッドへ戻るとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項１９】
前記コンパイルされたメソッドが実行されるとき、決定することは、第２のコンパイルされたメソッドから該コンパイルされたメソッドへ戻るとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２０】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッド内でバックワードブランチを開始するとき、命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２１】
前記コンパイルされたメソッドが実行されるとき、決定することは、該コンパイルされたメソッド内でバックワードブランチに対して、ターゲットで命令を実行することをさらに伴い、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２２】
前記方法は、前記コンパイルされたメソッドの実行の頻度が、所定のしきい値を下回るとき、該コンパイルされたメソッドをイヴィクトし、その結果、該方法は、該コンパイルされたメソッドが再び実行されるとき、続いてリコンパイルもしくはインタープリットされなければならないことをさらに包含する、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２３】
前記方法は、所定のしきい値を調整することにより、前記コンパイルされたメソッドの数を制御することをさらに包含する、請求項２２に記載のコンピュータ読み取り可能格納媒体。
【請求項２４】
前記カウンターを定期的に減少させることにより、デケイを導入して、それによって、前記コンパイルされたメソッドの過去の実行の関連性を自然にフェードすることをさらに包含する、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２５】
前記方法は、いずれかの方法に関連付けられたいずれかのカウンターが、所定のしきい値に達するとき、前記カウンターを定期的に減少させることをさらに包含する、請求項２４に記載のコンピュータ読み取り可能格納媒体。
【請求項２６】
前記方法は、前記フラグに割り当てられた重量値を定期的に増加させ、その結果、前記コンパイルされたメソッドの後の実行は、該コンパイルされたメソッドの前の実行より多くカウントすることをさらに包含する、請求項１４に記載のコンピュータ読み取り可能格納媒体。
【請求項２７】
バーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定する装置であって、
コンパイルされたメソッドが実行されるとき、決定するように構成されている決定メカニズムと、
該コンパイルされたメソッドに対応しているフラグをセットするように構成されているフラグセッティングメカニズムであって、該コンパイルされたメソッドが実行しているとき、該コンパイルされたメソッドが実行していることを示すフラグセッティングメカニズムと、
該フラグを定期的にスキャンして、フラグがセットされているとき、対応するカウンターの値を増加させて、該フラグをリセットするように構成されているスキャニングメカニズムと、
該カウンターの該値を解析することにより、該コンパイルされたメソッドの実行の頻度を決定するように構成されている解析メカニズムと
を備えた、装置。
【請求項２８】
前記カウンターの増加の間の時間間隔を調整するように構成されている調整メカニズムをさらに備えた、請求項２７に記載の装置。
【請求項２９】
前記決定メカニズムは、前記コンパイルされたメソッドが、第２のコンパイルされたメソッドを呼び出すとき、該コンパイルされたメソッドが、命令を実行することによって実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３０】
前記決定メカニズムは、前記コンパイルされたメソッドが、第２のコンパイルされたメソッドによって呼び出されるとき、該コンパイルされたメソッドが、命令を実行することによって、実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３１】
前記決定メカニズムは、前記コンパイルされたメソッドから、第２のコンパイルされたメソッドに戻るとき、該コンパイルされたメソッドが、命令を実行することによって、実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３２】
前記決定メカニズムは、第２のコンパイルされたメソッドから、前記コンパイルされたメソッドに戻るとき、該コンパイルされたメソッドが、命令を実行することによって、実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３３】
前記決定メカニズムは、前記コンパイルされたメソッドが、該コンパイルされたメソッド内でバックワードブランチを開始するとき、命令を実行することによって、実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３４】
前記決定メカニズムは、前記コンパイルされたメソッドが、該コンパイルされたメソッド内でバックワードブランチに対して、ターゲットで命令を実行することによって、実行されるとき、決定するようにさらに構成されており、該命令が、該コンパイルされたメソッドに対応する前記フラグをセットする、請求項２７に記載の装置。
【請求項３５】
前記コンパイルされたメソッドの実行の頻度が、所定のしきい値を下回るとき、該コンパイルされたメソッドをイヴィクトし、その結果、該方法は、該コンパイルされたメソッドが再び実行されるとき、続いてリコンパイルもしくはインタープリットされなければならないように構成されているイヴィクションメカニズムをさらに備えた、請求項２７に記載の装置。
【請求項３６】
前記所定のしきい値を調整することによって、前記コンパイルされたメソッドの数を制御するように構成されている調整メカニズムをさらに備えた、請求項３５に記載の装置。
【請求項３７】
前記カウンターを定期的に減少させることにより、デケイを導入して、それによって、前記コンパイルされたメソッドの過去の実行の関連性を自然にフェードするように構成されているデケイメカニズムをさらに備えた、請求項２７に記載の装置。
【請求項３８】
前記デケイメカニズムは、いずれかの方法に関連付けられたいずれかのカウンターが、所定のしきい値に達するとき、前記カウンターを定期的に減少させるようにされに構成されている、請求項３７に記載の装置。
【請求項３９】
前記フラグに割り当てられた重量値を定期的に増加させて、その結果、前記コンパイルされたメソッドの後の実行は、該コンパイルされたメソッドの前の実行より多くカウントするようにさらに構成されているウエイティングメカニズムである、請求項２７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、ここで、３５Ｕ．Ｓ．Ｃ．§１１９の下で、Ｕ．Ｓ．特許仮出願６０／５５０，８０２、２００４年３月５日出願、「Ｃｏｄｅ  Ｃａｃｈｅ  Ｅｖｉｃｔｉｏｎ  Ｒａｎｋｉｎｇ  Ｂａｓｅｄ  ｏｎ  Ｅｘｅｃｕｔｉｏｎ  Ｉｎｔｅｒｖａｌ  Ｓｕｍｍａｒｉｚａｔｉｏｎ」という名称、発明者Ｂｅｒｎｄ  Ｊ．Ｗ．ＭａｔｈｉｓｋｅとＯｌｅｇ  Ａ．Ｐｌｉｓｓ（代理人整理番号  ＳＵＮ０４−０４８１ＰＳＰ）の優先権主張をする。
【０００２】
本発明は、コンピュータシステム内におけるバーチャルマシンに関する。特に、本発明は、バーチャルマシン内でコンパイルされたメソッドを実行する頻度を決定する方法と装置に関する。
【背景技術】
【０００３】
（関連技術）
Ｊａｖａ  ２プラットフォーム、Ｍｉｃｒｏ  Ｅｄｉｔｉｏｎ（Ｊ２ＭＥ（登録商標））は、無線デバイスの領域において非常に人気が高くなった。Ｍｏｔｏｒｏｌａ、Ｎｏｋｉａ、ＮＴＴ  ＤｏＣｏＭｏ、ＲＩＭ、Ｓｉｅｍｅｎｓ、および無線デバイス産業における他に多く主要な企業は、最近、非常に大容量のＪ２ＭＥの使用可能なデバイスを出荷し始めた。２００３年だけで、２億台を超えるＪ２ＭＥの使用可能なモバイルフォンが出荷されたと推定される。
【０００４】
これらの無線デバイスの主な制限は、プログラムを実行するために利用可能なメモリが比較的少量であるということである。多くの方法は、これらのメモリ制限があるデバイスにおいてメモリの使用を最適化するために発展してきた。かつてのそのような方法は、インタープリット（ｉｎｔｅｒｐｒｅｔ）されたコードとコンパイル（ｃｏｍｐｉｌｅ）されたコードとの実行を両方ともサポートする動的なコンパイラーを用いることを伴う。より頻繁に実行されるコードは、コンパイルモードにおいてコンパイルされ、実行される。一方で、より少ない頻度で実行されるコードは、インタープリットモードにおいて実行される。ここで留意すべきは、コンパイルされたコードは、インタープリットされたコードよりもはるかに早く実行するということである。しかし、コンパイルされたコードは、インタープリットされたコードよりもはるかに多くの空間を要する。
【０００５】
この動的に生成されたコンパイルされたコードが、オブジェクトヒープ上に常駐していようと、メモリの別々のコードキャッシュ領域内に常駐していようと、このコンパイルされたコードは、一般的には、頻繁にアクセスされなくなったときにメモリからイヴィクト（ｅｖｉｃｔ）される。このイヴィクション（ｅｖｉｃｔｉｏｎ）は、一般的にはガーベージコレクション（ＧＣ）処理を介して行われる。ここで留意すべきは、コンパイルされたコードは、ＧＣ処理によって処理されるオブジェクトに対するポインターを含み得るということである。
【０００６】
コンパイルされたコードの実際のイヴィクションは、ＧＣの間に起こるが、イヴィクション処理の犠牲選択の部分は、ミューテーター（ｍｕｔａｔｏｒ）実行中に収集された情報に基づくことが理想的である。ここで、このシステムは、コンパイルされたメソッドが使用される頻度に従って、コンパイルされたメソッドをランク付けするための情報を収集することができる。
【０００７】
メモリ制限が厳しくなるにつれて、このランキング処理の質が、全体の実行速度を高く維持するためにますます重要になる。他方で、ランキングメカニズムが複雑になり過ぎた場合、ランキングデータを取得することは、ミューテーターへの追加的な大きな負担を作成し得る。
【０００８】
方法が使用されている時、決定するために、方法の特定場所にソフトウェアフックを挿入することは一般的なやり方である。これらのフックは、プログラムの実行中に出会うとき、データを収集し、様々な計算を行うことができる。
【０００９】
フックを使用する現行の犠牲選択のスキームは、２つのカテゴリ、重量フックと軽量フックとに分類される。重量フックを使用すると、システムは、上記のフック内において直接的にルーチンに関する重さ計算を行う。例えば、フックは、Ｊａｖａ（登録商標）方法のカウンターを増加させることができる。対照的に、軽量フックは、フックでできるだけ少なく計算することによって速度が落ちるミューテーターの最小量を生成する。例えば、所定のＧＣサイクル中にフックが実行される初回のみ、プロローグと呼ばれるＪａｖａ（登録商標）方法をパッチするＪ２ＭＥ（登録商標）内のＣｏｎｎｅｃｔｅｄ  Ｌｉｍｉｔｅｄ  Ｄｅｖｉｃｅ  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ＨｏｔＳｐｏｔ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（ＣＬＤＣ  ＨＩ）において自己書き換えコードスキームがある。同じルーチンの後に続く使用では、ミューテーターのオーバーヘッドがない。
【００１０】
方法の使い方を決定する別の方法は、統計的なサンプリングを使用することである。統計的なサンプリングは、現行のスタックを定期的に分析することによって動作することにより、ルーチンが実行しているときを決定する。（統計的なサンプリング方法は、また、一般的に比較的低頻度で実行するので、軽量でカウントする。）
しかし、前述した全ての技術は欠点を有する。それら技術は、顕著にミューテーターを減速させるか、またはよい犠牲選択のための十分な情報を収集しない。さらに、ＧＣ間の間隔は、一般的に大き過ぎて、多数の方法から有益なランキングを確立することができない。（ＣＬＤＣ  ＨＩのように複数ビットにおける複数のＧＣ間隔を反映することは、１つのＧＣ間隔は一般的に既に長すぎるので、この問題を解決しない。）
従って、前述した欠点なしにバーチャルマシン内でコンパイルされたメソッドを実行する頻度を決定する方法が必要とされる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
バーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定することを容易にするシステムを提供する。
【課題を解決するための手段】
【００１２】
（概要）
本発明の１つの実施形態は、バーチャルマシン内でコンパイルされたメソッドの実行の頻度を決定することを容易にするシステムを提供する。システムは、コンパイルされたメソッドが実行されるとき、決定することによって始まる。その場合、システムは、コンパイルされたメソッドに対応するコンパイルされたフラグをセットすることにより、コンパイルされたメソッドが実行していることを示す。システムは、フラグを定期的にスキャンし、フラグがセットされているとき、対応するカウンターの値を増加させて、それから、フラグをリセットする。最終的に、システムは、カウンターの値を解析することにより、コンパイルされたメソッド実行の頻度を決定する。
【００１３】
この実施形態の１つの変形において、システムは、カウンターの増加の間の時間間隔を調整する。
【００１４】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、第２のコンパイルされたメソッドを呼び出すとき、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００１５】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、第２のコンパイルされたメソッドによって呼び出されるとき、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００１６】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、そのコンパイルされたメソッドから第２のコンパイルされたメソッドへ戻るとき、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００１７】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、第２のコンパイルされたメソッドからコンパイルされたメソッドへ戻るとき、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００１８】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、そのコンパイルされたメソッド内でバックワードブランチを開始するとき、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００１９】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドが、コンパイルされたメソッド内でバックワードブランチに対してターゲットで、命令を実行することによって実行されるとき、決定し、命令が、コンパイルされたメソッドに対応するフラグをセットする。
【００２０】
この実施形態の１つの変形において、システムは、コンパイルされたメソッドの実行の頻度が、所定のしきい値を下回るとき、コンパイルされたメソッドをイヴィクトし、その結果、メソッドは、コンパイルされたメソッドが再び実行されるとき、続いてリコンパイルもしくはインタープリットされなければならい。
【００２１】
さらなる変形において、システムは、所定のしきい値を調整することにより、コンパイルされたメソッドの数を制御する。
【００２２】
この実施形態の１つの変形において、システムは、カウンターを定期的に減少させることにより、デケイを導入して、それによって、コンパイルされたメソッドの過去の実行の関連性を自然にフェードする。
【００２３】
さらなる変形において、システムは、いずれかの方法に関連付けられたいずれかのカウンターが、所定のしきい値に達するとき、カウンターを定期的に減少させる。
【００２４】
この実施形態の１つの変形において、システムは、フラグに割り当てられた重量値を定期的に増加させ、その結果、コンパイルされたメソッドの後の実行は、コンパイルされたメソッドの前の実行より多くカウントする。
【発明を実施するための最良の形態】
【００２５】
以下の説明が提供されることにより、当業者は本発明を作成し使用することができる。また、以下の説明は特定の用途とその条件との関連で提供される。開示された実施形態への様々な改良は、当業者にとって容易に明白であり、ここで定義された一般的な原則は、本発明の精神と範囲から逸脱することなく、他の実施形態と用途とに適用され得る。従って、本発明は説明された実施形態に限られるものではなく、ここで開示された原則と特徴と一致する最も広い範囲を許容する。
【００２６】
この詳細な説明の中で記載されるデータ構造とコードとは、一般的にコンピュータの読み取り可能格納媒体に格納され、このコンピュータの読み取り可能格納媒体は、コンピュータシステムによって使用するためのコードおよび／またはデータを格納することができる任意のデバイスまたは媒体であり得る。これには、この限りではないが、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）とＤＶＤ（デジタル多用途ディスクまたはデジタルビデオディスク）、および（信号が変調される搬送波と共に、もしくは搬送波なしで）送信媒体で具体化されるコンピュータの命令信号といった磁気および光学の記憶デバイスが含まれる。例えば、送信媒体はインターネットといった通信ネットワークを含む。
【００２７】
（メモリ制限があるコンピューティングデバイス）
図１は、本発明の実施形態に従ったメモリ制限があるコンピューティングデバイス１００を示す。メモリ制限があるコンピューティングデバイス１００は、この限りではないが、携帯電話、マイクロプロセッサに基づくコンピュータシステム、デジタル信号プロセッサ、携帯型コンピューティングデバイス、整理記録ツール、デバイスコントローラー、装置内のコンピューテーショナルエンジンを含む、いかなるタイプのコンピューティングデバイスを含むことができる。メモリ制限があるコンピューティングデバイス１００は、コンパイルされたメソッドとインタープリットされたメソッドとの両方の実行を交互にサポートするＪａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ（ＪＶＭ）１０２を備える。（ＪＡＶＡ、ＪＶＭ、ＪＡＶＡ  ＶＩＲＴＵＡＬ  ＭＡＣＨＩＮＥという用語は、ＳＵＮ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．ｏｆ  Ｓａｎｔａ  Ｃｌａｒａ，Ｃａｌｉｆｏｒｎｉａの登録商標である。）ＪＶＭ１０２はプラットフォーム独立バーチャルマシンのいかなるタイプでもあり得て、Ｊａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅに限られるものと意図されていない。
【００２８】
ＪＶＭ１０２は、コンパイルされたメソッドの格納装置１１０を備える。ＪＶＭ１０２内でのパフォーマンスを向上させるために、いくつかのメソッドはコンパイルされて、コンパイルされたメソッドの格納装置１１０に加えられる。これにより、これらのメソッドはインタープリットされたメソッドよりも早く実行することができる。しかし、コンパイルされたメソッドは、コンパイルされたコードの質によって、一般的にインタープリットされたメソッドよりも多くのスペースを要する。さらに、多くのシステムにおいて、インタープリットされたコードを、コンパイルの後に破棄することができない。従って、ＪＶＭ１０２は、より高い頻度で使用されるメソッドのみを動的にコンパイルし、それらをコンパイルされたメソッドの格納装置１１０に置く。加えて、ＪＶＭ１０２は、後に続くメソッドの実行がインタープリットモードで行われるように、より低い頻度で使用されるコンパイルされたメソッドをコンパイルされたメソッドの格納装置１１０からイヴィクトすることにより、スペースを節約する。このようなイヴィクションは、ガーベージコレクションオペレーションの外で作動する他のイヴィクションオペレーション中と同様に、ガーベージコレクションオペレーション中に行われ得る。
【００２９】
（フラグアレイ）
図２は、本発明の実施形態に従ったフラグアレイ２００を示す。フラグアレイ２００は、前述したように、重量フックの犠牲選択の質と軽量フックの全体コストとの近くに到達する形で、犠牲選択を容易にするために用いられる。本発明の１つの実施形態では、ＪＶＭ１０２における動的なコンパイラーは、（１）呼ばれる人のプロローグ、（２）呼び出し直後、（３）バックワードブランチの直前に、おいて、付加的なコードを生成する。前記の３つの場所を用いて、最も適切なメソッドのアクセス（結局インタープリットより実行されるより良い、長いループのないコードストレッチを除いて）をキャッチすることができる。また、その他のフックの場所（または前記の場所のサブセット）は、恐らく正確性が欠けるのでメソッドランキングの質が低くなるが、これもまた使用され得る。
【００３０】
本発明は、フックを非常に短いインラインアクション（ｉｎｌｉｎｅ  ａｃｔｉｏｎ）に制限する。すなわち、実行されているルーチン（メソッド、機能）に対応するフラグアレイ２００内にフラグをセットする。図２に示された例では、ビットがフラグアレイ２００にセットされており、コンパイルされたメソッド２０２でコンパイルされたメソッドを実行することを表す。フラグをセットするための実際のマシンの命令は、パフォーマンスを損なうことなくアドレス指定が可能な最小のメモリユニット（ワード、バイト、ビット）のアドレス指定をするために選ばれる。一般的に、実際のマシンの命令は１バイトをセットする。しかし、あるアーキテクチャにおいては、完全なワードまたは単一のビットをセットし得る。これらのフラグは、グローバル変数によって特定されるオフセットに位置づけられるフラグアレイ２００内に含まれる。各コンパイルされたメソッドは、フラグアレイ２００へそれ自身のインデックス（コンパイルされたメソッド２０２内に）を有する。ここで留意すべきは、イヴィクトされたルーチンのインデックスは再度使用することができるということである。
【００３１】
理論的に、当該のメソッドが時間内に所定の地点で使用されているという事実は、ミューテーターの実行が進行するにつれて、有用性の点で衰える。前述したように、ビットを収集して、それをランク付けする目的で使用するためにＧＣが起きるのを待つということは、一般的に時間がかかり過ぎる。１ビットよりも多くのビットを収集することは、他方で、ミューテーターの負担を増やす。本発明は、収集されたビットが調節されることにより、収集されたビットの関連性を、自然にフェードすることを表す第三段階を導入することによって、この緊張を解決する。
【００３２】
（参照アレイ）
図３は、本発明の実施形態に従った参照アレイ３００を示す。参照アレイ３００は、フラグのインデックスを、コンパイルされたメソッド１１２、コンパイルされたメソッド３０２、コンパイルされたメソッド３０４といった、それぞれのコンパイルされたメソッドにマッピングする。さらに、付加的な「カウント」のフィールドが各メソッドに関連付けられる。これは、第３のアレイもしくはカウントアレイ３１０によって、もしくは、各メソッドに付加的なフィールドを置くことによって、関連付けられる。前記のデータ構造を用いることで、システムは、コンパイルされたルーチン全てを反復し、フラグがセットされているフィールドに従って「カウント」のフィールドを更新する。カウントフィールドが更新される後に、全てのフラグはリセットされる。
【００３３】
本発明の１つの実施形態において、カウントフィールドを更新するプロセスは２つの段階を伴う。第１の段階では、全てのカウントが下げられることにより、メソッドの使用の関連性を自然にフェードする。そして、第２の段階では、（必要に応じていくらかの重量要素を要する）フラグは、所定の間隔でフラグのセットを有するそれらのルーチンのみに加えられる。
【００３４】
本発明のもう１つの実施形態では、段階がたった１つだけであり、そこで、セットされたフラグを有するメソッドのための全てのカウントが更新されるが、セットされたフラグのための重量要素は間隔毎に増加する。カウントの低下は、従って、フラグの重量がリセットされた後に、ＧＣの時まで遅らせることができる。ここで留意すべきは、このスキームはミューテーターへの影響をさらに減らすことである。
【００３５】
本発明の第３の実施形態では、カウントのデケイがコンパイルされた任意のメソッドのためのあるカウントしきい値に到達することによって、トリガーされる。このデケイの処理は、典型的なプログラム実行をモデリングすることを助け、そしてそれは、一般的に小規模のコンパイルされたワーキングセットのメソッドへの高頻度のアクセスを伴う。ここでのワーキングセットは自然に発達する。通常のプログラム実行中、あるメソッドは、特定の時間内で、他のメソッドよりもはるかに高い頻度で実行される。自然に、最も頻繁に実行されるメソッドのセット（ワーキングセット）は、プログラムが実行するにつれて変化する。この実施形態において、カウントのデケイの処理は、最近あまり実行されていないメソッドの重要性を減らすので、重要であり、そしてそれは、ワーキングセット内のメソッドのカウントの価値をより強くすることを助ける。
【００３６】
より多くのメソッドが実行されるよりもインタープリットされている場合を考慮することもまた重要である。全体のパフォーマンスを上げるために、本発明の１つの実施形態では、仕事量をインタープリットへシフトすることにより、デケイラウンドが誘発される。例えば、これは、特定の時間間隔の間、コンパイルされる実行に対するインタープリットされる実行の割合を観察することによって求められ得る。事実上、本発明のこの実施形態により、デケイの処理に実質的に無関係な間隔の長さが選択される。このデケイの「タイムフロー」は柱時計の時間とは分離されている。
【００３７】
さらに、ガーベージコレクション時に、すべての方法は、累積されたカウントによって、ランク付けされる。システムは、まず、カウントを方法によってソートし、もしくはあるカウントのしきい値より低い犠牲を繰り返し検索し、所定のイヴィクションターゲット（ｅｖｉｃｔｉｏｎ  ｔａｒｇｅｔ）が満たされるまでしきい値を増加させることを保つ。サマリゼーション間隔が、フラグアレイ２００内のセットされたフラグの関連性を維持するために十分に短い必要があることに留意する。サマリゼーション間隔は、またミューテーターの負担を広げるために十分に長い必要がある。これらの要求のバランスをとることにおいて、システムは、ミューテータスピードを考慮する必要がある。（例えば、フラグセッティングフックが、ヒットされる速度）
システムは、またインデックスのオーバーフローを処理する必要がある。各インデックスが、コンパイルされる前に、メソッドに割り当てられる。利用可能なインデックスがない場合、システムは、インデックスがあくまでコンパイルを止めるか、もしくは現在ランキングの低いルーチンのインデックスを取得しようとし得る。最初のインデックスの所有者が、まれにフラグをセットしたとき、不正確が起こる。しかしながら、これはまれであり、十分大きいアレイを選択することによってこの上なく保証されているので、インデックスのオーバーフローは、起こり得そうもない。このことを達成するために、アレイのサイズは、ヒープのサイズに比例し得る。（例えば、１メガバイト（ＭＢ）のヒープに対して、５００の要素を有するアレイが用いられ得る。）
（フラグビットのセット）
図４は、本発明の実施形態に従って、フラグアレイ２００内のフラグビットをセットするプロセスを示すフローチャートを示す。システムは、コンパイルされたメソッド（例えば、コンパイルされたメソッド１１２）が実行されるときを決定することによって始まる（ステップ４０２）。これは、上述の実行フックを用いることによって達成され得る。最終的に、システムは、フラグビットをフラグアレイ２００内にセットすることにより、コンパイルされたメソッドが実行したことを示す（ステップ４０６）。
【００３８】
（セットされたフラグビットを累積する）
図５は、本発明の実施形態に従って、フラブアレイ２００からカウントアレイ３１０に、セットされたフラグビットを累積するプロセスを示すフローチャートを示す。ある定期的間隔で、システムは、セットされたフラグビットに対して、フラグアレイ２００をスキャンする（ステップ５０２）。それぞれのセットされたフラグビットに対して、システムは、フラグアレイ２００内のフラグビットに対応するカウントアレイ３１０内でカウントを増加させる（ステップ５０４）。カウントアレイ３１０内のすべての適正なカウントが、増加されたら、システムは、次の定期的間隔で、フラグアレイ２００内のすべてのフラグビットを消去する（ステップ５０６）。カウントアレイを増加する一方で、システムが、カウントの１つにおいて、オーバーフローを検出するとき、システムは、上述のように、カウントアレイ３１０のビットをシフトすることによって、デケイを導入し得ることに留意する。
【００３９】
本発明の実施形態の上述が、例示および記載だけの目的のために示されてきた。それらは、完全であることは意図されておらず、また、開示されたフォームだけに本発明を制限することを意図されていない。従って、多くの改良および変形が、当業者にとってあきらかである。加えて、上述の開示は、本発明を制限することを意図されていない。本発明の範囲は、請求項によって定義される。
【図面の簡単な説明】
【００４０】
【図１】本発明の実施形態に従った、メモリ制限があるコンピューティングデバイスの図である。
【図２】本発明の実施形態に従った、フラグアレイの図である。
【図３】本発明の実施形態に従った、参照アレイの図である。
【図４】本発明の実施形態に従って、フラグビットをセットするプロセスを図示するフローチャートである。
【図５】本発明の実施形態に従って、セットされたフラグビットを蓄積するプロセスを図示するフローチャートである。
【符号の説明】
【００４１】
１００  メモリ制限があるコンピューティングデバイス
１０２  Ｊａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ（ＪＶＭ）
１１０  コンパイルされたメソッドの格納装置
１１２、２０２、３０２、３０４  コンパイルされたメソッド
２００  フラグアレイ
３００  参照アレイ
３１０  カウントアレイ
【図１】
2005251208.tif 000003
【図２】
2005251208.tif 000004
【図３】
2005251208.tif 000005
【図４】
2005251208.tif 000006
【図５】
2005251208.tif 000007