72

JavaバイトコードでLookUpSwitchとTableSwitchを理解するのが難しいです。

私がよく理解している場合、LookUpSwitchとTableSwitchの両方switchがJavaソースのステートメントに対応していますか？1つのJAVAステートメントが2つの異なるバイトコードを生成するのはなぜですか？

それぞれのJasminドキュメント：

4

4 に答える 4

113

違いは、

  • lookupswitchは、キーとラベルを持つテーブルを使用します
  • tableswitchは、ラベルのみを持つテーブルを使用します。

テーブルスイッチを実行すると、スタックの一番上の int 値がテーブルへのインデックスとして直接使用され、ジャンプ先を取得してすぐにジャンプを実行します。全体のルックアップ + ジャンプ プロセスはO(1) 操作です。つまり、非常に高速です。

lookupswitchを実行すると、一致が見つかるまでスタックの一番上の int 値がテーブル内のキーと比較され、その後、このキーの隣にあるジャンプ先がジャンプの実行に使用されます。ルックアップスイッチ テーブルは常に、X < Y ごとに keyX < keyY になるように並べ替える必要があるため、ルックアップ + ジャンプ プロセス全体はO(log n) 操作です。キーは二分探索アルゴリズムを使用して検索されるため (int 値をすべての可能なキーと比較して、一致を見つけたり、一致するキーがないと判断したりする必要はありません)。O(log n) は O(1) よりもやや遅いですが、よく知られているアルゴリズムの多くは O(log n) であり、これらは通常高速であると見なされているため、それでも問題ありません。O(n) または O(n * log n) でさえ、依然として非常に優れたアルゴリズムと見なされます (遅い/悪いアルゴリズムには O(n^2)、O(n^3)、またはそれ以上のものがあります)。

どの命令を使用するかは、switch ステートメントがどれほどコンパクトかという事実に基づいて、コンパイラによって決定されます。

switch (inputValue) {
  case 1:  // ...
  case 2:  // ...
  case 3:  // ...
  default: // ...
}

上記のスイッチは完全にコンパクトで、数字の「穴」はありません。コンパイラは、次のようなテーブルスイッチを作成します。

 tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

Jasmin ページの疑似コードは、これを非常によく説明しています。

int val = pop();                // pop an int from the stack
if (val < low || val > high) {  // if its less than <low> or greater than <high>,
    pc += default;              // branch to default 
} else {                        // otherwise
    pc += table[val - low];     // branch to entry in table
}

このコードは、そのようなテーブルスイッチがどのように機能するかについて非常に明確です。valはinputValue、low1 (スイッチの最小値) とhigh3 (スイッチの最大値) になります。

いくつかの穴があっても、スイッチはコンパクトにできます。

switch (inputValue) {
  case 1:  // ...
  case 3:  // ...
  case 4:  // ...
  case 5:  // ...
  default: // ...
}

上のスイッチは「ほぼコンパクト」で、穴が 1 つしかありません。コンパイラは次の命令を生成できます。

 tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

  ; <...code left out...>

  FakeTwoLabel:
  DefaultLabel:
    ; default code

ご覧のとおり、コンパイラは 2 の偽のケースを追加する必要がありますFakeTwoLabel。2 はスイッチの実際の値ではないため、2 の値はFakeTwoLabel実際にはデフォルト ケースを実行する必要があるため、実際にはデフォルト ケースが配置されているコード フローを正確に変更するラベルです。

そのため、コンパイラがテーブルスイッチを作成するために、スイッチは完全にコンパクトである必要はありませんが、少なくともコンパクトに近いものにする必要があります。ここで、次のスイッチを検討してください。

switch (inputValue) {
  case 1:    // ...
  case 10:   // ...
  case 100:  // ...
  case 1000: // ...
  default:   // ...
}

このスイッチはコンパクトとは言えません。値の 100 倍以上の穴があります。これはスパース スイッチと呼ばれます。コンパイラは、このスイッチをテーブルスイッチとして表現するために、ほぼ千の偽のケースを生成する必要があります。その結果、巨大なテーブルが作成され、クラス ファイルのサイズが劇的に増加します。これは実用的ではありません。代わりに、lookupswitch を生成します。

lookupswitch
    1       : Label1
    10      : Label10
    100     : Label100
    1000    : Label1000
    default : DefaultLabel

このテーブルには、1000 を超えるエントリではなく、5 つのエントリしかありません。テーブルには 4 つの実数値があり、O(log 4) は 2 です (log はここでは 2 BTW を底とする対数であり、コンピューターは 2 進数で動作するため、10 を底とするものではありません)。つまり、VM が inputValue のラベルを見つけるか、値がテーブルにないためデフォルト値を実行する必要があるという結論に達するまでに、最大 2 回の比較が必要です。テーブルに 100 のエントリがあったとしても、VM が正しいラベルを見つけるか、デフォルト ラベルにジャンプすることを決定するには、最大で 7 回の比較が必要です (そして、7 回の比較は 100 回の比較よりもはるかに少ないと思いませんか?)。

したがって、これら 2 つの命令が交換可能であるとか、2 つの命令の理由に歴史的な理由があるというのはナンセンスです。2 つの異なる状況に対応する 2 つの命令があります。1 つはコンパクトな値を持つスイッチ (最大速度) 用で、もう 1 つはスパース値を持つスイッチ (最大速度ではありませんが、数値の穴に関係なく良好な速度と非常にコンパクトなテーブル表現) です。

于 2012-10-17T15:46:33.377 に答える
19

javac1.8.0_45 はどのようにコンパイルするかを決定しますswitchか?

どちらをいつ使用するかを決定するには、javac選択アルゴリズムを基礎として使用できます。

javacのソースがリポジトリにあることがわかっていlangtoolsます。

次に grep します。

hg grep -i tableswitch

最初の結果はlangtools/src/share/classes/com/sun/tools/javac/jvm/Gen.javaです:

// Determine whether to issue a tableswitch or a lookupswitch
// instruction.
long table_space_cost = 4 + ((long) hi - lo + 1); // words
long table_time_cost = 3; // comparisons
long lookup_space_cost = 3 + 2 * (long) nlabels;
long lookup_time_cost = nlabels;
int opcode =
    nlabels > 0 &&
    table_space_cost + 3 * table_time_cost <=
    lookup_space_cost + 3 * lookup_time_cost
    ?
    tableswitch : lookupswitch;

どこ：

  • hi: 最大ケース値
  • lo: 最小ケース値

したがって、時間と空間の複雑さの両方を考慮しており、時間の複雑さの重みは3であると結論付けます。

TODO二分探索を使用して O(log(n)) で実行できるため、理由がわかりませんlookup_time_cost = nlabels。log(nlabels)tableswitch

ボーナス事実: C++ コンパイラも、O(1) ジャンプ テーブルと O(long(n)) 二分探索の間で同様の選択を行います: if-else ステートメントの切り替えの利点

于 2015-06-24T16:29:23.090 に答える
6

Java Virtual Machine Specificationに違いが説明されています。「tableswitch 命令は、スイッチのケースがターゲット オフセットのテーブルへのインデックスとして効率的に表現できる場合に使用されます。」詳細については、仕様書を参照してください。

于 2012-05-17T07:23:13.060 に答える
0

Javaバイトコードが基盤となるマシンコード（Sun自身のCPUなど）に特定にバインドされているため、これはほとんど歴史的なものだと思います。

これtableswitchは基本的に計算されたジャンプであり、宛先はルックアップテーブルから取得されます。対照的に、lookupswitch各値の比較が必要です。基本的には、一致する値が見つかるまでテーブル要素を反復処理します。

明らかに、これらのオペコードは交換可能ですが、値に基づいて、どちらかがより高速またはよりコンパクトになる可能性があります（たとえば、間に大きなギャップがあるキーのセットとシーケンシャルなキーのセットを比較します）。

于 2012-04-23T20:38:29.767 に答える