JP6193151B2 - 多分岐判断構文の最適化処理装置 - Google Patents

Description

本発明の実施形態は、多分岐判断構文の最適化処理装置に関する。

一般に、字句解析においては、まず処理すべき初めの文字を検査し、どのトークンを判定すればよいかを分けて、その後に詳細な判定を行っている。

リレーショナルデータベースマネジメントシステムでは、字句解析に要する処理時間の割合が小さいので、字句解析の処理速度は大きな問題とはならない。

しかし、いわゆるインメモリデータベースでは、Ｉ／Ｏ機器の処理速度も高速であるから、字句解析に要する処理時間の高速化が求められる。

字句解析で用いる多分岐判断構文ではジャンプテーブル（分岐先テーブル）が利用されることが多い。しかし、ジャンプテーブルでは、分岐先のアドレスをメモリからレジスタへロードするレジスタ間接ジャンプであるため、メモリを読むまで分岐先が決まらない。 このため分岐先の投機的実行ができず、結果として分岐前のパイプラインフラッシュ待ちやリロードのため時間を要し処理時間が長くかかるという問題があった。

特開平９−２８８５８１号公報 特開平７−１６０４９０号公報

本発明が解決しようとする課題は、投機的実行を上手く活用可能な多分岐判断構文の最適化処理装置を提供することである。

実施形態の多分岐判断構文の最適化処理装置は、トークンを含む多分岐判断構文を保持するメモリと、前記多分岐判断構文の最適化処理装置内に組み込まれるＣＰＵに依存するパラメータであって、多分岐判断処理に要する時間に基づいて設定するＣＰＵの能力情報と、予めソースコードを静的に分析し、字句解析するクエリの中で、出現頻度順に並び替えたトークンの種別と出現率を表した頻出字句表を保持するデータベース部と、前記ＣＰＵの能力情報と頻出字句表を参照して前記多分岐判断構文に対して判定を実行し、出現頻度の高いトークン種別では投機的実行可能な分岐をさせ、出現頻度の低いトークン種別ではジャンプテーブルを使用した分岐をさせるように変換した分岐コードを生成する変換部を備える。

投機的実行が可能／不可能な表現形式を説明する図である。 アセンブラレベルでのif-else型のswitch文とジャンプテーブルとの対比を説明する図である。 投機的実行による高速処理を説明する図である。 本発明の実施形態に係る多分岐判断構文の最適化処理装置の概略構成を示すブロック図である。 実施形態に係る多分岐判断構文の最適化処理装置における最適化処理の流れを示すフローチャートである。

以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。以下は本発明をSQLクエリの字句解析処理について実施した形態である。

まず、本実施形態で用いる主要な用語について説明する。

「字句解析」とは、プログラミング言語で記述されたプログラムを解析する処理であって、クエリ中の文字、スペース、記号を判別し、文字列をトークンに区切る作業をいう。

「構文解析」とは、プログラミング言語で記述されたプログラムを解析する処理であって、トークン列がプログラミング言語の文法に沿っているかを調べる処理をいう。

「クエリ」は、字句解析装置へ入力する文字列である。なお、以下では、クエリを構成する文字列中のアルファベットは大文字にあらかじめ統一しているものとする。

「トークン」とは、文字列の最小単位であって、構文解析装置が受理する予約語あるいは記号ＩＤ等をいう。トークンの種類には、他に、演算子、空白文字、テキスト、エスケープ、カッコ、コメント等がある。

「ジャンプテーブル」とは、分岐で用いる値に対して分岐先のアドレスが書いてある表をいう。

「投機的実行」：多分岐判断構文をコンパイルしてオブジェクトコードを生成する際の最適化処理の方法として、投機的実行がある。投機的実行は、プログラムが途中で分岐している場合に、分岐した先の処理を予め実行しておくことである。予測が当たっていれば処理の確定を待つことがないので、その分岐処理速度は高速化される。予測が外れたら投機的に実行された結果は破棄し、正しい分岐先の命令を実行する。

一般に、字句解析では、まず処理すべき初めの文字を検査して、どの種別のトークンを判定（例えば、アルファベットなのか数字なのか）すればよいかを分岐し、その後に詳細な判定（例えば、アルファベットであれば、“Ｓ”か“Ｆ”か等）を行っている。ここで、各トークン種別に対する分岐が発生する。

C言語などの手続き型プログラミング言語において、多分岐判断構文としてswitch 文がある。switch 文は、評価する変数の値に応じてその後の処理を異にするもので、コンパイラによって、ジャンプテーブルを用いた形に変換されることがある。後述するif-else 型の switch 文であれば、静的な分岐の連続なので、投機的実行が可能な表現形式である。図１は、投機的実行が可能／不可能な表現形式を説明する図である。図２は、アセンブラレベルでのif-else 型の switch 文とジャンプテーブルとの対比を説明する図である。図３は、投機的実行による高速処理を説明する図である。図３に示す例では、1億回、ほぼランダムに分岐するループを測定した場合を比較するもので、投機的実行の活用により処理時間が約３倍の差になっている。

本実施形態においては、投機的実行を有効なものとするため、字句解析におけるトークンの判断を行うswitch 文に対して、出現頻度の高いトークン種別では投機的実行可能な分岐をさせ、出現頻度の低いトークン種別ではジャンプテーブルを使用した分岐をするようにソースコードを変換する。

図４は、本発明の実施形態に係る多分岐判断構文の最適化処理装置の概略構成を示すブロック図である。この装置は汎用のコンピュータ（例えばパーソナルコンピュータ（ＰＣ）等）と、同コンピュータ上で動作するソフトウェアとを用いて実現される。コンピュータとしては、ＣＡＤ（Computer Aided Design）やＣＡＥ（Computer Aided Engineering）に好適なエンジニアリングワークステーション（ＥＷＳ）等も含む。本実施形態はこのようなコンピュータに、switch 文から出現頻度の高いトークン種別、分岐判定に係る一連の手続きを実行させるプログラムとして実施することもできる。

図４に示すように、本実施形態に係る多分岐判断構文の最適化処理装置は、主として、入力部１１、メモリ１２、データベース１３、変換部１４から構成されている。

入力部１１は、多分岐判断構文であるswitch 文を入力する。入力したswitch 文は、メモリ１２に保持される。メモリ１２に保持したswitch 文は、変換部１４に送られる。

データベース１３は、“ＣＰＵの能力情報”と“頻出字句表”を保持する。

ここで、ＣＰＵの能力情報とは、ＣＰＵ に依存するパラメータであって、多分岐判断処理に要する時間に基づいて設定する。ＣＰＵの能力情報＝ｎとおくと、ｎ回の比較命令の実行時間 ＝ジャンプテーブルのアクセス時間となるように決定する比較数である。

ｎの設定では、例えば、else 節が記述されている if 文であって、分岐の条件式が FALSE だった場合は else の直後に指定された文を実行するif−else 文による連続比較と、ジャンプテーブルを利用した場合を対比する。本発明者は、ＣＰＵとしてIntel社製の Core i7（登録商標）で実験した。それによれば、１５分岐の場合：if文による処理時間は１８７４ミリ秒であり、一方、ジャンプテーブルによる処理時間は１８９２ミリ秒で、ほぼ同等であった。１６分岐の場合：if文による処理時間は５３１ミリ秒であり、一方、ジャンプテーブルによる処理時間は８０４ミリ秒であった。さらに、３２分岐の場合：if文による処理時間は１１８４ミリ秒であり、一方、ジャンプテーブルによる処理時間は８７３ミリ秒であった。実験から、１６分岐までは、ジャンプテーブルによる処理の方が遅いことが分かった。以上のことから、ＣＰＵがIntel社製の Core i7（登録商標）の場合、ＣＰＵの能力情報＝ｎは、１６比較まで本実施形態による最適化の有効性判断に適しているということができる。

頻出字句表とは、字句解析するクエリの中で、どの字句が頻出するかを記述した表 (字句種類と確率のペア)である。例えば、ＳＱＬであれば、アルファベット、スペース、数字、＊、＋、−、 ( ) が頻出とする。

＜頻出字句表の決め方＞
一例として、次のＳＱＬクエリで説明する。頻出字句表は、予めソースコードを読み込んで静的に分析した結果を受けて作成する。

“SELECT FUNC(*) FROM TABLE WHERE COND(P+1)=1 AND X=Y”
予約語の出現回数:４回 (SELECT, FROM, WHERE, AND)
ＩＤの出現回数:６回 (FUNC, TABLE, COND, P, X, Y)
スペースの出現回数: ７回
()の出現回数: 合わせて４回
数字の出現回数：２回 (１が２回)
＝の出現回数：２回
＋の出現回数：１回
＊の出現回数：１回
したがって、この例では、トークンの総数は２７となる。

そして、トークン毎の出現率は、種別毎に以下のようになる。

アルファベットの出現率：３７％ (１０／２７)
スペースの出現率： ２６％ ( ７／２７)
（ ）の出現率: １５％ ( ４／２７)
数字の出現率： ７％（ ２／２７）
＝ の出現率： ７％ ( ２／２７)
＋の出現率： ３％ ( １／２７)
＊の出現率： ３％ ( １／２７)
したがって、出現頻度順は、アルファベット、スペース、( )、数字、＝、＋、＊となる。

次に、読み込んだソースコードにおいて、各トークンの種別を判定する場合を考える。例えば、ＡＳＣＩＩコードで表された文字が“アルファベット”であることを判定するには、“Ａ”以上で“Ｚ”以下であることを判定するため、計２回の比較が必要である。同様に、“数字”であることを判定するには、“０”以上“９”以下、２回の比較が必要である。また、“スペース”であることを判定するには、SQL 言語上における “スペース” がタブと改行コード２種類(キャリッジリターンCR、 ラインフィードLF) を含むため、４回の比較が必要である。したがって、出現頻度順に並べた頻出字句表からは、２回の比較判定で１個の種別（アルファベット）が判定可能であり、６回の比較判定で２個の種別（アルファベットとスペース）が判定可能である。上述した例では、頻出字句表における種別数は７となる。

本実施形態においては、巨大なswitch文のコンパイルにおいて、if−else型のswitch文として分岐させるのか、ジャンプテーブルを使用した分岐をさせるのが高速化できるかを、ＣＰＵの能力情報と頻出字句表を参照する。すなわち、ｎ−比較に消費する回数＝０になると、if−else型のswitch文として分岐させる方が遅くなる。換言すれば、出現頻度順に並べた頻出字句表からいくつかの種別を取り出し、それらの出現率の和がある閾値 (例えば６０％) を超えなかったら、高速化の効果は薄いことになる。

そこで、例えば、出現率の高いトークンからそれら出現率を累積した合計が６０％ を超えるまでの種別数をｍとする。上述した例では、アルファベットの出現率３７％とスペースの出現率２６％を合計すると６３％となるから、ｍの最小値は２となる。ＣＰＵの能力を表すｎがｍ以下であれば、if−else型のswitch文として分岐させることなく、ジャンプテーブルを使用した分岐をさせる方が高速となることを意味している。例えば、ＳＱＬ文の場合には、文字ｃを例にとると、ｃ＞＝‘Ａ’、ｃ＜＝‘Ｚ’、ｃ＝＝‘ ’を判定しないと出現率が稼げないから、ｍ は３以上となる。

変換部１４は、データベース１３に保持されているＣＰＵの能力情報と頻出字句表を参照しつつ、switch文を解析して、switch文から頻出するトークンの種別を抽出し、出現頻度の高いトークン種別では投機的実行可能な分岐をさせ、出現頻度の低いトークン種別ではジャンプテーブルを使用した分岐をさせるように変換した分岐コードを生成する。尚、この分岐コードは、いわゆる高級言語に限られず、コンパイラが解釈する中間コードであってもよい。

＜字句解析処理の流れ＞
次に、以上のように構成された多分岐判断構文の最適化処理装置１００における字句解析処理の流れについて説明する。

図５は、実施形態に係る多分岐判断構文の最適化処理装置１００における字句解析処理の流れを示すフローチャートである。上述したように、頻出するトークンの種別として、アルファベット、スペース、数字がある。そこで、これらをif文で判定していく。尚、予め小文字は大文字に変換しておく方が判定の際に好適である。

まず、if文でアルファベットを判定する（ステップＳ５１）。上述したように、アルファベットの特定には、３回の比較が必要である。

アルファベットであれば（ステップＳ５１でＹｅｓ）、続きの文字列と合わせて予約語を検索する（ステップＳ５２）。

予約語であれば（ステップＳ５２でＹｅｓ）、トークンの種類は予約語であると決定（ステップＳ５３）して、字句解析処理を終了する。予約語でなければ（ステップＳ５２でＮｏ）、トークンの種類はＩＤ名であると決定（ステップＳ５４）して、字句解析処理を終了する。

ステップＳ５１でアルファベットでなければ（ステップＳ５１でＮｏ）、if文で数字を判定する（ステップＳ５５）。数字の特定には、ｃ＞＝‘０’、ｃ＜＝‘９’の２回の比較が必要である。

数字であれば（ステップＳ５５でＹｅｓ）、続きの文字列が数字か否かを判定（ステップＳ５６）して、字句解析処理を終了する。

ステップＳ５５で数字でなければ（ステップＳ５５でＮｏ）、if文で空白文字を判定する（ステップＳ５７）。

空白文字であれば（ステップＳ５７でＹｅｓ）、空白が続く間、入力を読み飛ばし（ステップＳ５８）て、字句解析処理を終了する。

ステップＳ５７で空白文字でなければ（ステップＳ５７でＮｏ）、if−else型のswitch文で頻出字句を判定する（ステップＳ５９）。

頻出字句であれば（ステップＳ５９でＹｅｓ）、各字句に応じた処理を行った（ステップＳ６０）後、字句解析処理を終了する。上述の例で言えば、( )、＝などの特定である。

ステップＳ５９で頻出字句でなければ（ステップＳ５９でＮｏ）、ジャンプテーブルのswitch文で頻出でない字句を判定する（ステップＳ６１）。

字句であれば（ステップＳ６１でＹｅｓ）、各字句に応じた処理を行った（ステップＳ６０）後、字句解析処理を終了する。字句でなければ（ステップＳ６１でＮｏ）、エラーであり、字句解析処理を終了する。

＜最適化の効果＞
本実施形態による最適化の効果を、SQLite の字句解析ルーチンと比較した。SQLite の字句解析では、演算子、特殊記号の判定に switch 文を使用しており、分岐のcase が43個である。default 部で予約語とID名を判定し、文脈判定は構文解析器に任せている。

次のＳＱＬ文を100万回字句解析し、時間を測定した。

‘SELECT FUNC(*) FROM TABLE WHERE COND(P+1)=1 AND X=Y’
字句解析は、アルファベット、スペース、数字、 ( )、 ＝、＊、＋ を先に判定し、その他をジャンプテーブルで判定した。ＣＰＵは、Intel Core i7（登録商標）で、ｎ＝１６とした。

その結果、SQLiteの字句解析ルーチンでは５９７ミリ秒であった。一方、本実施形態によれば３８１ミリ秒で、約３６％速度が向上している。

以上説明したように、本実施形態によれば、投機的実行を上手く活用可能な多分岐判断構文を最適化することにより、字句解析の高速化が図られる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１００・・・多分岐判断構文の最適化処理装置
１１・・・入力部
１２・・・メモリ
１３・・・データベース
１４・・・変換部

Claims (4)

1. トークンを含む多分岐判断構文を保持するメモリと、
   前記多分岐判断構文の最適化処理装置内に組み込まれるＣＰＵに依存するパラメータであって、多分岐判断処理に要する時間に基づいて設定するＣＰＵの能力情報と、
   予めソースコードを静的に分析し、字句解析するクエリの中で、出現頻度順に並び替えたトークンの種別と出現率を表した頻出字句表を保持するデータベース部と、
   前記ＣＰＵの能力情報と頻出字句表を参照して前記多分岐判断構文に対して判定を実行し、出現頻度の高いトークン種別では投機的実行可能な分岐をさせ、出現頻度の低いトークン種別ではジャンプテーブルを使用した分岐をさせるように変換した分岐コードを生成する変換部を備える多分岐判断構文の最適化処理装置。
2. 前記多分岐判断構文は、switch 文であり、前記投機的実行可能な分岐は、if−else型のswitch 文による分岐である請求項１記載の多分岐判断構文の最適化処理装置。
3. 前記分岐コードは、コンパイラが解釈する中間コードである請求項１又は請求項２に記載の多分岐判断構文の最適化処理装置。
4. トークンを含む多分岐判断構文を蓄積した第１ファイルと、
   ＣＰＵに依存するパラメータであって、多分岐判断処理に要する時間に基づいて設定するＣＰＵの能力情報を蓄積した第２ファイルと、
   予めソースコードを静的に分析し、字句解析するクエリの中で、出現頻度順に並び替えたトークンの種別と出現率を表した頻出字句表を蓄積したデータベースファイルとを含んでおり、
   コンピュータに、前記ＣＰＵの能力情報と頻出字句表を参照して前記多分岐判断構文に対して判定を実行し、出現頻度の高いトークン種別では投機的実行可能な分岐をさせ、出現頻度の低いトークン種別ではジャンプテーブルを使用した分岐をさせるように変換した分岐コードを生成させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。

Images