JP4978025B2

JP4978025B2 - ポインタの圧縮・伸張方法、これを実行するプログラム、及び、これを用いた計算機システム

Info

Publication number: JP4978025B2
Application number: JP2006047665A
Authority: JP
Inventors: 博泰西山
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2006-02-24
Filing date: 2006-02-24
Publication date: 2012-07-18
Anticipated expiration: 2026-02-24
Also published as: US7539695B2; US20070276794A1; JP2007226583A

Description

本発明は、プログラムのデータ構造におけるポインタの格納技術に係り、特に、ポインタの圧縮・伸張のオーバーヘッドと、データ構造の小型化に関する。

プログラムを含む大規模なデータの取り扱いを容易とするために、最近のマイクロプロセッサには、64bitのアドレス空間をサポートするものがある。
アドレス桁数を32bitから64bitへ拡張することにより、プログラムが参照可能なメモリ空間は、最大4GB(GigaByte=10の9乗バイト)から最大16EB(ExaByte=10の18乗バイト)へ増大する。しかし一般的な顧客の用途では、数GBにも満たないメモリ空間しか必要としないことが多く、現在の計算機システムでは未だ32bitのアドレス桁数で十分であることが多い。

64bitのアドレスを指定するためのポインタは、32bitのアドレスのものより大きさが拡大する。このことは、プログラムが扱うデータ構造が同一であっても、32bitプロセッサの場合と比較して64bitプロセッサでは、メモリ上でポインタの占める割合が増大することを意味する。
また、Javaその他のオブジェクト指向プログラムでは、オブジェクトと呼ばれるデータ構造の中に、ポインタが頻繁に出現する。このためポインタ拡大の影響が特に大きく、メモリが有限であることから、ポインタを含むデータ構造の一部を格納しきれない事態が生じる。

単純なデータ構造を繰り返し用いる傾向の強い、FORTRANその他の旧来のプログラミング言語と比較すると、Javaのような言語では、キャッシュメモリの使用効率が悪くなってしまう。以下に説明を補足する。
一般的なマイクロプロセッサは、主記憶メモリを参照するために、数百サイクルに相当する長い時間を要する。これを避けるため、主記憶メモリとレジスタの間に、キャッシュと呼ばれる小容量かつ高速アクセスが可能なメモリを備えている。プロセッサは、アクセスしたデータのコピーをキャッシュ上に保持する機能を備えており、キャッシュ上に参照対象のデータが存在する場合には、そのデータ参照を高速に行なうことが可能となる。ただし、キャッシュ容量は有限であり、データ量が増加すると、キャッシュに格納可能なデータの個数は減少する。

そこで、Java言語を用いたプログラムは、Javaのヒープメモリ内に確保されるオブジェクトを対象として、オブジェクト内のポインタ表現を圧縮する手法が提案されている(非特許文献1)。非特許文献1で提案されている手法では、Javaヒープメモリ内に確保されたオブジェクトを指定するポインタを、ヒープメモリの先頭を表すベースアドレスと、ベースアドレスからのオフセット値として表現する。

かかるメモリ空間の構成を図３に示す。64bitのアドレスを有するメモリ空間301において、ヒープメモリ302は、変数 base によって指定されたベースアドレス304から始まり、連続するアドレスを有する。そして、オブジェクト303は、ヒープメモリ302の中に配置される。ベースアドレス304は固定であるので、ヒープメモリのアドレスの最大長を、32bitで表現可能な最大値である4GBに制限すれば、ヒープメモリ内のオブジェクトを指定するポインタを、ベースアドレス304からのオフセット305で指定すれば、32bitへ圧縮した形式で表現することができる。
なお、例えば、オブジェクトの配置アドレスが8の倍数である場合には、オフセット値を8倍するなどの工夫によって、より大きなヒープメモリ領域を対象とすることができる。このように、ポインタを64bitから32bitに圧縮することにより、ポインタを含むデータ構造のサイズを削減することができる。これは前述のようにキャッシュに格納可能なデータ構造の総量を増加させることとなり、キャッシュヒット率の向上に繋がる。

オブジェクト中のデータを実際に参照する場合には、非圧縮形式のポインタ値が必要である。従って、圧縮形式で定義されたポインタが指定するオブジェクトを、計算機システムが参照する場合、圧縮形式から非圧縮形式へ、ポインタ表現の変換が必要となる。逆に、非圧縮形式のポインタ値を格納する場合、非圧縮形式から圧縮形式へ、ポインタ表現の変換が必要となる。
圧縮形式から非圧縮形式への変換は、圧縮形式のポインタ値にベースアドレスを加算して為される。また、非圧縮形式から圧縮形式への変換は、非圧縮形式のオブジェクトのアドレスからベースアドレスを減算して為される。ただし、Javaを始めとして殆どのプログラミング言語では、有効なデータを指定しないポインタ値として、nullと呼ばれる特殊な値を用意していることに留意する必要がある。図3に示すように、null306の値としては0を利用することが一般的である。オブジェクト303のアドレスを、ベースアドレス304からのオフセット305で表現する場合、そのままではnull値を表現することができない。よって、ポインタ値がnullの場合を特別に扱う必要がある。

図４は、ポインタの圧縮・伸長シーケンスの従来例である。つまり図４は上述の考慮を加えた、圧縮形式のポインタのロード/ストア処理の擬コードを示している。圧縮形式のポインタのロードを行う際には、ロードした値が0(null値)か否かを確認し、0の場合はポインタ値の補正を行う(401)。同様にストアの際にはストア対象の値を確認し、0である場合には補正を行う(402)。

図５に、従来のポインタの圧縮の効果を例示する。
501はポインタ圧縮の対象とするオブジェクト定義の例である。ここで、オブジェクト定義中left、right、name、valueは他のオブジェクトを指定するポインタであるものとする。オブジェクトの属性等を格納するヘッダが2ワードを占めるものと仮定すると、64bitプロセッサにおいて非圧縮形式のポインタ表現を利用した場合には、502に示すように対象オブジェクトは10ワードのメモリ領域を占める。一方、圧縮形式のポインタ表現を利用した場合には、503に示すように6ワードの占有となり、使用メモリ量が4ワード削減される。

A. Adl-Tabatabai, J. Bharadwaj, M. Cierniak, M. Eng, J. Fang, B. Lewis, B. Murphy, and J. Stichnoth, Improving 64-Bit Java IPF Performance by Compressing Heap References, In Proceedings of the International Symposium on Code Generation and Optimization, 2004.

従来のポインタ圧縮手法では、非圧縮形式と圧縮形式のポインタの間で変換を必要とする。このため、プログラムが参照する頻度の高いポインタを圧縮してしまうと、圧縮によるキャッシュヒットの向上よりも、変換のオーバヘッドが勝り、結果として性能低下を招く可能性がある。

プログラムにおけるポインタの参照を解析し、ポインタをアクセス頻度の高いポインタと、そうでないポインタに分類する。アクセス頻度の高いポインタは非圧縮形式とし、そうでないポインタは圧縮形式とする。更に、ポインタが圧縮形式、非圧縮形式のいずれであるかを識別するための手段を設ける。その手段は、ポインタの帰属するフィールド毎に表によって識別すること、又は、ポインタ自身に格納された値によって識別することを含む。

プログラムが参照するポインタの圧縮・非圧縮の変換に要するオーバヘッドを削減・抑制しつつ、圧縮形式のポインタを使用してデータ構造のメモリ占有量を削減することにより、キャッシュヒット率が向上し、計算機システム（プログラム実行）の性能向上を図ることができる。

以下に、本発明の実施の形態を説明する。

図２に本発明の適用対象である計算機システムの概略構成を示す。
本発明を適用した言語処理系は、外部記憶装置203に格納される。言語処理系の実行は、CPU201によって、外部記憶装置203から主記憶メモリ202へ言語処理系のプログラムが読み出され、CPU201によって実行されることにより為される。
CPU201は、主記憶メモリ202へのアクセスを高速化するために、小容量かつ高速なキャッシュメモリ206を備えている。CPU201が計算処理を行う場合は、データをレジスタ205へロードし、演算器204で演算を行う。レジスタ205へデータのロードを行う際には、まず、キャッシュメモリ206に当該データが存在するか否かを確認し、存在する場合はそれを利用する。存在しない場合は、主記憶メモリ202からデータを読み出してレジスタ205へロードすると共に、キャッシュ206へも格納しておく。

図1に本発明の1つの実施例を示す。
本発明を適用した言語処理系101は、ソースプログラム105を入力とし、変換済みプログラム107を出力する。言語処理系101は、ポインタ参照頻度解析部102、データ構造変換処理部103、コード生成処理部104から構成される。言語処理系101を構成する各部は、中間語106を参照する。また、実施形態によっては、ポインタ参照頻度解析部102は、ポインタ参照頻度に関するプロファイルデータ108を参照する。

図６に、図５のオブジェクトにおけるポインタの、参照頻度に関するプロファイルデータ108の例を示す。
プロファイルデータ108（図１）は、クラス名601、フィールド名602、参照頻度603の3つのフィールドからなるエントリより構成される。なお、ここでは、プログラム中の全てのフィールド参照回数に対する個々のフィールドの参照回数の割合を参照頻度と呼ぶものとする。図6の例では、フィールドright、および、leftの参照頻度が高く、value、nameの参照頻度が低いことが分る。よって、right、および、leftを非圧縮対象とし、value、nameを圧縮対象とすることで、ポインタ参照の際の圧縮・非圧縮変換のオーバヘッドを削減しながらメモリ使用量を削減できる。この結果を図７に示す。

図７に示す混合形式のオブジェクト構造では、オブジェクトの属性等を格納するヘッダが2ワードを占め、フィールドleft及びrightを非圧縮形式(2ワード)とし、フィールドname及びvalueを圧縮形式(1ワード)としている。これにより、オブジェクトサイズは8ワードに削減されると共に、left及びrightを参照する際の変換オーバヘッドが低減される。

図8〜10のフローチャートを用いて図1の言語処理系101の処理について説明する。
図8は、ポインタ参照頻度解析部102の処理フローの実施例を示したものである。この処理では、プロファイルデータ108を参照してフィールド参照を圧縮対象とするか否かの分類を行う。処理801で処理を開始し、処理802においてプログラム中で定義されるデータ構造の集合を変数Sとする。次に、判定処理803に制御を移し、変数Sが空集合か否かを確認する。空集合である場合は処理すべきデータ構造の定義が存在しないため、処理809へ制御を移して処理を終了する。

判定処理803において変数Sが空集合でなかった場合は、処理804へ制御を移し、変数Sからデータ構造の定義を1つ取り出して変数sに格納する。また、データ構造の定義sの各フィールドに関する参照頻度の情報の集合を変数Rとする。なお、各フィールド、例えばフィールド名602（図６）に関する参照頻度の情報の集合は、図1のプロファイルデータ108から、同一のデータ構造に対するエントリを取り出すことで求めることができる。なお、プロファイルデータ108は、プログラムを事前に実行することにより生成しておく必要がある。
続いて判定処理805によって変数Rが空集合か否かを確認する。変数Rが空集合である場合は、処理すべきフィールドが存在しないので、処理803へ制御を移して次のデータ構造を処理する。変数Rが空集合でない場合は、処理806へ制御を移し、参照頻度の情報の集合Rから要素を1つ取り出し変数rへ格納すると共に、参照頻度の情報を有する変数rの表すフィールド名に対応する参照頻度を変数fに格納する。

続いて、判定処理807においてfの値が一定の閾値より小さいか否かを判定する。一定の閾値より小さな場合（807、YES）は、ポインタの参照頻度が低いものとしてrに対応するポインタの値を圧縮対象とし（808）、判定処理805へ戻って次の参照頻度の情報を処理する。fが閾値以上の場合（807、NO）は、rに対応するポインタの値を圧縮対象とせず、判定処理805へ戻って次の参照頻度の情報を処理する。
以上の処理により、参照頻度の低いポインタの値のみを圧縮対象として選別することができる。ここで、あるポインタが圧縮対象か否かの情報は、図1の中間語106又はこれに付随した情報として記憶しておく。

図９のフローチャートは、図1のデータ構造変換処理部103の処理フローの実施例を示したものである。データ構造変換処理部103は、プログラム中で定義されるデータ構造に対して、その中で定義される個々のポインタが占める領域長を、ポインタ参照頻度解析部102の結果に基づき求める。ポインタ参照頻度解析部102はプロファイルデータ108を参照し、非圧縮対象フィールドについては圧縮前のフィールド長、圧縮対象フィールドについては圧縮後のフィールド長を、各フィールド（図６）の領域長として求め、データ構造の先頭から足し合わせることにより、データ構造内のフィールドのレイアウトが決定される。なお、オブジェクトにおけるフィールドの順序が宣言順と異なることを許す言語の場合、フィールド長の計算後に、フィールドの並べ替えを行うことで、メモリ領域を有効に利用することができる。

データ構造変換処理部103（図１）は、処理901で処理を開始し、処理902においてプログラム中で定義されるデータ構造の定義の集合を変数Sとし、圧縮形式のポインタのメモリ上での大きさを変数PSとし、非圧縮形式のポインタのメモリ上での大きさを変数PLとする。次に処理903へ制御を移し、変数Sが空集合か否かを確認する。空集合である場合は、処理すべきデータ構造が存在しないため、処理910に制御を移して処理を完了する。
変数Sが空集合でない場合は、処理904に制御を移し、変数Sからデータ構造の定義を表す要素を1つ取り出して変数sに格納すると共に、データ構造の変数sの中で定義されるポインタフィールドの集合を変数Fとする。続いて、判定処理905へ制御を移し、変数Fが空集合か否かを確認する。Fが空集合である場合は処理すべきポインタフィールドが存在しないため、処理903へ制御を移して次のデータ構造の定義の処理を行う。Fが空集合でない場合は、処理906へ制御を移し、変数Fからポインタフィールドを1つ取り出して、変数fに格納する。ポインタ参照頻度解析部102において、フィールドfが圧縮対象と判定されたか否かを、判定処理907によって確認し、圧縮対象である場合は処理908によってフィールドfの領域長をPSとし、圧縮対象でない場合は、処理909によってフィールドfの領域長をPLとする。
その後、処理905へ制御を移し、次のフィールドの処理を継続する。以上の処理により、データ構造のメモリ割り当て時にポインタフィールドの占める領域が決定される。

図10のフローチャートは、図1のコード生成処理部104の実施例を示したものである。
コード生成処理部104は、処理1001によって処理を開始し、処理1002において出力対象命令列を変数Iとする。次に、判定処理1003において、変数Iが空か否かを確認する。空である場合は、処理すべき命令が存在しないため、処理1010に制御を移して処理を完了する。変数Iが空でない場合は、処理1004に制御を移し、変数Iから要素を1つ取り出して変数iに格納する。
次に、判定処理1005によって変数iがポインタフィールドを参照する命令か否かを確認する。ポインタフィールド参照命令でない場合は、処理1006によって従来の命令生成処理を変数iに適用し、処理1003に制御を移して次の命令の処理を行う。判定処理1005で、変数iがポインタフィールド参照命令であった場合、続いて判定処理1007によって、iの参照先が圧縮対象であるか否かを判定する。iの参照先が圧縮対象でない場合は処理1008で通常のポインタ参照コードを生成し、圧縮対象である場合は処理1009で圧縮・伸長処理を付加したポインタ参照コードを生成する。
続いて処理1003に制御を移して次の命令の処理を行う。以上の処理によって、ポインタを圧縮形式と非圧縮形式に分類し、参照頻度の高いフィールドについては非圧縮形式として扱うことにより、ポインタ参照オーバヘッドを削減すると共に、全体のデータ量を削減することが可能となる。

実施例１で、プロファイルデータ108（図１）を用いて行っていた、プログラム中のフィールド参照頻度の予測処理は、プロファイルデータ108を使用せず、プログラム解析によって行うことも可能である。プログラム解析によって図1のポインタ参照頻度解析部102を実現した場合の処理の実施例を、図11のフローチャートに示す。
処理1101で処理を開始し、処理1102においてプログラム中のループ集合を変数Lとする。続いて判定処理1103によって変数Lが空集合か否かを判定する。変数Lが空集合であった場合、処理対象のループが存在しないので、処理1107に制御を移して処理を終了する。変数Lが空集合でなかった場合は、処理1104に制御を移して、ループ集合Lから要素を1つ取り出して変数lとする。また、変数lの予測ループ長を変数nとし、変数lの中のフィールド参照集合を変数Rとする。

次に、判定処理1105によって、変数R（フィールド参照集合）が空集合であるか又は変数n（予測ループ長）が閾値より小さいか否かを確認する。変数Rが空集合、又は、nが閾値よりも小さな場合は、変数l（ループ集合Lの１要素）には圧縮対象のフィールド参照は存在しないため、処理1103に制御を移して次の変数Lを処理する。
変数Rが空集合でなく、かつ、nが閾値以上の場合は、処理1106に制御を移す。処理1106では、変数R（フィールド集合）から要素を取り出して変数rに格納し、フィールドrを圧縮対象とする。続いて処理1105に制御を移して次の変数R（フィールド参照集合）の判定処理を行う。

以上の処理によって、ループの自動的な解析を行うことでプログラム中のフィールド参照頻度を予測し、参照頻度が低いと予測されるデータのみを圧縮対象として選別することができる。

図7のような、圧縮形式のポインタ704、705と非圧縮形式のポインタ702、703がまじった混合形式のオブジェクトのフォーマットを利用する場合には、あるフィールドが圧縮されているか否かを静的に決定できない場合がある。例えば、多くのJava言語の実装では、プログラムをインタープリタ又は動的コンパイラによって生成されたコードによって実行する。このとき、コンパイラではフィールドの形式とそれを参照するコードとを、1対1に対応づけることが可能であるため、ポインタがどちらの形式であるかを静的に決定することができる。
一方、インタープリタでは、１つのコードで複数のフィールドの参照を司る必要があるため、フィールドの形式を動的に判定する必要がある(後述)。
図12は、フィールド情報1203の表を用いて、ポインタの圧縮形式を判定する場合の、データ構造を表わした図である。フィールド情報1203は、クラスの定義とポインタ参照頻度解析部102(図1)の判定結果に基づき、求められる。オブジェクト1201は、プログラムのデータ構造を表しており、その所属するクラスに関する情報1202へのポインタ又は類似の情報を持っている。クラスに関する情報1202を経由して、フィールド情報1203を参照することが可能である。ここで、フィールド情報1203は、フィールド名称1204、フィールド位置1205、フィールドが圧縮されていることを意味するフラグ1206から構成される。図12のフィールド情報1203からオブジェクト1201の中の位置2に存在するフィールドは非圧縮形式、位置6に存在するフィールドは圧縮形式であることがわかる。

図17にフィールド情報1203の作成処理のフローチャートを示す。
フィールド情報1203の作成処理は、処理1701で処理を開始し、処理1702においてフィールド情報の作成対象であるクラスの中で定義されるフィールドの集合を、変数Fとする。また、変数Tを空のフィールド情報に初期化する。続いて、判定処理1703によって、求めたフィールド集合Fが空集合か否かを判定する。空集合であれば、処理すべきフィールドが存在しないので、処理1705に制御を移して、変数Tのフィールド情報を対象クラスのフィールド情報とする。判定処理1703で集合Fが空集合でない場合は、処理1704に制御を移し、集合Fからフィールドを1つ取り出して変数fへ格納する。また、fの名称、位置、圧縮対象か否かを、それぞれ、変数n, p, cへ格納し、変数n, p, cの組をフィールド情報Tへ追加する。続いて、処理1703へ制御を移して次のフィールドの処理を行う。

実施例３による、ポインタが圧縮されているか否かの識別方法では、オブジョエクト1201の各フィールドを参照する度に、フィールド情報1203を参照せねばならず、効率が悪い。そこで、ポインタ自身に圧縮・非圧縮の情報を保存することにより、その識別を可能とする。
図13に、メモリ上のデータ構造に含まれるポインタの圧縮表現を、データ表現形式別に例示する。複数バイトデータの内部バイトの配置によって (a)のbig-endian形式と、(b)のlittle-endian形式がある。big-endian形式では、データの最上位ビット(MSB: Most Significant Bit)が低位アドレス、最下位ビット（LSB: Least Significant Bit）が高位アドレスに保存される。逆に、little-endian形式では、データのMSBが高位アドレス、LSBが低位アドレスに保存される。圧縮形式(1301)と非圧縮形式(1302)のポインタは、どちらも低位アドレスを占めるので、低位アドレスに識別用の情報を持たせるようにする。

すなわち、big-endian形式では、最低位アドレスに配置されるバイトのMSB(1303)をポインタ形式の識別用に用い、little-endian形式では、最低位アドレスに配置されるバイトのLSB(1304)をポインタ形式の識別のために利用する。この時、非圧縮形式のポインタの値を通常とは異なる値とすると、実行時のオーバヘッドが増加するため、通常の値と同一とするのが良い。通常、オブジェクトの配置アドレスは8の倍数であるため、LSBの値は常に0となる。
よって、little-endian形式のポインタ表現の場合では、圧縮形式のポインタのLSB値を1、非圧縮形式のポインタのLSBの値を0と決めておくと都合が良い。

big-endian形式のポインタ表現の場合では、非圧縮形式のポインタのMSBの値はヒープメモリ領域の割り当てアドレスに依存する。ヒープメモリ領域の割り当てアドレスは、OSその他のプログラムのメモリ割り当て処理に依存するため、MSBを固定値とすることは一般に容易でない。ただし、ヒープメモリは連続領域に確保されるため、その領域内でのMSB値は同一にできる。
よって、(i) ヒープメモリの割り当てアドレスのMSBが0の場合、0が非圧縮形式、1が圧縮形式のポインタを表すものとし、(ii) ヒープメモリの割り当てアドレスのMSBが1の場合、1が非圧縮形式、0が圧縮形式のポインタを表すものとすれば好都合である。(ii)の場合において、非圧縮形式のポインタと、ヒープメモリの先頭を指定するベースアドレスからのオフセットが一致しているため、アドレス計算のための余分なオーバヘッドは生じない。

(i)の場合において、オフセット値を求める際にMSBを補正するためのオーバヘッドが生じる。これについては、図14を用いて説明する。図14は、big-endian計算機システムにおけるメモリ空間の構成を示している。図14に示すように、オブジェクトのアドレスを求めるためのベースアドレスを、ヒープメモリの先頭アドレスであるbase 1404ではなく、そこから0x80000000だけ低位のアドレス、virtual_base 1401を用いれば良い。こうすることにより、アドレス計算時の加算によりMSBの補正が行なわれ、オブジェクト1403(図14)のアドレスが求められる。
詳述すれば、ヒープ先頭を示すbase 1404のアドレスが、16進表記で0x0000000080000000とする。また、オブジェクト1403のアドレスを0x0000000080102030とする。この時、ヒープ先頭からオブジェクト1403までのオフセットは、32bit表現で0x00102030と表され、圧縮表現であることを示すためにMSBを1とすると圧縮ポインタ表現は0x80102030=0x80000000+0x00102030となる。
また、上記virtual_base 1401の値は、base 1404から0x80000000だけ低位のアドレス、すなわち、0x0000000080000000-0x80000000=0x0000000000000000となる。よって、virtual_baseの値とMSBを1とした圧縮形式ポインタを加算することで、MSBを1とすることによる値の増加分(0x80000000)が補正され、オブジェクト1404のポインタ値0x0000000080102030を得ることができる。
なお図13の例では、圧縮表現のポインタが非圧縮表現のポインタの4バイト目以降に配置される場合がある。このときは、圧縮表現のMSBと非圧縮表現のMSBが重ならない（整列しない）ため、MSBによるポインタ形式の識別はできないこととなる。しかし通常のポインタは、そのデータサイズの倍数のアドレスに整列して配置されるため、ポインタのアドレスが、非圧縮表現で整列して配置されたアドレスと異なることをもって、圧縮表現であることを知ることができる。

図15に、ポインタの圧縮形式識別処理のフローチャートを示す。
圧縮形式識別処理は、処理1501で処理を開始し、続いて処理1502で判定対象のポインタのフィールドから、アドレスを変数pに、pの指定するアドレスのバイト値を変数bに、それぞれ格納する。次に判定処理1503で、対象となる計算機システムがbig-endian形式を使用しているか否かを判定する。
big-endian形式を使用している場合は、処理1504に制御を移し、変数bのMSB値を変数fとし、ヒープメモリ領域の割り当てられたアドレス空間のMSBの値を変数hとする。次に判定処理1505によって、fがhに等しいか否かを判定する。等しくない場合は圧縮形式のポインタであるので、処理1506に制御を移し、圧縮形式であると判定する。等しい場合は、処理1507に制御を移し、非圧縮形式であると判定する。その後、処理1510に制御を移して処理を完了する。
判定処理1503で対象となる計算機システムがbig-endian形式でなかった場合は、処理1508に制御を移して変数bのLSBを変数fとする。続いてfの値が0か否かを判定処理1509で判定する。fの値が0でなければ処理1506に制御を移してポインタを圧縮形式と判定し、fの値が0であれば処理1507に制御を移してポインタを非圧縮形式と判定する。その後、処理1510に制御を移して処理を終了する。
以上により、ポインタの指定先の形式を動的に判定することができる。

図16に、圧縮形式のポインタをデータ構造の実アドレスに変換する処理のフローチャートを示す。
この変換処理は、処理1601で処理を開始し、処理1602で対象とする圧縮ポインタ値を変数cとする。続いて、判定処理1603で対象となる計算機システムがbig-endian形式が否かを判定し、big-endian形式の場合は、処理1604に制御を移して、変数cに仮想ベースの値を加えた値を、求めるデータ構造におけるポインタの実アドレスとして変数pとし、処理1606に制御を移して処理を完了する。前述のように、仮想ベース1401（図14）の値は、圧縮ポインタ1301（図13）のMSBを1に設定することによって増加する値(0x80000000)だけ、ヒープメモリ1402の先頭から下位アドレス方向へずらしたアドレスに設定されている。よって、仮想ベース1401と圧縮ポインタ1301の値を加算することにより、MSBによる増分が打ち消され、オブジェクト1403の実アドレスが求められる。また、対象となる計算機システムがbig-endian形式でない場合は、変数c（1301）のLSBをクリアした値に、ヒープメモリ1402のベースアドレス1404の値を加えた値を、求めるデータ構造におけるオブジェクトをポインタが示す実アドレスとして変数pとし、処理1606に制御を移して処理を完了する。
以上により、圧縮形式のポインタ値からデータ構造の実アドレスを求めることができる。

ポインタを扱うプログラムの性能向上のために利用できる。

本発明を適用した言語処理系の構成を示す図である。本発明の適用対象である計算機システムの概略構成図である。メモリ空間の構成を示す図である。ポインタの圧縮・伸長シーケンスを例示するための図である。従来のポインタの圧縮を例示するための図である。参照頻度のプロファイルデータ108の例を示す図である。圧縮・非圧縮のポインタが混合したオブジェクト構造の例を示す図である。ポインタ参照頻度解析部102の処理フローを示す図である。データ構造変換処理部103の処理フローを示す図である。コード生成処理部104の処理フローを示す図である。プログラム解析による、ポインタ参照頻度解析部102の処理フローを示す図である。ポインタの圧縮形式を、フィールド情報を用いて判定することを説明するための図である。プログラム形式別のポインタ圧縮表現を例示する図である。 big-endian計算機システムにおけるメモリ空間の構成を示す図である。ポインタの圧縮形式識別処理のフローを示す図である。圧縮形式のポインタを、実アドレスに変換する処理のフローを示す図である。フィールド情報1203を作成する処理のフローを示す図である。

符号の説明

101…言語処理系、 102…ポインタ参照頻度解析部
103…データ構造変換処理部 104…コード生成処理部
105…ソースプログラム 106…中間語
107…変換済プログラム 108…プロファイルデータ

Claims

ポインタによるデータ構造の参照機能を備えたプログラム又は計算機システムのポインタの圧縮・伸張方法において、
当該データ構造に含まれるポインタを、頻繁に参照されるポインタと、それ以外のポインタに分類し、
当該それ以外のポインタのみを圧縮し、参照の際に伸張する、ポインタの圧縮・伸張方法。
請求項1記載のポインタの圧縮・伸張方法において、前記分類は、予め作成されたプロファイルデータを用いて為される、ポインタの圧縮・伸張方法。
請求項1記載のポインタの圧縮・伸張方法において、前記伸張を行うか否かの制御は、前記ポインタ自体に格納された、ポインタ形式を判定するための情報を参照することによって為される、ポインタの圧縮・伸張方法。
請求項1記載のポインタの圧縮・伸張方法において、
前記頻繁に参照されるポインタ以外のポインタの値を、ベースアドレスからのオフセット値に指定する、ポインタの圧縮・伸張方法。
請求項1記載のポインタの圧縮・伸張方法において、前記分類は、前記計算機システムが、プログラムを解析することによって為され、
前記頻繁に参照されるポインタ以外のポインタが参照されるに際し、前記計算機システムが、当該ポインタの伸長を行うコードを生成する、ポインタの圧縮・伸張方法。
請求項３乃至５の何れか一項に記載のポインタの圧縮・伸張方法において、前記伸張を行うか否かの制御は、予め作成されたフィールド情報を用いて為される、ポインタの圧縮・伸張方法。
請求項３乃至５の何れか一項に記載のポインタの圧縮・伸張方法において、
前記プログラム又は計算機システムはbig-endian形式のデータ表現を使用するものであり、
前記ポインタのMSBにおいて、当該ポインタが圧縮形式である旨のビットが有れば、前記伸張が為される、ポインタの圧縮・伸張方法。
請求項３乃至５の何れか一項に記載のポインタの圧縮・伸張方法において、
前記プログラム又は計算機システムはlittle-endian形式のデータ表現を使用するものであり、
前記ポインタのLSBにおいて、当該ポインタが圧縮形式である旨のビットが有れば、前記伸張が為される、ポインタの圧縮・伸張方法。
請求項７記載のポインタの圧縮・伸張方法において、
前記伸張に際し、圧縮形式のポインタを非圧縮形式に変換するために用いるベースアドレスを、MSBの値だけシフトさせる、ポインタの圧縮・伸張方法。
ポインタによるデータ構造の参照を実行する計算機に、
当該データ構造に含まれるポインタを、頻繁に参照されるポインタと、それ以外のポインタに分類させる手順と、
当該それ以外のポインタのみを圧縮させ、参照の際に伸張させる手順と、
を実行させるポインタの圧縮・伸張プログラム。
請求項１０記載のポインタの圧縮・伸張プログラムにおいて、前記分類は、前記計算機に、プログラムを解析させることによって実行させ、
前記頻繁に参照されるポインタ以外のポインタを参照させるに際し、当該ポインタの伸長を行わせるコードを生成させることを実行させる、ポインタの圧縮・伸張プログラム。
ポインタによるデータ構造の参照機能を備えた計算機システムであって、
当該データ構造に含まれるポインタを、頻繁に参照されるポインタと、それ以外のポインタに分類し、
当該それ以外のポインタのみを圧縮し、参照の際に伸張する機能を有する、ポインタの圧縮・伸張機能を備えた計算機システム。
請求項１２記載のポインタの圧縮・伸張機能を備えた計算機システムにおいて、前記分類は、当該計算機システムが、プログラムを解析することによって為され、
前記頻繁に参照されるポインタ以外のポインタが参照されるに際し、前記計算機システムが、当該ポインタの伸長を行うコードを生成する機能を有する、ポインタの圧縮・伸張機能を備えた計算機システム。