20

配列がビットごとの and を介して計算されるときに境界チェックを排除できるかどうかを調べるために、簡単なベンチマークを作成しました。これは基本的に、ほぼすべてのハッシュ テーブルが行うことです。

h & (table.length - 1)

へのインデックスとして、tableはhまたはhashCode派生値です。結果は、境界チェックが排除されていないことを示しています。

私のベンチマークの考え方は非常に単純です。2 つの値iと を計算jします。両方とも有効な配列インデックスであることが保証されています。

  • iループカウンターです。配列インデックスとして使用されると、境界チェックがなくなります。
  • jとして計算されます。x & (table.length - 1)ここで、xは反復ごとに変化する値です。配列インデックスとして使用される場合、境界チェックは排除されません。

関連する部分は次のとおりです。

for (int i=0; i<=table.length-1; ++i) {
    x += result;
    final int j = x & (table.length-1);
    result ^= i + table[j];
}

他の実験では

    result ^= table[i] + j;

代わりは。タイミングの違いはおそらく 15% です (私が試したさまざまなバリアントでほぼ一貫しています)。私の質問:

  • これには、バウンドチェックの排除以外に考えられる理由はありますか?
  • バウンドチェックの削除がない理由がわからない複雑な理由がありますjか?

回答の要約

MarkoTopolnik の答えは、それがすべてより複雑であり、境界チェックの排除が勝利であるとは限らないことを示しています。特に彼のコンピューターでは、「通常の」コードは「マスクされた」コードよりも遅くなります。これは、この場合実際に有害であることが示されている追加の最適化を許可しているためだと思います（現在のCPUの複雑さを考えると、コンパイラーは確実に知ることさえほとんどありません）。

leventovの答えは、配列の境界チェックが「マスク」で行われ、それを排除することでコードが「通常」と同じくらい高速になることを明確に示しています。

x & (0-1)Donal Fellows は、長さが 0 のテーブルではマスキングが機能しないという事実を指摘していますx。したがって、コンパイラが実行できる最善の方法は、バウンド チェックを長さ 0 のチェックに置き換えることです。しかし、長さゼロのチェックはループから簡単に移動できるため、これはまだ価値があります。

提案された最適化

a[x & (a.length - 1)]if and only ifの等価スローa.length == 0により、コンパイラは次のことを実行できます。

  • 配列アクセスごとに、インデックスがビットごとの and を介して計算されているかどうかを確認します。
  • その場合、いずれかのオペランドが長さから 1 を引いたものとして計算されたかどうかを確認してください。
  • その場合は、境界チェックを長さゼロのチェックに置き換えます。
  • 既存の最適化に任せましょう。

このような最適化は、SSAグラフの親ノードのみを参照するため、非常にシンプルで安価です。多くの複雑な最適化とは異なり、1 つのチェックをわずかに単純なチェックに置き換えるだけなので、有害になることはありません。そのため、ループの外に移動できなくても問題はありません。

これを hotspot-dev メーリング リストに投稿します。

ニュース

John Rose がRFEを提出し、すでに「簡単な」パッチがあります。

4

3 に答える 3

5

まず、2 つのテストの主な違いは、間違いなく境界チェックの排除にあります。ただし、これがマシン コードに与える影響は、単純な予想が示唆するものとはかけ離れています。

私の推測:

境界チェックは、オーバーヘッドを導入する追加のコードとしてよりも、ループの出口点としてより強く考慮されます。

ループの終了点は、出力されたマシン コードから抜粋した次の最適化を防ぎます。

  • ループが展開されます (これはすべての場合に当てはまります)。
  • さらに、配列ステージからのフェッチは、すべてのアンロールされたステップに対して最初に行われ、次にアキュムレータへの xorがすべてのステップに対して行われます。

ループがどのステップでも発生する可能性がある場合、このステージングにより、実際には実行されなかったループ ステップに対して実行される作業が発生します。

コードのこのわずかな変更を検討してください。

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.N)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(1)
 public class Measure {
  public static final int N = 1024;

  private final int[] table = new int[N];
  @Setup public void setUp() {
    final Random random = new Random();
    for (int i = 0; i < table.length; ++i) {
      final int x = random.nextInt();
      table[i] = x == 0? 1 : x;
    }
  }
  @GenerateMicroBenchmark public int normalIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }
  @GenerateMicroBenchmark public int maskedIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[j];
      result ^= i + entry;
      if (entry == 0) break;
    }
    return result;
  }
}

違いは1つだけです。チェックを追加しました

if (entry == 0) break;

ループが任意のステップで途中で終了する方法を提供します。(また、配列エントリが実際に 0 にならないようにするためのガードも導入しました。)

私のマシンでは、これが結果です：

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.378        0.229    ns/op
o.s.Measure.normalIndex     avgt         5        0.924        0.092    ns/op

「通常のインデックス」バリアントは、一般的に予想されるように、大幅に高速です。

ただし、追加のチェックを削除しましょう。

// if (entry == 0) break;

今私の結果はこれらです：

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.130        0.065    ns/op
o.s.Measure.normalIndex     avgt         5        1.229        0.053    ns/op

「マスクされたインデックス」は予想どおりに応答しましたが (オーバーヘッドが削減されました)、「通常のインデックス」は突然大幅に悪化しました。これは明らかに、追加の最適化ステップと特定の CPU モデルとの適合が悪いためです。

私のポイント：

このような詳細なレベルでのパフォーマンス モデルは非常に不安定であり、私の CPU で見られるように不安定ですらあります。

于 2014-02-12T09:19:59.637 に答える
1

その境界チェックを安全に排除するには、次のことを証明する必要があります。

h & (table.length - 1)

への有効なインデックスを生成することが保証さtableれています。table.lengthがゼロの場合はそうではありません（& -1効果的なヌープになるため）。また、 が 2 の累乗でない場合も有効ではありません (情報が失われます。が 17table.lengthの場合を考えてください)。table.length

HotSpot コンパイラは、これらの悪い条件が真ではないことをどのように知ることができますか? プログラマーはシステムの高レベルの制約についてより多くのことを知ることができるため、プログラマーよりも保守的である必要があります (たとえば、配列は決して空ではなく、常に要素の数としてのべき乗であるなど)。 2）。

于 2014-02-12T08:15:40.730 に答える