(57)【要約】【課題】キャッシュ効果オブジェクトローダを提供する。【解決手段】性能を改善するために今日の多くのプロセッサのキャッシュアーキテクチャの利点を得る改善されたオブジェクトローダを提供する。ＰＥＮＴＩＵＭプロセッサのような今日の最新のプロセッサの幾らかは、１次キャッシュと２次キャッシュを利用する２レベルキャッシュスキームを有し、１次キャッシュに包含されたデータは、メインメモリのデータよりも５０乃至１５０倍速くアクセスされ得る。改善されたオブジェクトローダは、オブジェクトをロードするために、ハッシュテーブルとオブジェクトハンドルテーブルとを使用し、これらのテーブルの各々は、システム性能を向上させるために、プロセッサのキャッシュアーキテクチャを十分に利用するような方法で設計され、利用される。【選択図】  図２
2008027450.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介してリモートコンピュータシステムに接続されたコンピュータシステムのメモリにおけるメモリアドレスに配置されたオブジェクトにアクセスする方法であって、前記コンピュータシステムはバケットの複数のチェーンを有するハッシュテーブルを備えており、それぞれのバケットは、オブジェクトに関する識別子を含むエントリと、前記オブジェクトに関するオブジェクトハンドルテーブルのフィールドに対する参照とを有し、前記オブジェクトハンドルテーブルにおけるフィールドは前記オブジェクトのメモリアドレスを含む、方法において、
要求されたオブジェクトのメモリアドレスに関するコーラから、前記要求されたオブジェクトのネットワーク・ワイド・オブジェクト識別子を含む要求を受信するステップと、
前記ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子に変換するステップと、
前記システム・ワイド・オブジェクト識別子をハッシュ関数に入力し、前記ハッシュテーブルにおける前記バケットの複数のチェーンの中の１つを参照するインデックスを生成するステップと、
インデックスを用いて前記バケットチェーンにアクセスするステップと、
前記要求されたオブジェクトの前記システム・ワイド・オブジェクト識別子に対して、それぞれのエントリの識別子を照合することによって、前記要求されたオブジェクトのエントリに関するバケットチェーンをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスし、前記オブジェクトハンドルテーブルの中への参照を得るステップと、
前記参照を用いて前記オブジェクトハンドルテーブルにアクセスし、要求されたオブジェクトのメモリアドレスを含むフィールドを識別するステップと、
前記識別されたフィールドに含まれる要求されたオブジェクトのメモリアドレスを前記コーラに返すステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記コンピュータシステムのメモリの中のそれぞれのオブジェクトは前記オブジェクトに関するネットワーク・ワイド・オブジェクト識別子を含み、前記ハッシュテーブルのそれぞれのエントリの識別子はオブジェクトを一意的に識別せず、前記バケットチェーンをサーチするステップはそれぞれのエントリの識別子に対して前記システム・ワイド・オブジェクト識別子の一部を照合するステップを含んでおり、前記オブジェクトハンドルテーブルにアクセスするステップは、
前記識別されたフィールドに含まれるメモリアドレスにおける前記オブジェクトにアクセスするステップと、
前記要求されたオブジェクトのネットワーク・ワイド・オブジェクト識別子と前記アクセスされたオブジェクトのネットワーク・ワイド・オブジェクト識別子とを比較することによって、前記アクセスされたオブジェクトが前記要求されたオブジェクトであるかどうかを判断するステップと、
前記アクセスされたオブジェクトが前記要求されたオブジェクトではないと判断されるときには、
前記バケットチェーンの中のエントリを選択するステップと、
前記選択されたエントリの参照を用いて前記オブジェクトハンドルテーブルにアクセスして、前記要求されたオブジェクトのメモリアドレスを含むオブジェクトハンドルテーブルの中のフィールドを確認するステップと、
確認されたフィールドに含まれる前記要求されたオブジェクトのメモリアドレスを前記コーラに返すステップと、
を含むことを特徴とする方法。
【請求項３】
請求項１記載の方法において、前記ネットワーク・ワイド・オブジェクト識別子を前記システム・ワイド・オブジェクト識別子に変換するステップは、前記システム・ワイド・オブジェクト識別子がより少ないスペースを要求するように前記ネットワーク・ワイド・オブジェクト識別子を圧縮するステップを含むことを特徴とする方法。
【請求項４】
請求項１記載の方法において、前記オブジェクトハンドルテーブルの中の前記フィールドの複数はメモリアドレスを含まず、前記オブジェクトハンドルテーブルにアクセスするステップは、
前記オブジェクトハンドルテーブルの中の前記識別されたフィールドが、前記要求されたオブジェクトのメモリアドレスを含まないかどうかを判断するステップと、
前記識別されたフィールドが、前記要求されたオブジェクトのメモリアドレスを含まないときには、
前記ネットワーク・ワイド・オブジェクト識別子を用いて、前記ネットワークの遠隔位置から、前記要求されたオブジェクトにアクセスするステップと、
前記要求されたオブジェクトをあるメモリアドレスにおいて前記メモリの中にロードするステップと、
を含むことを特徴とする方法。
【請求項５】
請求項４記載の方法において、前記ハッシュテーブルの中のそれぞれのエントリにおける識別子はオブジェクトを一意的に識別せず、前記オブジェクトハンドルテーブルの中にメモリアドレスを含まないそれぞれのフィールドはシステム・ワイド・オブジェクト識別子を含み、前記バケットチェーンをサーチするステップはそれぞれのエントリの識別子に対して前記システム・ワイド・オブジェクト識別子の一部を照合するステップを含んでおり、この方法は、更に、
前記要求されたオブジェクトのシステム・ワイド・オブジェクト識別子と前記オブジェクトハンドルテーブルの中の前記識別されたフィールドのシステム・ワイド・オブジェクト識別子とを比較し、前記オブジェクトハンドルテーブルの中の前記フィールドが前記要求されたオブジェクトのメモリアドレスを含まないかどうかの判断に応答して、その同等性を判断するステップと、
前記要求されたオブジェクトのシステム・ワイド・オブジェクト識別子が前記フィールドのシステム・ワイド・オブジェクト識別子と等しくないと判断されるときには、
前記バケットチェーンの中の別のエントリを選択するステップと、
前記選択されたエントリの参照を用いて前記オブジェクトハンドルテーブルにアクセスし、前記要求されたオブジェクトのメモリアドレスを含むフィールドにアクセスするステップと、
前記要求されたオブジェクトのメモリアドレスを前記コーラに返すステップと、
を含むことを特徴とする方法。
【請求項６】
請求項４記載の方法において、前記メモリアドレスを返すステップは、前記要求されたオブジェクトに関する前記オブジェクトハンドルテーブルの中の識別されたフィールドに前記メモリアドレスを記憶するステップを含むことを特徴とする方法。
【請求項７】
請求項４記載の方法において、前記要求されたオブジェクトは参照されたオブジェクトのネットワーク・ワイド・オブジェクト識別子を含み、前記要求されたオブジェクトをロードするステップは、
前記参照されたオブジェクトに関する前記オブジェクトハンドルテーブルにフィールドを配分するステップと、
前記配分されたフィールドに関する参照されたオブジェクトのネットワーク・ワイド・オブジェクト識別子を上書きするステップと、
を含むことを特徴とする方法。
【請求項８】
請求項４記載の方法において、前記要求されたオブジェクトにアクセスするステップは、
機能的に関連する所定の数のオブジェクトをプリフェッチするステップと、
前記所定の数のオブジェクトに関する前記オブジェクトハンドルテーブルの中にフィールドを配分するステップと、
前記所定の数のオブジェクトに関するハッシュテーブルのバケットチェーンの中にエントリを配分するステップと、
を含むことを特徴とする方法。
【請求項９】
請求項１記載の方法において、前記ネットワーク・ワイド・オブジェクト識別子は機能的に関連するオブジェクトが等しいオリジン部分を有するようにオリジン部分を有し、前記ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子に変換するステップは、ネットワーク・ワイド・オブジェクト識別子のオリジン部分にシーケンシャルな数を割り当てるステップを含むことを特徴とする方法。
【請求項１０】
請求項９記載の方法において、前記コンピュータシステムは、当該コンピュータシステムのメモリの中のオブジェクトに関するネットワーク・ワイド・オブジェクト識別子のそれぞれのオリジン部分にシーケンシャルな数をマップするマッピングテーブルを維持し、前記ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子に変換するステップは、
前記ネットワーク・ワイド・オブジェクト識別子のオリジン部分を前記マッピングテーブルの中の照合するオリジン部分に照合するステップと、
前記照合するオリジン部分にマップされたシーケンシャルな数に等しい前記システム・ワイド・オブジェクト識別子のオリジン部分を設定するステップと、
を含むことを特徴とする方法。
【請求項１１】
請求項１記載の方法において、前記ハッシュ関数は、複数のシステム・ワイド・一意性識別子を単一のインデックスにマップして、機能的に関連するオブジェクトに関するエントリをバケットの同じチェーンの中へ記憶することを容易にするように設計されていることを特徴とする方法。
【請求項１２】
請求項１１記載の方法において、前記ハッシュ関数は、更に、一時的に関連するオブジェクトに関するエントリをバケットの同じチェーンに記憶することを容易にするように設計されていることを特徴とする方法。
【請求項１３】
請求項１記載の方法において、前記コンピュータシステムは、それぞれのキャッシュラインがキャッシュラインサイズを有するキャッシュラインを有するキャッシュを有し、前記ハッシュテーブルのそれぞれのチェーンのそれぞれバケットは前記キャッシュラインサイズに等しいサイズを有し、前記バケットチェーンにアクセスするステップは、前記バケットチェーンのバケットにアクセスするステップを含み、アクセスされたそれぞれのバケットは、正確に適合する前記キャッシュラインの中の１つにロードされることを特徴とする方法。
【請求項１４】
請求項１記載の方法において、前記オブジェクトハンドルテーブルエントリは機能的に関連するオブジェクトのメモリアドレスを含むフィールドのグループを含み、前記コンピュータシステムは、キャッシュラインサイズを有するキャッシュラインを有するキャッシュを有し、それぞれのエントリは前記キャッシュラインサイズに等しいサイズを有し、前記オブジェクトハンドルテーブルにアクセスするステップは、エントリにアクセスするステップを含み、前記アクセスされたエントリは、正確に適合する前記キャッシュラインの中の１つにロードされることを特徴とする方法。
【請求項１５】
コンピュータシステムにおいて、バケットを有するハッシュテーブルにデータを記憶する方法であって、前記コンピュータシステムはオブジェクトを有し、それぞれのオブジェクトは関連するデータと識別子とを有するオブジェクトを有し、前記識別子の一部は機能的に関連するオブジェクトでは等しい、方法において、
前記ハッシュテーブルの中のバケットを参照するインデックスを生成するハッシュ関数を、前記ハッシュ関数が機能的に関連するオブジェクトについては同じインデックスを生成するように選択するステップと、
前記ハッシュ関数を用いて、前記関連するデータを前記ハッシュテーブルの中に挿入するステップであって、前記関連するデータは、機能的に関連する場合には、同じバケットに記憶される、ステップと、
を含むことを特徴とする方法。
【請求項１６】
コンピュータシステムにおいて、バケットを有するハッシュテーブルにデータを記憶する方法であって、前記コンピュータシステムはオブジェクトを有し、それぞれのオブジェクトは関連するデータを有するオブジェクトを有している、方法において、
それぞれが機能的に関連するオブジェクトを含む複数のグループに前記オブジェクトをグループ分けするステップと、
それぞれのグループに関する前記関連するデータを前記ハッシュテーブルに記憶するステップであって、それぞれのグループの機能的に関連するオブジェクトに関する前記関連するデータは同じバケットに記憶される、ステップと、
を含むことを特徴とする方法。
【請求項１７】
請求項１６記載の方法において、
前記オブジェクトをグループ分けするステップは、前記オブジェクトに識別子を割り当てて、前記識別子の一部が１つのグループの中のそれぞれの機能的に関連するオブジェクトに関して等しくなるようにするステップと、前記オブジェクトを前記識別子の前記一部に基づいてグループ分けするステップとを含むことを特徴とする方法。
【請求項１８】
請求項１６記載の方法において、
前記複数のグループの前記機能的に関連するオブジェクトには等しいインデックスが生成されるようにインデックスを前記バケットの中に生成することによって、衝突を生じさせるハッシュ関数を選択するステップを含み、
それぞれのグループからの前記関連するデータを記憶するステップは、それぞれのオブジェクトに関し、
前記ハッシュ関数を呼び出し、指定されたバケットを参照するインデックスを生成するステップと、
前記オブジェクトに関する関連するデータを前記指定されたバケットの中に記憶するステップと、
を含むことを特徴とする方法。
【請求項１９】
請求項１６記載の方法において、前記コンピュータシステムはキャッシュラインサイズを有するキャッシュラインを備えたキャッシュを有し、前記バケットはキャッシュラインサイズであることを特徴とする方法。
【請求項２０】
請求項１６記載の方法において、それぞれのバケットはサブバケットのチェーンであることを特徴とする方法。
【請求項２１】
請求項２０記載の方法において、それぞれのバケットは複数のオブジェクトに関する関連したデータを含み、それぞれのサブバケットは前記複数のオブジェクトのそれぞれに関する識別子を含むことを特徴とする方法。
【請求項２２】
請求項２０記載の方法において、前記コンピュータシステムの中のそれぞれのオブジェクトは対応するオブジェクト識別子を有し、それぞれのサブバケットは複数のオブジェクトに関する関連したデータを含み、それぞれのサブバケットは前記複数のオブジェクトのそれぞれに関する前記オブジェクト識別子の導関数（デリバティブ）を含むことを特徴とする方法。
【請求項２３】
キャッシュラインサイズを有するキャッシュラインを有するキャッシュを備えたプロセッサを含むコンピュータシステムのメモリに記憶されているオブジェクトに対する所定の数のメモリアドレスを含むエントリを有するオブジェクトハンドルテーブルを用いる方法であって、前記オブジェクトハンドルテーブルのそれぞれエントリは前記キャッシュラインサイズである、方法において、
前記所定の数のオブジェクトに対するメモリアドレスを、前記オブジェクトハンドルテーブルの中の１つのエントリに記憶するステップと、
前記エントリの中の１つにアクセスし、正確な適合によって前記キャッシュラインの中の１つの中に前記エントリがロードされるメモリアドレスを取得するステップと、
を含むことを特徴とする方法。
【請求項２４】
請求項２３記載の方法において、メモリアドレスを記憶するステップは、
前記オブジェクトを、それぞれのグループの中のオブジェクトが機能的に関連している複数のグループにグループ分けするステップと、
前記所定の数の機能的に関連するオブジェクトに対するメモリアドレスを前記１つのエントリに記憶するステップと、
を含むことを特徴とする方法。
【請求項２５】
請求項２４記載の方法において、前記オブジェクトをグループ分けするステップは、
識別子を、当該識別子の一部が機能的に関連するオブジェクトのそれぞれのグループでは同じであるように、前記オブジェクトに割り当てるステップと、
前記識別子の前記一部に基づいて、前記オブジェクトをグループ分けするステップと、
を含むことを特徴とする方法。
【請求項２６】
請求項２５記載の方法において、メモリアドレスを記憶するステップは、前記識別子の前記一部の１つのコピーを前記１つのエントリに記憶するステップを含むことを特徴とする方法。
【請求項２７】
コンピュータシステムであって、
キャッシュラインサイズを有するキャッシュラインを備えたキャッシュと、
オブジェクトと、前記オブジェクトに対する複数のメモリアドレスを含むエントリを有するオブジェクトハンドルテーブルと、前記オブジェクトハンドルテーブルにアクセスすることによって前記オブジェクトのメモリアドレスを取得するオブジェクトローダと、を有するメモリと、
前記オブジェクトローダを動作させ、要求されたオブジェクトに対するメモリアドレスを取得し、前記要求されたオブジェクトに対するメモリアドレスを含むエントリを、正確に適合するように前記キャッシュラインの中の１つにロードするプロセッサと、
を備えていることを特徴とするコンピュータシステム。
【請求項２８】
ネットワークを介してリモートコンピュータに接続されたコンピュータシステムであって、
メモリであって、
メモリアドレスに配置された複数のオブジェクトと、
ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子にマップするマッピングテーブルと、
前記オブジェクトのメモリアドレスを記憶するフィールドを備えたオブジェクトハンドルテーブルと、
このメモリの中のそれぞれのオブジェクトに対するエントリを含むバケットを備えたハッシュテーブルであって、それぞれのエントリは、前記オブジェクトに対するメモリアドレスを含むオブジェクトハンドルテーブルの中のフィールドへの参照を含む、ハッシュテーブルと、
オブジェクトローダであって、要求されたオブジェクトのネットワーク・ワイド・オブジェクト識別子を受信し、前記マッピングテーブルを用いることにより前記ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子に変換し、前記システム・ワイド・オブジェクト識別子をハッシュ関数に入力して前記バケットの中の１つを参照するインデックスを生成し、前記参照されたバケットにアクセスして前記要求されたオブジェクトに対するエントリを確認し、前記確認されたエントリにアクセスして前記要求されたオブジェクトに対する前記オブジェクトハンドルテーブルの中のフィールドへの参照を取得し、前記オブジェクトハンドルテーブルの中の前記参照されたフィールドにアクセスして前記要求されたオブジェクトに対するメモリアドレスを取得し、前記要求されたオブジェクトのメモリアドレスを返す、オブジェクトローダと、
を含むメモリと、
前記オブジェクトローダを動作させるプロセッサと、
を備えていることを特徴とするコンピュータシステム。
【請求項２９】
請求項２８記載のコンピュータシステムにおいて、キャッシュラインサイズを備えたキャッシュラインを有するキャッシュを更に含み、前記ハッシュテーブルのバケットは前記キャッシュラインサイズであることを特徴とするコンピュータシステム。
【請求項３０】
請求項２９記載の方法において、前記キャッシュは前記プロセッサの一部であることを特徴とするコンピュータシステム。
【請求項３１】
請求項２８記載の方法において、キャッシュラインサイズを備えたキャッシュラインを有するキャッシュを更に含み、前記オブジェクトハンドルテーブルは所定の数のフィールドを含むエントリを有し、前記オブジェクトハンドルテーブルの中のエントリは前記キャッシュラインサイズであることを特徴とするコンピュータシステム。
【請求項３２】
請求項３１記載の方法において、前記キャッシュは前記プロセッサの一部であることを特徴とするコンピュータシステム。
【請求項３３】
請求項２８記載のコンピュータシステムにおいて、それぞれバケットは、機能的に関連しているオブジェクトに関するエントリを含むことを特徴とするコンピュータシステム。
【請求項３４】
請求項２８記載のコンピュータシステムにおいて、それぞれのバケットは、一時的に関連するオブジェクトに関するエントリを含むことを特徴とするコンピュータシステム。
【請求項３５】
請求項２８記載のコンピュータシステムにおいて、前記オブジェクトハンドルテーブルはエントリを有し、それぞれのエントリは、機能的に関連するオブジェクトに対するメモリアドレスを備えた所定の数のフィールドを含むことを特徴とするコンピュータシステム。
【請求項３６】
オブジェクトに対するオブジェクト識別子と前記オブジェクトに対するオブジェクトハンドルテーブルの中のフィールドへの参照とを含むエントリをそれぞれのバケットが有する複数のバケットを備えたハッシュテーブルを有するコンピュータシステムのメモリにおけるメモリアドレスに配置されたオブジェクトにアクセスする方法であって、前記オブジェクトハンドルテーブルの中のフィールドは前記オブジェクトのメモリアドレスを含む、方法において、
メモリアドレスが要求されている要求されたオブジェクトの識別子を受信するステップと、
前記識別子をハッシュ関数の中に入力して、前記ハッシュテーブルの中の前記バケットの中の１つを参照するインデックスを生成するステップと、
前記インデックスを用いて前記バケットにアクセスするステップと、
前記要求されたオブジェクトの識別子に対してそれぞれのエントリの識別子を照合することによって、前記要求されたオブジェクトのエントリに関するバケットをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスして、前記要求されたオブジェクトに対する前記オブジェクトハンドルテーブルの中のフィールドへの参照を取得するステップと、
前記参照を用いて、前記要求されたオブジェクトのメモリアドレスを含むオブジェクトハンドルテーブルの中の前記フィールドにアクセスするステップと、
前記要求されたオブジェクトのメモリアドレスを返すステップと、
を含むことを特徴とする方法。
【請求項３７】
ネットワークを介してリモートコンピュータシステムに接続されたコンピュータシステムのメモリの中のメモリアドレスに配置されたオブジェクトにアクセスする方法であって、前記コンピュータシステムは、複数のバケットを備えたハッシュテーブルを有し、それぞれのバケットは、オブジェクトに対するオブジェクト識別子と前記オブジェクトに対するメモリアドレスを取得するのに十分な情報とを含むエントリとを含む、方法において、
要求されたオブジェクトのメモリアドレスに対する要求をコーラから受信するステップであって、前記要求は、前記要求されたオブジェクトのネットワーク・ワイドに一意的な識別子を含む、ステップと、
前記ネットワーク・ワイドに一意的な識別子をシステム・ワイドに一意的な識別子に圧縮するステップと、
前記システム・ワイドに一意的な識別子をハッシュ関数に入力して、前記ハッシュテーブルの中の前記バケットの中の１つを参照するインデックスを生成するステップと、
前記インデックスを用いて前記バケットにアクセスするステップと、
それぞれのエントリの中のオブジェクト識別子を前記システム・ワイドに一意的な識別子と照合することによって、前記要求されたオブジェクトのエントリに関するバケットをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスして、前記要求されたオブジェクトのメモリアドレスを取得するのに十分な情報にアクセスするステップと、
前記十分な情報を用いることによって、前記要求されたオブジェクトのメモリアドレスをコーラに返すステップと、
を含むことを特徴とする方法。
【請求項３８】
コンピュータシステムを制御してメモリの中のメモリアドレスに配置されたオブジェクトにアクセスする命令を含むコンピュータ可読な記憶媒体であって、前記コンピュータシステムはバケットの複数のチェーンを有するハッシュテーブルを備えており、それぞれのバケットは、オブジェクトに関する識別子を含むエントリと、前記オブジェクトに関するオブジェクトハンドルテーブルのフィールドに対する参照とを有し、前記オブジェクトハンドルテーブルにおけるフィールドは前記オブジェクトのメモリアドレスを含む、コンピュータ可読な記憶媒体であって、
要求されたオブジェクトのメモリアドレスに関するコーラから、前記要求されたオブジェクトのネットワーク・ワイド・オブジェクト識別子を含む要求を受信するステップと、
前記ネットワーク・ワイド・オブジェクト識別子をシステム・ワイド・オブジェクト識別子に変換するステップと、
前記システム・ワイド・オブジェクト識別子をハッシュ関数に入力し、前記ハッシュテーブルにおける前記バケットの複数のチェーンの中の１つを参照するインデックスを生成するステップと、
インデックスを用いて前記バケットチェーンにアクセスするステップと、
前記要求されたオブジェクトの前記システム・ワイド・オブジェクト識別子に対して、それぞれのエントリの識別子を照合することによって、前記要求されたオブジェクトのエントリに関するバケットチェーンをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスし、前記オブジェクトハンドルテーブルの中への参照を得るステップと、
前記参照を用いて前記オブジェクトハンドルテーブルにアクセスし、要求されたオブジェクトのメモリアドレスを含むフィールドを識別するステップと、
前記識別されたフィールドに含まれる要求されたオブジェクトのメモリアドレスを前記コーラに返すステップと、
によってアクセスを実現することを特徴とするコンピュータ可読な記憶媒体。
【請求項３９】
コンピュータシステムを制御して、バケットを有するハッシュテーブルにデータを記憶する命令を含むコンピュータ可読な記憶媒体であって、前記コンピュータシステムはオブジェクトを有し、それぞれのオブジェクトは関連するデータと識別子とを有するオブジェクトを有し、前記識別子の一部は機能的に関連するオブジェクトでは等しい、コンピュータ可読な記憶媒体において、前記記憶は、
前記ハッシュテーブルの中のバケットを参照するインデックスを生成するハッシュ関数を、前記ハッシュ関数が機能的に関連するオブジェクトについては同じインデックスを生成するように選択するステップと、
前記ハッシュ関数を用いて、前記関連するデータを前記ハッシュテーブルの中に挿入するステップであって、前記関連するデータは、機能的に関連する場合には、同じバケットに記憶される、ステップと、
によってなされることを特徴とするコンピュータ可読な記憶媒体。
【請求項４０】
コンピュータシステムを制御して、バケットを有するハッシュテーブルにデータを記憶する命令を含むコンピュータ可読な記憶媒体であって、前記コンピュータシステムはオブジェクトを有し、それぞれのオブジェクトは関連するデータを有するオブジェクトを有している、コンピュータ可読な記憶媒体において、前記記憶は、
それぞれが機能的に関連するオブジェクトを含む複数のグループに前記オブジェクトをグループ分けするステップと、
それぞれのグループに関する前記関連するデータを前記ハッシュテーブルに記憶するステップであって、それぞれのグループの機能的に関連するオブジェクトに関する前記関連するデータは同じバケットに記憶される、ステップと、
によってなされることを特徴とするコンピュータ可読な記憶媒体。
【請求項４１】
請求項４０記載のコンピュータ可読な記憶媒体において、
前記オブジェクトをグループ分けするステップは、前記オブジェクトに識別子を割り当てて、前記識別子の一部が１つのグループの中のそれぞれの機能的に関連するオブジェクトに関して等しくなるようにするステップと、前記オブジェクトを前記識別子の前記一部に基づいてグループ分けするステップとを含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項４２】
請求項４０記載のコンピュータ可読な記憶媒体において、
前記複数のグループの前記機能的に関連するオブジェクトには等しいインデックスが生成されるようにインデックスを前記バケットの中に生成することによって、衝突を生じさせるハッシュ関数を選択するステップを含み、
それぞれのグループからの前記関連するデータを記憶するステップは、それぞれのオブジェクトに関し、
前記ハッシュ関数を呼び出し、指定されたバケットを参照するインデックスを生成するステップと、
前記オブジェクトに関する関連するデータを前記指定されたバケットの中に記憶するステップと、
を含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項４３】
請求項４０記載のコンピュータ可読な記憶媒体において、前記コンピュータシステムはキャッシュラインサイズを有するキャッシュラインを備えたキャッシュを有し、前記バケットはキャッシュラインサイズであることを特徴とするコンピュータ可読な記憶媒体。
【請求項４４】
請求項４０記載のコンピュータ可読な記憶媒体において、それぞれのバケットはサブバケットのチェーンであることを特徴とするコンピュータ可読な記憶媒体。
【請求項４５】
請求項４４記載のコンピュータ可読な記憶媒体において、それぞれのバケットは複数のオブジェクトに関する関連したデータを含み、それぞれのサブバケットは前記複数のオブジェクトのそれぞれに関する識別子を含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項４６】
請求項４４記載のコンピュータ可読な記憶媒体において、前記コンピュータシステムの中のそれぞれのオブジェクトは対応するオブジェクト識別子を有し、それぞれのサブバケットは複数のオブジェクトに関する関連したデータを含み、それぞれのサブバケットは前記複数のオブジェクトのそれぞれに関する前記オブジェクト識別子の導関数（デリバティブ）を含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項４７】
コンピュータシステムを制御して、メモリの中に記憶されているオブジェクトに対する所定の数のメモリアドレスを含むエントリを有するオブジェクトハンドルテーブルを用いる命令を含むコンピュータ可読な記憶媒体であって、前記コンピュータシステムは、キャッシュラインサイズを有するキャッシュラインを有するキャッシュを備えたプロセッサを有し、前記オブジェクトハンドルテーブルのそれぞれエントリは前記キャッシュラインサイズである、コンピュータ可読な記憶媒体において、前記用いる動作は、
前記所定の数のオブジェクトに対するメモリアドレスを、前記オブジェクトハンドルテーブルの中の１つのエントリに記憶するステップと、
前記エントリの中の１つにアクセスし、正確な適合によって前記キャッシュラインの中の１つの中に前記エントリがロードされるメモリアドレスを取得するステップと、
によって実行されることを特徴とするコンピュータ可読な記憶媒体。
【請求項４８】
請求項４７記載のコンピュータ可読な記憶媒体において、メモリアドレスを記憶するステップは、
前記オブジェクトを、それぞれのグループの中のオブジェクトが機能的に関連している複数のグループにグループ分けするステップと、
前記所定の数の機能的に関連するオブジェクトに対するメモリアドレスを前記１つのエントリに記憶するステップと、
を含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項４９】
請求項４８記載のコンピュータ可読な記憶媒体において、前記オブジェクトをグループ分けするステップは、
識別子を、当該識別子の一部が機能的に関連するオブジェクトのそれぞれのグループでは同じであるように、前記オブジェクトに割り当てるステップと、
前記識別子の前記一部に基づいて、前記オブジェクトをグループ分けするステップと、
を含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項５０】
請求項４９記載のコンピュータ可読な記憶媒体において、メモリアドレスを記憶するステップは、前記識別子の前記一部の１つのコピーを前記１つのエントリに記憶するステップを含むことを特徴とするコンピュータ可読な記憶媒体。
【請求項５１】
コンピュータシステムを制御して、オブジェクトに対するオブジェクト識別子と前記オブジェクトに対するオブジェクトハンドルテーブルの中のフィールドへの参照とを含むエントリをそれぞれのバケットが有する複数のバケットを備えたハッシュテーブルを有するコンピュータシステムのメモリにおけるメモリアドレスに配置されたオブジェクトにアクセスする命令を含むコンピュータ可読な記憶媒体であって、前記オブジェクトハンドルテーブルの中のフィールドは前記オブジェクトのメモリアドレスを含む、コンピュータ可読な記憶媒体において、前記アクセスする動作は、
メモリアドレスが要求されている要求されたオブジェクトの識別子を受信するステップと、
前記識別子をハッシュ関数の中に入力して、前記ハッシュテーブルの中の前記バケットの中の１つを参照するインデックスを生成するステップと、
前記インデックスを用いて前記バケットにアクセスするステップと、
前記要求されたオブジェクトの識別子に対してそれぞれのエントリの識別子を照合することによって、前記要求されたオブジェクトのエントリに関するバケットをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスして、前記要求されたオブジェクトに対する前記オブジェクトハンドルテーブルの中のフィールドへの参照を取得するステップと、
前記参照を用いて、前記要求されたオブジェクトのメモリアドレスを含むオブジェクトハンドルテーブルの中の前記フィールドにアクセスするステップと、
前記要求されたオブジェクトのメモリアドレスを返すステップと、
によって実行されることを特徴とするコンピュータ可読な記憶媒体。
【請求項５２】
コンピュータシステムを制御して、ネットワークを介してリモートコンピュータシステムに接続されたコンピュータシステムのメモリの中のメモリアドレスに配置されたオブジェクトにアクセスする命令を含むコンピュータ可読な記憶媒体であって、前記コンピュータシステムは、複数のバケットを備えたハッシュテーブルを有し、それぞれのバケットは、オブジェクトに対するオブジェクト識別子と前記オブジェクトに対するメモリアドレスを取得するのに十分な情報とを含むエントリとを含む、コンピュータ可読な記憶媒体において、前記アクセスする動作は、
要求されたオブジェクトのメモリアドレスに対する要求をコーラから受信するステップであって、前記要求は、前記要求されたオブジェクトのネットワーク・ワイドに一意的な識別子を含む、ステップと、
前記ネットワーク・ワイドに一意的な識別子をシステム・ワイドに一意的な識別子に圧縮するステップと、
前記システム・ワイドに一意的な識別子をハッシュ関数に入力して、前記ハッシュテーブルの中の前記バケットの中の１つを参照するインデックスを生成するステップと、
前記インデックスを用いて前記バケットにアクセスするステップと、
それぞれのエントリの中のオブジェクト識別子を前記システム・ワイドに一意的な識別子と照合することによって、前記要求されたオブジェクトのエントリに関するバケットをサーチするステップと、
前記要求されたオブジェクトのエントリにアクセスして、前記要求されたオブジェクトのメモリアドレスを取得するのに十分な情報にアクセスするステップと、
前記十分な情報を用いることによって、前記要求されたオブジェクトのメモリアドレスをコーラに返すステップと、
によって実行されることを特徴とするコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【従来の技術】
【０００１】
この発明は一般的に、データ処理システムに関し、特に、キャッシュ効率的なオブジェクトローダに関する。
プロセッサがより高速になってきているので、メインメモリアクセスは、増加する性能全体にわたってボトルネックとなっている。従って、性能を改善するために、メモリキャッシュスキームが、メインメモリボトルネックの影響を減少させるために採用されてきた。ＰＥＮＴＩＵＭプロセッサは、非常に高速な１次キャッシュと高速２次キャッシュを使用する、かかるメモリキャッシュスキームを採用する。プロセッサがメモリからデータを読み取る必要があるとき、プロセッサは最初に、データを位置決めするために１次キャッシュをチェックする。データが１次キャッシュに配置されるならば、該データはプロセッサに戻される。要求されたデータが１次キャッシュに見つからないとき、次いで、２次キャッシュがチェックされるが、該２次キャッシュは、１次キャッシュよりも遅いアクセス時間を有するが、メインメモリよりもまだ高速である。データが２次キャッシュに配置されているならば、データはプロセッサに戻され、データがストアされた２次キャッシュのライン（「キャッシュライン」）が、１次キャッシュにコピーされる。即ち、１次キャッシュの読み出しがされているデータを単にコピーするだけでなく、全体３２バイトキャッシュラインが１次キャッシュにコピーされる。１次キャッシュは、サイズが８ＫＢであるので、２５６キャッシュラインをストアすることができる。２次キャッシュは、典型的には２５６ＫＢ乃至５１２ＫＢであるので、８１９２と１６３８４キャッシュラインの間をストアすることができる。
【０００２】
２次キャッシュをチェックした後、データが依然として見つからないならば、２次キャッシュより著しく遅いキャッシュ時間を有するメインメモリが、アクセスされる。メインメモリがアクセスされるとき、要求されたデータだけでなく、３２バイトの全体メモリラインも戻される。３２バイトを戻すとき、プロセッサは要求されたデータを受け取り、１次及び２次キャッシュの双方は、キャッシュラインとしても知られている、全体３２バイトメモリラインを受け取る。３２バイトメモリラインは、次回、プロセッサがデータをメモリから読み出す必要があることを希望して、１次キャッシュにストアされ、該データは、メインメモリアクセスを避けて、このキャッシュライン内で見つけられ、著しく処理時間を省くであろう。将来におけるコストを見積もるために、１次キャッシュへアクセスするために１プロセッササイクルを要し、２次キャッシュへアクセスするために４乃至１２プロセッサを要し、メインメモリへアクセスするために典型的には５０プロセッササイクルを要する。従って、１次キャッシュは、メインメモリに一度アクセスするのに要する時間で、おそらく５０回サーチされることができる。ＰＥＮＴＩＵＭプロセッサのキャッシュスキームは、Ａｎｄｅｒｓｏｎ、及び、Ｓｈａｎｌｅｙ著、「ＰｅｎｔｉｕｍＰｒｏｃｅｓｓｏｒ Ｓｙｓｔｅｍ Ａｒｃｈｉｔｅｃｔｕｒｅ」、第２版、３５乃至６０頁、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ（１９９５年) により詳細に説明されており、参照によりここに組み込まれる。
【０００３】
オブジェクトを使用するためにアプリケーションプログラムの要求に関してオブジェクトをメモリ内にロードするオブジェクトローダが開発されてきた。オブジェクトの一例は、スプレッドシートプログラムからのスプレッドシートセルの範囲のような、データの一部分である。在来のいくつかのシステムでは、アプリケーションプログラムがオブジェクトを使用したいとき、それはオブジェクトの識別子を有するが、それは、オブジェクトが利用され得る前に、オブジェクトのメモリアドレスを得なければならない。この状況では、オブジェクトローダはメモリアドレスを得るのに利用されている。しかしながら、オブジェクトがまだメモリ内にロードされていないならば、オブジェクトローダは２次記憶装置からのオブジェクトを配置し、オブジェクトをメモリ内にストアし、メモリアドレスを戻す。
【０００４】
幾つかの在来のオブジェクトローダは、それらの機能を実行する際に役立つ在来のハッシュ機構を使用する。在来のハッシュ機構は、直接的なアクセスをストアされたデータに対して行うためのハッシュテーブルとして知られる、データ構造を利用する。在来のハッシュ機構１００の一例を図１に示す。ハッシュ機構１００は、キー１０２、ハッシュ関数１０４、ハッシュインデックス１０６、及び、ハッシュテーブル１０８を含む。ハッシュテーブル１０８は、多数のハッシュバケット１１０乃至１３０を含み、かかるハッシュバケットは、キー１０２として作用するレコードのフィールドのうちの１つを備えた、レコードのようなデータを含む。ハッシュテーブル１０８へアクセスするために、キー１０２は、特定のハッシュバケット（例えば、１１４）と称する、インデックス１０６（又はハッシュアドレス）を生ずるハッシュ関数１０４に入力される。ハッシュバケット１１４内に、キーを照合するデータがある。ハッシュテーブルが、インデックスの小さな範囲内に、キー値の大きな範囲をマッピングすることにより、データへの直接アクセスを提供するので、ハッシュテーブルは有用である。この方法では、例えば、０乃至９９９９９９９９のキー値の範囲を有する８桁のキーが利用でき、１０値以下が引き続き使用されるならば、ハッシュ機構は、１０バケットを包含するハッシュテーブルと称する、１桁のインデックスにキーをハッシュするのに使用することができる。従って、バケットの非常に制限された数だけが引き続き使用されている、100,000,000 ハッシュバケットを有するハッシュテーブルの使用の代わりに、１０バケットだけのハッシュテーブルを、システムリソースをより有効に使用するのに用いることができるが、データへの直接アクセスを依然として行う。
【０００５】
関数「ｈ」１０４は、各キー値を正確に１インデックスにマップし、従って、同じキー値が一度以上使用されたときはいつでも、ハッシュテーブル１０８への同じインデックス１０６が生成される。しかしながら、ときどき、データをハッシュテーブル１０８にストアしようとするとき、１キー値より大きなものが、同じインデックス１０６にハッシュされ得る。この状況では、「衝突」が発生している。衝突が生じるとき、データは、インデックスによって示されたハッシュバケットにストアされる必要があり、従って、１レコードより大きなものが、このハッシュバケットにストアされ得る。ハッシュバケット１１８は、衝突が生じ、１レコードより大きなものがハッシュバケットにストアされた後の、ハッシュバケットの状態を示す。ハッシュバケット１１８では、データ「データ３」の１レードが、データ「データ４」の第２のレコードにリンクされている。更なる衝突が生じたとき、ハッシュバケットはより占領された状態になり、従って、ハッシュバケット内の各レコードがもはや直接アクセスできないので、ハッシュテーブルの利益は小さくなりはじめる。その代わりに、キー値をインデックス内にハッシュした後、インデックスは、互いにリンクした多数のレコードを包含するハッシュバケットを参照し、ハッシュバケットは、次いで、処理時間に関してコストがかかる、正しいレコードを求めるためにサーチされなければならない。従って、在来のハッシュシステムは、衝突を回避するために設計されている。
【０００６】
在来のオブジェクトローダは、キー１０２としてオブジェクト識別子の使用によって、且つ、オブジェクトのメモリアドレスと、ハッシュテーブル１０８のハッシュバケット１１０乃至１３０のデータとしてのオブジェクト識別子との双方をストアすることによって、在来のハッシュ機構１００を利用する。かかるように、アプリケーションプログラムからの所定のオブジェクトのオブジェクト識別子を受信する際、在来のオブジェクトローダは、ハッシュテーブル１０８のハッシュバケットを参照するインデックス１０６を生成するために、ハッシュ関数１０４をオブジェクト識別子に適用することによって、且つ、ハッシュバケットからのオブジェクトに関するメモリアドレスを検索することによって、オブジェクトのメモリアドレスを検索する。オブジェクトに関するメモリアドレスが、ハッシュテーブルに既に含まれていないならば、オブジェクトローダは、２次記憶装置からオブジェクトを配置し、オブジェクトをメモリ内にストアし、メモリアドレスをハッシュテーブルにストアし、メモリアドレスを戻す。
【０００７】
在来のオブジェクトローダの処理は、オブジェクトを配置し、それらをメモリ内にロードさせるために、著しい量の処理時間を要する可能性があった。この処理は、システム内で利用されるオブジェクトの数が非常に大きくなるにつれて、システムにとって、更に非常に重荷となる。更に、著しい量の処理時間とメモリが、オブジェクトをメモリ内にロードした後でさえ、オブジェクトを配置するのに使用されていた。従って、オブジェクトローダの性能を改善するのが望ましい。しかしながら、在来のオブジェクトローダは、性能を改善するために、今日のプロセッサのキャッシュアーキテクチャを利用していない。
【発明の開示】
【０００８】
性能を改善するために今日の多くのプロセッサのキャッシュアーキテクチャの利点を得る改善されたオブジェクトローダを提供する。ＰＥＮＴＩＵＭプロセッサのような今日の最新のプロセッサの幾らかは、１次キャッシュと２次キャッシュを利用する２レベルキャッシュスキームを有し、１次キャッシュに包含されたデータは、メインメモリのデータよりも５０乃至１５０倍速くアクセスされ得る。改善されたオブジェクトローダは、オブジェクトをロードするために、ハッシュテーブルとオブジェクトハンドルテーブルとを使用し、これらのテーブルの各々は、システム性能を向上させるために、プロセッサのキャッシュアーキテクチャを十分に利用するような方法で設計され、利用される。
【０００９】
改善されたオブジェクトローダシステムのハッシュテーブルでは、ハッシュバケットは実際には、バケットのチェーンであり、オブジェクト情報は、バケットのチェーンにストアされる。改良されたオブジェクトローダは、オブジェクト情報をハッシュテーブルに挿入するとき、衝突が、機能的に関連するオブジェクトに関係する情報がバケットの同じチェーンにストアされるように故意に生じるように設計される。ハッシュテーブルのバケットは、キャッシュラインと同じサイズ（例えば、３２バイト）となるように構成される。その結果、正常な発生であるプログラムが、関連するオブジェクトにアクセスするためにオブジェクトローダを使用するとき、特に、同じバケットに包含されたオブジェクト情報が最近アクセスされているならば、関連するオブジェクトに関するオブジェクト情報を包含するバケットが既に１次キャッシュにロードされているので性能節減がある。この方法では、１次キャッシュヒットは増加し、メインメモリアクセスは減少する。更に、改善されたオブジェクトローダは、概してオブジェクトローダ、特に、オブジェクトハンドルテーブルのメモリ要求を減少させるために、システム内のオブジェクトの識別子を圧縮する。
【００１０】
オブジェクトハンドルテーブルは、プロセッサのキャッシュアーキテクチャを利用するようにハッシュテーブルに同様に構成される。即ち、機能的に関連するオブジェクトのグループに関する（メモリアドレスを含む）情報は、オブジェクトハンドルテーブルの各エントリにストアされ、各エントリは、キャッシュラインと同じサイズであるように設計される。従って、関連するオブジェクトがアクセスされるに連れて、１次キャッシュヒットは増加し、１次キャッシュミスは減少する。オブジェクトの識別子が圧縮されるので、オブジェクトハンドルテーブルは、１つのエントリ内に、適合するよりも多くのオブジェクトに関する情報をストアすることができる。更に、オブジェクトハンドルテーブルのエントリ内のオブジェクトに関する情報は圧縮され、また、１つのエントリ内に適合され得るよりも多くのオブジェクトに関する情報をストアすることに至る。
【００１１】
本発明の第１の態様によれば、バケットを有するハッシュテーブル内へのオブジェクトに関するデータをストアするためのコンピュータシステムにおける方法を提供する。かかる方法は、オブジェクトを、機能的に関連するオブジェクトのグループにグループ化し、書くグループの機能的に関連するオブジェクトが同じバケットにストアされるように、各グループからのデータをハッシュバケット内にストアする。本発明の第２の態様によれば、コンピュータシステムのメモリ内にストアされたオブジェクトに関するメモリアドレスの所定の数を包含するエントリを有するオブジェクトハンドルテーブルを生成するためのコンピュータシステムにおける方法を提供する。かかる方法は、オブジェクトを機能的に関連するオブジェクトのグループにグループ化し、機能的に関連するオブジェクトの所定の数に関するメモリアドレスをオブジェクトハンドルテーブルの単一のエントリにストア（記憶）する。
【００１２】
本発明の第３の態様によれば、複数のバケットを備えるハッシュテーブルを有するコンピュータシステムのメモリのメモリアドレスに配置されたオブジェクトにアクセスする方法を提供する。各バケットは、オブジェクトに関するオブジェクト識別子と、オブジェクトに関するオブジェクトハンドルテーブルのフィールドへのリファレンス（参照）とを含むエントリを有する。オブジェクトハンドルテーブルのフィールドは、オブジェクトに関するメモリアドレスを含む。かかる方法は、メモリアドレスが要求される要求されたオブジェクトの識別子を受信し、ハッシュテーブルのバケットのうちの１つを参照するインデックスを生成するために、識別子をハッシュ関数に入力し、インデックスを使用してバケットにアクセスする。かかる方法は更に、要求されたオブジェクトの識別子に対して、各エントリの識別子を照合することによって、要求されたオブジェクトのエントリに関するバケットをサーチし、要求されたオブジェクトに関するオブジェクトハンドルテーブルのフィールドへのリファレンスを得るために、要求されたオブジェクトのエントリにアクセスする。かかる方法はまた、要求されたアドレスのメモリアドレスを含むフィールドにアクセスするためのリファレンスを使用してオブジェクトハンドルテーブルへアクセスし、要求されたオブジェクトのメモリアドレスを返す。
【００１３】
本発明の第４の態様によれば、リモートコンピュータに接続されたネットワークに接続されたコンピュータシステムのメモリにおけるメモリアドレスに配置されたオブジェクトへのアクセスする方法を提供する。かかるコンピュータシステムは、オブジェクトと、オブジェクトに関するメモリアドレスストレージ情報とに関するオブジェクト識別子を含むエントリを各々持った複数のバケットを備えるハッシュテーブルを有する。かかる方法は、要求が、要求されたオブジェクトに関するネットワーク・ワイド・一意性識別子を含む、要求されたオブジェクトのメモリアドレスに関するコーラから要求を受信する。かかる方法は、ネットワーク・ワイド・一意性識別子をシステム・ワイド・一意性識別子に圧縮し、ハッシュテーブルのバケットのうちの１つを参照するインデックスを生成するために、システム・ワイド・一意性識別子をハッシュ関数に入力し、インデックスを使用してバケットにアクセスする。かかる方法は更に、システム・ワイド・一意性識別子に対して、各エントリにおけるオブジェクト識別子を照合することによって、要求されたオブジェクトのエントリに関するバケットをサーチし、メモリアドレスストレージ情報を得るために、要求されたオブジェクトのエントリにアクセスし、要求されたオブジェクトのメモリアドレスを配置するために、メモリアドレスストレージ情報を利用し、要求されたオブジェクトのメモリアドレスをコーラに返す。
【発明の実施の形態】
【００１４】
本発明の好ましい実施形態は、性能を改善するために、今日のプロセッサの多くのキャッシュアーキテクチャを利用して設計されているか依然されたオブジェクトローダを提供する。ＰＥＮＴＩＵＭプロセッサのような今日の最新のプロセッサのいくつかは、１次キャッシュと２次キャッシュとを利用する２レベルキャッシュスキームを有し、１次キャッシュに包含されたデータは、メインメモリのデータより５０乃至１５０倍速くアクセスすることができる。改善されたオブジェクトローダは、ハッシュテーブルと、オブジェクトをロードするためのオブジェクトハンドルテーブルとを使用する。これらのテーブルの各々は、システム性能を向上させるために、プロセッサのキャッシュアーキテクチャを十分に利用するような仕方で、設計され且つ利用されている。
【００１５】
改善されたオブジェクトローダシステムのハッシュテーブルでは、ハッシュバケットは実際にバケットのチェーンであり、オブジェクト情報はバケットのチェーンにストアされる。改善されたオブジェクトローダは、オブジェクト情報をハッシュテーブルに挿入したとき、機能的に関連したオブジェクトに関係する情報がバケットの同じチェーンにストアされるように、衝突が故意に生じるように設計されている。ハッシュテーブルのバケットがハッシュラインと同じサイズ（例えば、３２バイト）に構成されている。その結果、プログラムが、通常の発生である関連したオブジェクトにアクセスするためにオブジェクトローダを使用するとき、関連したオブジェクトに関するオブジェクト情報を包含するバケットが既に１次キャッシュ内にロードされているので、特に、同じバケットに包含されたオブジェクト情報が、最近アクセスされているならば、性能が減ぜられる。この方法では、１次キャッシュヒットは増加し、メインメモリアクセスは減少する。更に、改善されたオブジェクトローダは、概してオブジェクトローダ、特に、オブジェクトハンドルテーブルのメモリ要求を減らすためにシステムのオブジェクトの識別子を圧縮する。
【００１６】
オブジェクトハンドルテーブルは、プロセッサのキャッシュアーキテクチャを利用するように、ハッシュテーブルに同様に構成されている。即ち、機能的に関連したオブジェクトのグループに関する（メモリアドレスを含む）情報は、オブジェクトハンドルテーブルの各エントリにストアされ、各エントリはキャッシュラインと同じサイズに設計される。従って、関連するオブジェクトがアクセスされるにつれて、１次キャッシュヒットは増加し、１次キャッシュミスが減少する。オブジェクトの識別子が圧縮されるので、オブジェクトハンドルテーブルは、照合し得るよりも多い、あるエントリへのオブジェクトの情報をストアすることができる。更に、オブジェクトハンドルテーブルのエントリのオブジェクトに関する情報は圧縮され、照合し得るよりも多い、あるエントリへのオブジェクトに関する情報をストアすることにもなる。
【００１７】
概観アプリケーションプログラムが、データベースオブジェクトのようなオブジェクトにアクセスしたいとき、アプリケーションプログラムは典型的には、オブジェクトの識別子を有するが、そのメモリアドレスは有しない。しかし、オブジェクトを利用する前に、アプリケーションプログラムはオブジェクトのメモリアドレスを得る必要がある。以前に述べたように、オブジェクトに関するメモリアドレスを得ることと、アプリケーションプログラムがオブジェクトを利用するようにメモリアドレスをアプリケーションプログラムにパスすることは、オブジェクトローダの責任である。この機能を実行する際に、オブジェクトローダは、オブジェクトがまだメモリ内にロードされていないことを判断し得る。この状況では、オブジェクトローダは、オブジェクトをメモリ内にロードする必要がある。好ましい実施形態では、各オブジェクトは、ネットワークの他の全てのコンピュータの他の全てのオブジェクトからのあるオブジェクトを区別する一意性識別子である、連想グローバル一意性識別子（ＧＵＩＤ）を有する。ＧＵＩＤは１６バイト識別子である。図２に示すように、改善されたオブジェクトローダ２００は、アプリケーションプログラム２０４からＧＵＩＤ２０２を受信し、ＧＵＩＤを受信した後、改善されたオブジェクトローダは、マッピングテーブル２０８を使用することによって、オブジェクト識別子（ＯＩＤ）２０６として知られている、８バイト識別子にＧＵＩＤを変換する。ＧＵＩＤをＯＩＤに変換することによって、オブジェクトローダ２００内でオブジェクトを参照するのに使用されるスペースの量と、並びに、以下で議論する、オブジェクトハンドルテーブル２０８のエントリをストアするために必要なスペースの量を最小にする。ＧＵＩＤ２０２をＯＩＤ２０６に変換する際に、改良されたオブジェクトローダ２００は、オブジェクトのメモリアドレスを得るために、ＯＩＤをハッシュ機構２０７に入力する。
【００１８】
ハッシュ機構２０７を利用する際に、改良されたオブジェクトローダ２００は、ハッシュ関数２１０を使用するＯＩＤ２０６を、ハッシュテーブル２１４におけるバケット２１２の特定のチェーンを指示する２４ビットインデックスにハッシュする。従って、ハッシュテーブル２１４のサイズは、２24バックチェーンまで含む。ハッシュテーブル２１４がより少数のバックチェーンを最初に含んでいてよく、時間をかけて、２24バックチェーンまで含むように大きくすることができることは、当業者には明らかであろう。アプリケーションプログラムが、互いに関連したオブジェクトのグループを使用することは認められているので、各バケットチェーンは、機能的に関連するオブジェクトに関する情報（「オブジェクトエントリ」）をストアする。ＧＵＩＤがオブジェクトに割り当てられ、ハッシュ関数の設計のため、機能的に関連するオブジェクトに関するオブジェクトのエントリが同じバケットチェーンにストアされることを保証する。ＧＵＩＤは、機能的に関連するオブジェクトがそれらのＧＵＩＤの等価な部分を有するようにオブジェクトに割り当てられる。改良されたオブジェクトローダ２００のハッシュ関数２１０は、それらのＧＵＩＤの等価な部分を有するオブジェクトの間で衝突させるように設計され、従って、機能的に関連するオブジェクトが同じチェーンにストアされることを保証する。オブジェクトがアクセスされるとき、各バケットがキャッシュラインのサイズであるように構成されているので、全体バケットはキャッシュされる。従って、同じバケットにストアされ得る機能的に関連するオブジェクトは、１次キャッシュに自動的に持ってこられる。それゆえ、メインメモリアクセスは、次いで、バケットの機能的に関連したオブジェクトのうちの１つの情報がアクセスされるとき、セーブされる。
【００１９】
同じバケットチェーンの関連するオブジェクトに関するオブジェクトエントリをストアし、キャッシュラインと同じサイズである各バケットを構成することによって、著しい性能をセーブすることを生じさせることができる。即ち、いったんバケットチェーンがサーチされたならば、アクセスされた各バケットは、プロセッサによって１次キャッシュにストアされる。従って、アクセスされたバケットが以前として１次キャッシュにある間、バケットチェーンが再びサーチされるならば、このサーチは、１次キャッシュの減少したアクセス時間から利益を得るであろう。この方法では、改良されたオブジェクトローダは、改良された性能を提供するために、今日の進んだプロセッサの多くのキャッシュアーキテクチャを利用するように設計される。
【００２０】
ハッシュテーブル２１４の各オブジェクトエントリ（例えば、２１５）は、弁別器２１６とポインタ２１８とを包含する。弁別器２１６は、オブジェクトを「識別するのを助けるためにＯＩＤの適所で使用される１２ビット数である。１２ビット弁別器によって、多くのオブジェクトに関する識別子は、３２バイトキャッシュラインにストアされることができる。（８バイトＯＩＤがバケットにストアされるならば、２つのオブジェクト識別子だけが１つのバケットにフィットされ得る。）弁別器はＯＩＤの導関数であるが、弁別器とオブジェクトの間に１対１のマッピングはない。それゆえ、弁別器とオブジェクトエントリイールドとを比較すると、だいたい照合するが、正確な照合は必要でない。判断するために、オブジェクトエントリが実際に、ＯＩＤと照合するならば、オブジェクトハンドルテーブルのＯＩＤはチェックされる。弁別器の使用を更に、以下で説明する。ポインタ２１８は、オブジェクトハンドルテーブル２０８のフィールド２２０を参照し、該フィールド２２０は、システムの各オブジェクトに関するあるフィールドを包含する。各オブジェクトハンドルテーブルフィールドは、メモリ内に現在ロードされているならばオブジェクトに関するメモリアドレスか、オブジェクトがロードされる必要があることの指示のいずれかを包含する。オブジェクトハンドルテーブル２０８は、機能的に関連するオブジェクトに関する情報の多くのフィールドを、キャッシュラインのサイズであるあるエントリ（例えば、２２２）内にストアし、従って、減少されたメモリアクセス時間をもたらす。更に、各エントリの関連したオブジェクトに関する情報は、照合するであろうより多くのオブジェクトに関する情報をエントリにストアするように、圧縮される。
【００２１】
インデックスを生成するためにＯＩＤをハッシュした後、改良されたオブジェクトローダ２００は、弁別器をＯＩＤから計算し、バケットのチェーンの各オブジェクトエントリの分別器に対する照合を試みる。各バケットがサーチされるに連れて、プロセッサはそれを１次キャッシュにロードする。従って、バケットが１次キャッシュから移動される前に、バケットのオブジェクトエントリがアクセスされるならば、性能は著しく改善される。改善されたオブジェクトローダは、この性能改善を利用して、関連するオブジェクトに関するオブジェクトエントリを同じバケットチェーングループ化する。弁別器照合がなされたとき、オブジェクトエントリ２１８のポインタは、オブジェクトに関するオブジェクトハンドルテーブル２０８のエントリ２２２のフィールド２２０を参照する。フィールド２２０がメモリアクセスを包含するならば、アプリケーションプログラムがオブジェクトを利用し得るように、このメモリアドレスをアプリケーションプログラム２０４に返す。しかし、オブジェクトハンドルテーブル２０８のフィールド２２０が、オブジェクトがメモリ内にロードされていないことを示すならば、オブジェクトは遠隔にアクセスされ、ローカルメモリにストアされる。オブジェクトをローカルメモリにストアした後、オブジェクトローダ２００は、オブジェクトに関するメモリアドレスをオブジェクトハンドルテーブルフィールド２２０に挿入し、メモリアドレスをアプリケーションプログラム２０４にパスする。
【００２２】
改善されたオブジェクトローダ２００の操作をより明確に説明するために、今、例を提供する。オブジェクトローダは、メモリアドレスが要求され、且つ、マッピングテーブル２０８を使用してＧＵＩＤを８バイトＯＩＤ２０６（例えば、12345678）に変換するためのオブジェクトを指示する、１６バイトＧＵＩＤ２０２（例えば、1234567890123456）を受ける。次いで、オブジェクトローダは、ＯＩＤ２０６を、要求されたオブジェクトに関するオブジェクト情報と、機能的に関連するオブジェクトに関するオブジェクト情報とをストアするバケットチェーン２１２を参照するインデックスを生ずるハッシュ関数２１０に入力する。例えば、ＯＩＤの最後の３バイトが、機能的に関連するオブジェクトの各グループと同じであり得る。即ち、最後の３バイトの「678 」は、ある関数を指示することがあり、最後の３バイトの「689 」は別の関数を指示し得る。次いで、ハッシュ関数は、第３のバケットチェーンを指示する「3 」という同じインデックスに対する同じ最後の３バイトを有するＯＩＤをハッシュし得る。次いで、１２ビット弁別器２１６は、ＯＩＤ２０６から導出され、ＯＩＤ２０６から計算された弁別器を照合する弁別器２１６を有するオブジェクトエントリ２１５を見つけるまで、バケットチェーン２１２の各オブジェクトエントリの弁別器に対して照合される。照合弁別器でオブジェクトエントリ２１５を配置する際に、オブジェクトエントリに包含されたポインタ２１８は、ＯＩＤ２０６によって識別されたオブジェクトに関するメモリアドレスを包含するオブジェクトハンドルテーブルエントリ２２２のフィールド２２０にアクセスするのに使用される。しかしながら、エントリ２２２がメモリアドレスを包含しないならば、オブジェクトは、メモリにロードされ、メモリアドレスはエントリにストアされる。先に述べたように、改善されたオブジェクトローダは、機能的に関連するオブジェクトに互いに関係する情報をグループ化し、オブジェクト情報を圧縮し、各バケットがキャッシュラインの正確なサイズとなるように構成する、バケットのチェーンにこのオブジェクト情報をストアすることによって、多くの進んだプロセッサのチェーンアーキテクチャを利用する。更に、オブジェクトハンドルテーブルの各エントリは、機能的に関連するオブジェクトに関する圧縮された情報を包含し、各エントリは、キャッシュラインの正確なサイズとなるように構成される。その結果、著しい性能改善が達成される。
【００２３】
実施形態の詳細な説明図３は、本発明の好ましい実施形態を実施するために適している処理システム３００を示す。データ処理システム３００は、ネットワーク３０６を介して相互接続された、クライアントコンピュータ３０２とサーバコンピュータ３０４とを含む。２つのコンピュータだけがネットワーク３０６で示されているが、更に多くのコンピュータがネットワークに存在し得ることは明らかである。データ処理システム３００では、サーバコンピュータ３０４は、クライアントコンピュータ３０２のコンピュータプログラムのような、ネットワーク３０６を横切ってたのエントリによって利用される多くのオブジェクト３０８を有する。本発明の好ましい実施形態では、サーバコンピュータ３０４は、レコード、レコードのフィールド、又は、テーブルのようなデータベースオブジェクトをストアするが、しかし、ここで説明される技術が他のタイプのオブジェクトで利用され得ることは当業者には明らかであろう。データ処理システム３００では、クライアントコンピュータ３０２のコンピュータシステムが、サーバコンピュータ３０４の１又はそれ以上のオブジェクト３０８を利用し、従って、サーバコンピュータからオブジェクトを検索し、コンピュータプログラムがそれにアクセスし得るようにメモリ内にオブジェクトをロードするために、改良されたオブジェクトローダと対話する。
【００２４】
図４は、クライアントコンピュータ３０２をより詳細に示す。サーバコンピュータ３０４が同様のコンポーネントを有し得ることは、当業者には明らかであろう。クライアントコンピュータ３０２は、メインメモリ４０２と、２次記憶装置４０４と、カリフォルニア州サンタクララのインテルコーポレーションから入手可能なＰＥＮＴＩＵＭプロセッサのような中央処理装置（ＣＰＵ）４０６と、入力デバイス４０８と、ビデオディスプレィ４１０とを有する。メインメモリ４０２は、オブジェクトにアクセスするコンピュータプログラム４１２と、改良されたオブジェクトローダ４１４と、ハッシュテーブル４１６と、オブジェクトハッシュテーブル４１８と、マッピングテーブル４２０と、メモリ内にロードされており、コンピュータプログラム４１２によって利用される種々のオブジェクト４２２とを含む。ＣＰＵ４０６は、メモリキャッシュ４２４を有する。メモリキャッシュ４２４が、ＣＰＵ４０６の部分として記載されているけれども、クライアントコンピュータ３０２の別の部分に配置されてもよいことは当業者には明らかであろう。
【００２５】
オブジェクトを利用することを試みるとき、コンピュータプログラム４１２はオブジェクトを識別するＧＵＩＤを有するが、オブジェクトを利用することができるようにメモリアドレスを必要とし、従って、改善されたオブジェクトローダ４１４を呼び出す。改善されたオブジェクトローダは、オブジェクトがメモリ４０２に現在ロードされているかどうか判断し、もしそうならば、それがオブジェクトを利用することができるように、オブジェクトのメモリアドレスをコンピュタプログラム４１２に戻す。このプロセスを実行する際に、改善されたオブジェクトローダ４１４は、マッピングテーブル４２０と、ハッシュテーブル４１６と、オブジェクトハンドルテーブル４１８とを利用する。マッピングテーブル４２０は、ＧＵＩＤをＯＩＤに変換するのに使用され、従って、スペースをメモリ４２０にセーブする。変換後、ＯＩＤは次いで、ハッシュテーブル４１８のバケットチェーンを参照するインデックスにハッシュされる。バケットチェーンは、オブジェクトに関するメモリアドレスが包含されているオブジェクトハンドルテーブル４１８にポインタを包含する、要求されたオブジェクトに関するオブジェクトエントリを包含する。しかしながら、オブジェクトハンドルテーブル４１８がメモリアドレスを包含しないならば、オブジェクトローダ４１４は、サーバコンピュータ３０４からオブジェクトを入手し、オブジェクトをメモリ４０２にロードし、メモリアドレスをオブジェクトハンドルテーブルにストアし、メモリアドレスをコンピュータプログラム４１２に返す。
【００２６】
図５Ａは、ＧＵＩＤ５００のダイアグラムを示す。ＧＵＩＤ５００は、オリジン部分５０２と、シーケンス部分５０４という、２つの部分を含む。オリジン部分は、長さが１２バイトであり、オブジェクトの機能（即ち、オブジェクトの機能ユニット）を一意的に指定する。シーケンス部分５０４は、機能ユニットにおける特定のオブジェクトを一意的に識別する順序番号である。ＧＵＩＤ５００は、アプリケーションプログラムのような、オブジェクトの発信者によって生成される。発信者は、全体ネットワークにわたって一意的であるように、オリジン部分５０２を指定する。オリジン部分５０２は、オブジェクトが属する機能ユニットを指定するのに使用される。例えば、発信者は、従業員情報と会社の資本的資産との両方に関するデータベースオブジェクトを生成し得る。発信者は、それが、それらの機能ユニットによってオブジェクトを識別するように、オリジン部分５０２を指定する。例えば、従業員情報に機能的に関連する全てのオブジェクトは、３３１５７のオリジン部分を有するのに対して、資本的資産に機能的に関する全てのオブジェクトは、３３１５８のオリジン部分を有する。オブジェクトに関するオリジン部分５０２を指定する際に、発信者は、特定の機能ユニットの他の全てのオブジェクトに特有の順次番号であり、且つ、機能ユニット内の特定のオブジェクトを指示する、シーケンス部分５０４を指定する。シーケンス部分５０４が順次番号なので、それは、所定の機能ユニットのオブジェクトが生成される、入力順のオーダーを示す。ＧＵＩＤをオブジェクトに割り当てるためのこの方法を使用するので、同じオリジン部分５０２を有する全てのオブジェクトは、機能的に関連することを保証する。更に、逐次実行部分を有する２つのオブジェクトは、互いに近くに一時的に生成されることが保証される。特定の機能ユニットに関するオブジェクト（例えば、従業員データベースオブジェクト）を生成する１より多い発信者があり得ることに注意すべきであり、それゆえ、１より多い発信者は同じオリジンパート５０２をオブジェクトに指定し得る。他の多くのスキームが、機能的に関連するオブジェクトが確実に同じオリジン部分５０２を有するように使用され得ることは、当業者には明らかであろう。
【００２７】
先に述べたように、ＧＵＩＤは、メモリ３０２のスペースを抑えるために、ＯＩＤにマップされる。図５Ｂに示されたＯＩＤ５０６は、長さが８バイトであり、４バイトの圧縮されたオリジン部分５０８と、４バイトのシーケンス部分５１０とを含む。シーケンス部分５１０は、ＧＵＩＤ５００のシーケンス部分５０４と同様である。圧縮されたオリジン部分５０８は、特定のオリジン部分５０２を一意的に識別する値を含む。圧縮されたオリジン部分５０８は、改善されたオブジェクトローダによってオブザーブされる各一意性のオリジン部分５０２に対して一意性の数を順次割り当てることによって生成される。各一意性の数は、図５Ｃに示したような、マッピングテーブル５２０にストアされる。マッピングテーブル５２０は、ＧＵＩＤオリジン部分５３０に対応して、ＯＩＤの圧縮されたオリジン部分５２８のマッピングを含む。マッピングテーブル５２０は、ハッシュテーブルとして実施される。しかしながら、他のデータ構造が、マッピングテーブル５２０を実行するのに使用され得ることは、当業者には明らかであろう。改善されたオブジェクトローダが、マッピングテーブル５２０内に包含されていない、ＧＵＩＤのオリジン部分に出会うたびに、それは、新しいエントリをマッピングテーブルに生成し、一意性の順次番号をＧＵＩＤのオリジン部分に割り当てる。ＯＩＤへのＧＵＩＤの変換中に、ＧＵＩＤオリジン部分が既に出会っており、エントリがマッピングテーブル５２０に存在しているならば、マッピングテーブルエントリに見られる、対応する圧縮されたオリジン５０８は、使用される。
【００２８】
図６は、ハッシュテーブル４１６をより詳細に示す。ハッシュテーブル４１６は、バケット６０２乃至６１２のチェーンを含む。チェーン６０２乃至６１２の各々は、互いにリンクされた多数の個々のバケット（例えば、バケット６１４乃至６２４）である。各バケットは、ＣＰＵ４０６のキャッシュ４２４のキャッシュラインと同じサイズとなるように構成される（例えば、３２バイト）。更に、各バケットは、あるオブジェクトに関する情報を包含する各オブジェクトエントリをもった、多数のオブジェクトエントリを包含する。ハッシュテーブル４１６の他のバケットが同様な構成であるけれども、図７は、バケット６１４のより詳細なダイアグラムを示す。バケット６１４は長さが３２バイトであり、５つのオブジェクトエントリ７０２乃至７１０と、オーバーフローポインタ７１２と、フラグフィールド７１４とを含む。各オブジェクトエントリ７０２乃至７１０は、１２ビット弁別器と、４ビットポインタを含む。次に弁別器を生成するある方法を説明するけれども、他の方法が使用され得ることは、当業者には明らかであろう。弁別器は、ＯＩＤの高オーダー５６ビット（７バイト）を８ビットにマッピングし、低オーダー８ビット（１バイト）を４ビットにマッピングすることによって得られる。ＯＩＤの高オーダー７バイトは、弁別器の高オーダー８ビットを生ずるために、互いに、７バイトと排他的論理和をとることによって弁別器の高オーダー８ビットにマップされる。ＯＩＤの低オーダー８ビットは、弁別器の低オーダー４ビットを生ずるために、互いに、２つの連続の４ビットグループと排他的論理和をとることによって、４ビットにマップされる。ＯＩＤと弁別器との間に１対１のマッピングはないことは明らかである。このように、弁別器は、正確な照合でないが、以下に更に説明するような適当な照合を求めるのに使用される。各オブジェクトエントリ７０２乃至７１０の４バイトポインタ部分は、オブジェクトに関するオブジェクトハンドルテーブルの特定のフィールドを参照する。オーバーフローポインタ７１２は、バケットのチェーンの次のバケットを参照する４バイトポインタである。フラグ７１４は、それらが空であるかどうかのような、オブジェクトエントリ７０２乃至７１０の状況情報を包含する４ビットである。全体バケット６１４は、ＣＰＵキャッシュのキャッシュラインサイズと対応するように、長さが正確に３２バイトである。
【００２９】
図８は、オブジェクトハンドルテーブル４１８をより詳細に示す。オブジェクトハンドルテーブル４１８は、多数のエントリ８０２、８０４及び８０６を含む。各エントリ８０２，８０４及び８０６は、それらのＧＵＩＤ及びＯＩＤの共通のオリジン部分を共有する６つのオブジェクトに関係する情報を包含する。従って、エントリのうちの１つを参照するオブジェクトは、機能的に関連されるように保証される。各エントリは、4 バイトのＯＩＤ８０８の圧縮されたオリジン部分と、4 バイト参照カウント８１０と、エントリの各関連するオブジェクトに関する１つの４バイトシーケンスフィールド８１２乃至８２２とを含む。各エントリ８０２乃至８０６は、キャッシュラインのサイズと対応するように、長さが正確に３２バイトである。参照カウントフィールド８１０は、エントリに参照されたオブジェクトで顕著であるリファレンスの数を含む。参照カウントは、エントリがオブジェクトハンドルテーブルから取り除かれることができるときを判断するのに使用される。各シーケンスフィールド８１２乃至８２２は、オブジェクトがメモリにロードされていないならば、オブジェクトに関するＯＩＤのシーケンス部分か、オブジェクトに対する実際の４バイトポインタを包含するものか、のいずれかを含む。関連するオブジェクトの情報を１つのキャッシュラインにストアすることによって、１次キャッシュヒットは増加し、メインメモリアクセスは減少する。
【００３０】
図９Ａ、９Ｂ及び９Ｂは、改善されたオブジェクトローダによって実行されるステップのフローチャートを示す。以下の説明から明らかなように、ハッシュテーブルとオブジェクトハンドルテーブルの両方のアクセスは、プロセッサのキャッシュアーキテクチャから利益を得る。オブジェクトローダによって実施される第１のステップは、ＧＵＩＤをアプリケーションプログラムから受信し、アプリケーションプログラムは、ＧＵＩＤによって指定されたオブジェクトに関するメモリアドレスを要求する（ステップ９０２）。オブジェクトローダは、ＧＵＩＤをＯＩＤにマップする（ステップ９０４）。このステップは、ＧＵＩＤのオリジン部分が既に存在し、新しいシーケンシャル数をＧＵＩＤのオリジン部分に割り当てず、マッピングテーブルのエントリを生成するならば、マッピングテーブルにアクセスすることによって行われ、そして決定される。ＧＵＩＤをＯＩＤにマッピングした後、オブジェクトローダは、ハッシュテーブル内のインデックスにＯＩＤをハッシュする（ステップ９０６）。このステップでは、オブジェクトローダは、８バイトＯＩＤの高オーダー７バイト（５６ビット）を２４ビットインデックスにマッピングすることによって、ＯＩＤをインデックスにハッシュする。高オーダー５６ビットを利用することによって、各バケットチェーンは、機能的に関連し、一時的に関連する両方であるオブジェクトに関するオブジェクトエントリを有するに違いない。従って、５６ビットの高オーダー３２ビットは、圧縮されたオリジン部分に対応し、従って、機能的に関連したオブジェクトがバケットにストアされることを保証する。更に、５６ビットの残りの２４ビットは、シーケンス部分の最も重要な意味を持つ２４ビットである。それゆえ、同じオリジン部分（即ち、機能的に関連するオブジェクト）と、シーケンス部分の同様の最も重要な意味を持つ２４ビット（即ち、一時的に関連するオブジェクト）との両方を備えるオブジェクトに関するオブジェクトエントリは、同じインデックスに対するそれらのＯＩＤハッシュを有し、従って、同じバケットにストアされるであろう。このステップは、５６ビットを連続の２８ビットの２つのグループに分割することによって実行される。各グループでは、１／４の連続した１２ビットの高オーダーのグループは、残り４ビットを残して互いに排他的論理和がとられる。排他的論理和演算から残った値は、各２８ビットグループに関する１２ビット値をもたらすために、剰余４ビットで排他的論理和がとられたその低オーダー４ビットを有する。次いで、各２８ビットグループに関する１２ビット値は、２４ビットインデックスの半分を構成する。ＧＵＩＤがオブジェクトに割り当てられる方法と組み合わせて、このハッシュ関数が、バケットの同じチェーンにストアされる、機能的に関連するオブジェクトと一時的に関連するオブジェクトの両方に関する情報を導く。
【００３１】
インデックスを生成した後、オブジェクトローダは、先に説明したような弁別器を計算する（ステップ９０８）。弁別器を計算した後、オブジェクトローダは、ステップ９０６で計算されたインデックスによって示されたバケットのチェーンにアクセスし、照合オブジェクトエントリを見つけるために、ステップ９０８で計算された弁別器を、バケットのチェーンの各オブジェクトエントリの弁別器に照合する（ステップ９１０）。照合弁別器でオブジェクトエントリをサーチする間、そらがバケットチェーンの端に達したならば、オブジェクトローダは判断する（ステップ９１１）。バケットチェーンの端が達しているならば、この要求されたオブジェクトに関するオブジェクトエントリはバケットチェーンに含まれておらず、そういうものとして、オブジェクトは、図９Ｃのステップ９３４乃至９４４によって反映されたようなサーバから得られなければならない。要求されたオブジェクトを得るために、オブジェクトローダは、ステップ９０２で受信されたＧＵＩＤを最初に得る（ステップ９３４）。次いで、オブジェクトローダは、サーバコンピュータからＧＵＩＤによって示されたオブジェクトを要求し、サーバコンピュータは、関連するオブジェクトの数（「クラスタ」）をオブジェクトローダに送る（ステップ９３６）。このステップでは、サーバコンピュータは、関連するオブジェクトのグループを先取りし、それらのオブジェクトのうちの１つがすぐに利用されるであろうことを希望して、それらをオブジェクトローダに送り、次いで、サーバコンピュータへのアクセスと関連したオーバーヘッドをセーブする。サーバコンピュータは、要求されたオブジェクトのＧＵＩＤに連続的に続くＧＵＩＤを有するオブジェクトの所定の数を選択することによって、オブジェクトのグループを決定する。オブジェクトのクラスタを受信した後、オブジェクトローダは、要求されたオブジェクトをメモリにロードする（ステップ９３８）。要求されたオブジェクトをメモリにロードするとき、オブジェクトローダは、要求されたオブジェクトによって参照されるオブジェクトのアプリケーションプログラムの使用を容易にするために処理を実行する。システムの各オブジェクトは通常、１又はそれ以上の他のオブジェクトに対するリファレンス（即ち、ＧＵＩＤ）を含む。要求されたオブジェクトをメモリにロードする際に、オブジェクトローダは、ＧＵＩＤをＯＩＤに変換し、参照されたオブジェクトに関するオブジェクトハンドルテーブルの適当なフィールドを求め、リファレンスを有するこれらのＧＵＩＤを参照されたオブジェクトに関するオブジェクトハンドルテーブルのフィールドに置換する。フィールドがリファレンスされたオブジェクトに関して現在生成されていないならば、フィールドは以下に説明するように生成される。
【００３２】
次に、オブジェクトローダは、オブジェクトハンドルテーブルに返された各オブジェクトを加える（ステップ９４０）。このステップでは、オブジェクトローダは、オブジェクトのＯＩＤのオリジン部分を照合するオリジン部分を有するオブジェクトハンドルテーブルのエントリがあるかどうかを判断するために、各オブジェクトに関するオブジェクトハンドルテーブルにアクセスする。かかるエントリがなく、若しくは、かかるエントリはあるが、そのシーケンスフィールドの全てが満たされているならば、オブジェクトローダは、オブジェクトのＯＩＤのオリジン部分をオリジンフィールド８０８に挿入することによって、且つ、ＯＩＤのシーケンス部分を第１のシーケンスフィールド８１２に挿入することによって、オブジェクトハンドルテーブルのえんとりを生成する。もちろん、要求されたオブジェクトをオブジェクトハンドルテーブルに追加するとき、そのメモリアドレスはシーケンスフィールドにストアされる。オブジェクトＯＩＤのオリジン部分を照合するオリジン部分を有するオブジェクトハンドルテーブルにエントリがあり、エントリが空のシーケンスフィールドを有するならば、オブジェクトに関するＯＩＤのシーケンス部分は挿入される。各オブジェクトをオブジェクトハンドルテーブルに加えた後、オブジェクトローダは各オブジェクトに関するハッシュテーブルエントリを生成する（ステップ９４２）。このステップでは、オブジェクトローダは、各オブジェクトに関するＧＵＩＤを受信し、ステップ９０４に記載したようにＧＵＩＤをＯＩＤに変換し、ステップ９０６に記載したようにハッシュテーブル内のインデックスにこれらのＯＩＤをハッシュする。次いで、オブジェクトローダは、指示されたバケットチェーンにアクセスし、オブジェクトエントリをバケットチェーンの第１のからのエントリに挿入する。空のエントリが見つからず、バケットチェーンの端が達しているならば、新しいバケットが割り当てられ、バケットチェーンの端に加えられる。オブジェクトエントリを生成する際に、オブジェクトローダは、以前にステップ９０８で記載したように弁別器を計算し、ステップ９４０で求められたオブジェクトハンドルテーブルのオブジェクトのフィールドにリファレンスを挿入する。各オブジェクトに関するハッシュテーブルのオブジェクトエントリを生成した後、オブジェクトローダは、要求されたオブジェクトのメモリアドレスを、アプリケーションプログラム及び処理端に返す。
【００３３】
ステップ９１１でチェーンの端が達しておらず、照合弁別器を備えるオブジェクトエントリが見つかっていないならば、オブジェクトローダは、オブジェクトエントリに包含されたポインタを使用してオブジェクトハンドルテーブルにアクセスする（ステップ９１２）。オブジェクトハンドルテーブルにアクセスした後、オブジェクトローダは、シーケンスフィールドへの参照がポインタを含むかどうか判断する（ステップ９１４）。フィールドの最後のビットは、それがポインタであるかシーケンスであるかどうか示す。シーケンスフィールドがポインタを含むならば、オブジェクトローダは、ポインタを使用してオブジェクトにアクセスし、照合があるかどうか判断するために、オブジェクトに包含されたＧＵＩＤをステップ９０２で受信されたＧＵＩＤと比較する（ステップ９１６）。各オブジェクトは、それ自身のＧＵＩＤのコピーをストアする。このステップでは、ＧＵＩＤは、ハッシュテーブルの正しいオブジェクトエントリが確実にアクセスされるためにチェックされる。弁別器が正確な照合、もっともらしい照合さえも保証しないので、この処理を行う必要がある。ＧＵＩＤが照合するならば、オブジェクトローダはメモリアドレスをアプリケーションプログラム（ステップ９１８）と処理端に返す。しかしながら、ＧＵＩＤが照合しないならば、オブジェクトローダは、照合弁別器を包含するバケットチェーンから次のオブジェクトエントリを選択し（ステップ９２０）、バケットチェーンの端が達しているかどうか判断するステップ９１１へ続く。
【００３４】
シーケンスフィールドがポインタを包含しないならば、オブジェクトローダは、ステップ９０４のＯＩＤがオブジェクトハンドルテーブルに包含されたＯＩＤと照合するかどうか判断する。ＯＩＤが照合しないならば、処理は、ステップ９２０に続き、別のオブジェクトエントリが選択される。しかし、ＯＩＤが照合するならば、オブジェクトローダは、ステップ９０２で受信されたＧＵＩＤを得る（ステップ９２４）。ＧＵＩＤを得た後、オブジェクトローダは、サーバコンピュータからオブジェクトを得る（ステップ９２６）。このステップでは、オブジェクトローダは、ネットワーク３０６を介してサーバコンピュータ３０４にアクセスし、オブジェクトのクラスタを受信する。オブジェクトのクラスタを得た後、オブジェクトローダは、ステップ９３８に記載したようにオブジェクトをメモリにロードする（ステップ９２８）。オブジェクトをメモリにロードした後、オブジェクトローダは、オブジェクトのメモリアドレスをアプリケーションプログラムに返し、メモリアドレスをオブジェクトハンドルテーブルのシーケンスフィールドにストアする（ステップ９３０）。メモリアドレスをアプリケーションプログラムに返し、アドレスをオブジェクトハンドルテーブルにストアした後、オブジェクトローダは、ステップ９４０に記載したようにかかるオブジェクトをオブジェクトハンドルテーブルに加え、ステップ９４２に記載したように各オブジェクトに関するハッシュテーブルエントリを生成する（ステップ９１２）。このプロセスを実行した後、プロセスは終了する。
【００３５】
本発明を好ましい実施形態を参照して説明してきたけれども、添付した特許請求の範囲で定義される本発明の精神及び範囲から逸脱することなく、形態及び詳細における種々の変更がなされることは、当業者には明らかであろう。
【図面の簡単な説明】
【００３６】
【図１】在来のオブジェクトローダによって利用される在来のハッシュ機構を示す。
【図２】本発明の好ましい実施形態の改良されたオブジェクトローダの機能的ダイアグラムを示す。
【図３】本発明の好ましい実施形態を実行するために適しているデータ処理システムを示す。
【図４】図３のクライアントコンピュータのより詳細なダイアグラムを示す。
【図５Ａ】本発明の好ましい実施形態において使用されるような汎用一意性識別子のフォーマットを示す。
【図５Ｂ】本発明の好ましい実施形態において使用されるようなオブジェクト識別子のフォーマットを示す。
【図５Ｃ】図４のマッピングテーブルをより詳細に示す。
【図６】図４のハッシュテーブルをより詳細に示す。
【図７】図６のハッシュテーブルのバケットをより詳細に示す。
【図８】図４のオブジェクトハンドルテーブルをより詳細に示す。
【図９Ａ】図４に示された改良されたオブジェクトローダによって実行されるステップのフローチャートを示す。
【図９Ｂ】図４に示された改良されたオブジェクトローダによって実行されるステップのフローチャートを示す。
【図９Ｃ】図４に示された改良されたオブジェクトローダによって実行されるステップのフローチャートを示す。
【図１】
2008027450.tif 000003
【図２】
2008027450.tif 000004
【図３】
2008027450.tif 000005
【図４】
2008027450.tif 000006
【図５Ａ】
2008027450.tif 000007
【図５Ｂ】
2008027450.tif 000008
【図５Ｃ】
2008027450.tif 000009
【図６】
2008027450.tif 000010
【図７】
2008027450.tif 000011
【図８】
2008027450.tif 000012
【図９Ａ】
2008027450.tif 000013
【図９Ｂ】
2008027450.tif 000014
【図９Ｃ】
2008027450.tif 000015
【外国語明細書】
2008027450000001.pdf