java - 奇妙な分岐パフォーマンス

Question

私のベンチマークの結果は、分岐の確率が 50% ではなく 15% (または 85%) の場合にパフォーマンスが最悪であることを示しています。

説明はありますか？

コードは長すぎますが、関連する部分は次のとおりです。

private int diff(char c) {
    return TABLE[(145538857 * c) >>> 27] - c;
}

@Benchmark int timeBranching(int reps) {
    int result = 0;
    while (reps-->0) {
        for (final char c : queries) {
            if (diff(c) == 0) {
                ++result;
            }
        }
    }
    return result;
}

指定された文字列内のBREAKING_WHITESPACE文字の数をカウントします。結果は、分岐確率が約 0.20 に達すると、急激な時間の低下 (パフォーマンスの向上) を示しています。

ドロップの詳細。シードを変化させると、より奇妙なことが起こっていることがわかります。崖の近くを除いて、最小値と最大値を示す黒い線が非常に短いことに注意してください。

Answer 1

マイナーな JIT バグのようです。分岐確率が小さい場合、次のようなものが生成されますが、展開が原因でさらに複雑になります (かなり単純化しています)。

movzwl 0x16(%r8,%r10,2),%r9d

文字を取得します。int r9d = queries[r10]

imul   $0x8acbf29,%r9d,%ebx

かける：ebx = 145538857 * r9d

shr    $0x1b,%ebx

シフト：ebx >>>= 27

cmp    %edx,%ebx
jae    somewhere

境界を確認してください: if (ebx > edx || ebx < 0) goto somewhere(そしてそこにIndexOutOfBoundsException.

cmp    %r9d,%ebx
jne    back

等しくない場合は、ループの先頭に戻ります。if (r9d != ebx) goto back

inc    %eax

結果をインクリメントします。eax++

jne    back

単にgoto back

1 つのスマートなものと 1 つのばかげたものを見ることができます。

• バウンド チェックは、1 回の符号なし比較で最適に実行されます。
• x >>> 27 は常に正で、テーブルの長さ (32) より小さいため、完全に冗長です。

分岐確率が 20% を超える場合、これら 3 つの命令は

cmp    %r9d,%ebx
jne    back
inc    %eax

のようなものに置き換えられます

mov    %eax,%ecx   // ecx = result
inc    %ecx        // ecx++
cmp    %r9d,%ebx   // if (r9b == index)
cmoveq %ecx,%ebx   //    result = ecx

条件付き移動命令を使用します。これは 1 命令多くなりますが、分岐がないため、分岐予測ミスのペナルティはありません。

これは、20 ～ 80% の範囲で時間が非常に一定であることを説明しています。20% を下回る上昇は、明らかに分岐の予測ミスによるものです。

したがって、0.18 ではなく約 0.04 の適切なしきい値を使用するのは、JIT の失敗のように見えます。