perf(java): rolling min/max family runs 6-9x slower than C on a 100k random walk

[mario4tier]

Problem

The Java batch tier of the rolling min/max family (MIN, MAX, MINMAX, MIDPOINT, MIDPRICE, WILLR, the #147 Van Herk block scan) runs 6 to 9x slower than C on a 100k-bar random walk. MFI shows the same signature at 3x. Across the corpus Java batch is 1.13x C at the median, so these rows are the tail a Java user would notice, and the only place a JNI wrapper of the C library would beat the pure-Java jar.

Measurements

Host: laptop, AMD Ryzen 7 PRO 8840U (Zen 4), WSL2, OpenJDK 21.0.12. Not yet measured on the Intel devbox. C is the shipped CMake Release libta-lib.so; Java is the public Core tier from dev 745247fe5. One function per process, min of 25 rounds, best of 3 processes, period 14. Both arms produce identical output.

ns/bar:

function	C 1k	Java 1k	Java/C	C 100k	Java 100k	Java/C
MIN	0.74	2.48	3.3	0.79	7.31	9.3
MAX	0.80	2.20	2.8	0.79	7.43	9.4
MINMAX	1.52	4.02	2.6	1.64	14.01	8.6
MIDPOINT	1.52	3.97	2.6	1.59	13.53	8.5
MIDPRICE	1.52	4.06	2.7	1.63	14.03	8.6
WILLR	2.45	4.52	1.8	2.46	15.29	6.2
MFI	3.77	3.82	1.0	3.74	11.39	3.1
SMA (control)	1.27	1.28	1.0	1.34	1.33	1.0
BBANDS (control)	3.27	3.64	1.1	3.38	3.61	1.1

What the numbers say about the cause

• C's cost per bar is the same at both sizes. Java's triples from 1k to 100k. A 1k series replayed thousands of times lets the branch predictor memorize it; 100k bars cannot be memorized. So the gap is data-dependent control flow in the C2 output, where GCC compiles the same min/max to branch-free code. A benchmark on a short repeated series understates this gap by about 3x.
• Input shape confirms it (MIN, 100k): Java is 8.7 ns/bar on a random walk and 2.6 to 3.6 on constant or monotone input.
• Spelling alone does not fix it. a < b ? a : b and -XX:+UseCMoveUnconditionally both measure the same as the current code. Math.min reaches 4.9 to 5.8 ns/bar on a random walk and still gets faster on monotone input (1.9), so C2 is not branch-free there either.
• Math.min is not a drop-in anyway: it propagates NaN and orders -0.0 below 0.0, where the C min keeps the incumbent. Outputs must stay bit-identical to C.
• The streaming rescan does not help: Java MinStream.update is 9.1 ns/bar on the same input.
• A residual ~3x remains even with perfect prediction (2.6 vs 0.8 ns/bar), with an unidentified cause.

Deliverables

1. The C2 disassembly of MIN_Impl (hsdis) on a random walk, identifying what the hot loops pay for: branches, range checks, or missed vectorization.
2. A Java emission for the seven functions that gets the 100k random walk within 2x of C (proposed target), bit-identical to C including NaN and signed-zero inputs (--xlang-hash stays bitwise).
3. No regression at 1k bars or on the constant/monotone shapes.

Not this mechanism

SAR/SAREXT (1.3 to 1.4x) and TRANGE (~1.9x) are slower at both sizes alike, so the size-dependent signature above does not apply. Rows in the corpus-wide ta_bench pass that did not reproduce in isolation: IMI (1.15x), AD (1.0x). DIV, SQRT and TYPPRICE run about 2x faster in Java than the shipped .so.

[kevinlincg]

Reproduced on the Intel devbox side you had not measured yet — and with one finding about the measurement path that I think explains the rows you saw in the corpus pass but not in isolation.

Host. Intel Core i7-10700K (Comet Lake), macOS, Temurin 21.0.12.1 (same JDK minor as yours). C is the CMake Release static lib; both arms through bin/ta_bench --language=c,java, period 14, --iters=1000. Each row is the ratio of the minima of 5 repeated runs; the per-arm spread across those 5 is quoted so a row measured on a busy box is visible as one.

function	points	shape	Java/C	spread C / Java
MIN	100k	randwalk	4.52x	1.25x / 1.16x
MIN	1k	randwalk	2.69x	1.15x / 2.03x
MIN	100k	mono-up	1.73x	1.89x / 2.41x
MIN	100k	constant	2.11x	3.82x / 2.50x — C arm too noisy, direction only
SMA (control)	100k	randwalk	0.94x	1.31x / 1.73x
BBANDS (control)	100k	randwalk	1.12x	1.12x / 1.08x

Both controls land where yours do (you have 1.0 and 1.1), which is what makes the MIN row mean something rather than being my harness. The randwalk row reproduced at 4.51x in a separate 7-run batch before this one.

Both of your signatures reproduce, at lower amplitude. Size-dependent: 2.69x at 1k against 4.52x at 100k, C's per-bar cost flat across the two (bars x100, time x91.6) while Java's per-bar cost rises 5.3x. Shape-dependent: 4.52x on a random walk against 1.73x on a monotone ramp, same length, same code. So the mechanism you describe is visible on Comet Lake too — it is just 4.5x here rather than 9.3x on Zen 4, which I would attribute to the branch predictor rather than to anything in the emission.

The measurement path has a hole, and I fell in it first. My first number was 11.3x, and it was noise. At ta_bench's default --iters=100 the Java arm's run-to-run spread is 7.2x (5 repeats of the identical command: ratios 4.34, 5.26, 5.82, 8.56, 26.86). At --iters=1000 the spread drops to 1.16x and the ratio converges on 4.5. The three BENCH_PASSES and the min-keeping in ta_bench.c:305-329 are not enough on their own — at 100 iters the C2 compile is still landing inside the measured window.

What makes that invisible: the spread accounting is cref-only. g_spread_sum/_worst (ta_bench.c:242-244) is fed under strcmp(LANGUAGES[li].name, "cref") == 0 (ta_bench.c:334), so --max-spread — whose own comment says "the ratio columns below are only as meaningful as this is small" — never sees the Java, Rust or C arms. A Java row can swing 7x run to run and nothing in the tool says so. That is my candidate explanation for IMI (1.15x) and AD (1.0x) showing up in the corpus-wide pass and not reproducing in isolation.

Two things I can send as a separate PR if you want them, neither touching this issue's deliverables:

1. Track the spread per active arm instead of only cref, and have --max-spread fail on the worst arm. The control is the run above: at --iters=100 the Java arm must trip it and at 1000 it must not.
2. A note in --help that the Java arm needs --iters well above the default before its rows mean anything.

What I have not done: the hsdis/C2 disassembly in deliverable 1. I have not built hsdis on this host and have no reading of the compiled loop, so I have nothing to say about what it pays for — everything above is black-box timing.

[kevinlincg]

Sent the first of the two items above as #420 — per-arm spread accounting, so --max-spread fires on the worst arm rather than on cref alone. It does not touch this issue's deliverables.

The control run is the part worth a glance: at --language=c,java --max-spread=10 the old gate exits 0 with No C-ref column ... uncalibrated while the Java column is swinging 15% between passes, because with no cref arm there was nothing to accumulate. The new one exits 1 and names Java; at --iters=1000 the same binary exits 0 with Java at 3%.

[kevinlincg]

Correcting something I wrote above. In my first comment I said the cref-only spread accounting was my candidate explanation for IMI (1.15x) and AD (1.0x) appearing in the corpus-wide pass and not reproducing in isolation. That does not follow, and I should not have offered it.

Mario pointed out the underlying confusion on #420: ta_bench's spread figure measures variation between BENCH_PASSES inside one invocation. The IMI/AD discrepancy is between two separate invocations — run-to-run variance. Those are different quantities, and the gate's domain is the first one, so extending its coverage to every arm would not have flagged either row. The tool tracks nothing across invocations, for any arm.

What I wrote that does still hold, restated without the overreach:

• The accounting really was cref-only (ta_bench.c:334), so no arm's within-run spread but the reference's was ever checked. test(bench): watch every arm's spread, not only the reference #420 fixes that, and nothing more.
• The run-to-run figures I reported — the Java arm's 7.2x range over five identical commands at the default --iters, settling to 1.16x at --iters=1000 — are measurements of a quantity no gate in the tool watches, before or after test(bench): watch every arm's spread, not only the reference #420. That is why my first number on this issue was 11.3x and the settled one is 4.5x.

So the IMI/AD rows remain unexplained as far as I am concerned. If they are run-to-run, the same --iters effect would be the thing to check first — but I have not measured those two functions specifically and am not going to assert it.

[mario4tier]

Deliverable 1, answered by counting rather than by disassembly

Neither host has hsdis, so I attached hardware counters to the process instead. That settles the question deliverable 1 asks (branches, range checks, or missed vectorization) without a listing.

Host: laptop, AMD Ryzen 7 PRO 8840U (Zen 4), WSL2, OpenJDK 21.0.12. MIN, 100k bars, period 14, one function per process. The Java arm is the shipped Core.minImpl compiled from dev 48cd6e3 and driven directly in-process; the C arm is TA_MIN from the CMake Release libta-lib.a. Per-bar figures are counter deltas between two round counts (C: 600 minus 200, Java: 1200 minus 400), so JIT and startup cancel out.

arm	shape	ns/bar	instr/bar	branches/bar	mispredicts/bar	cycles/bar
C	randwalk	0.79	17.9	1.50	0.00004	3.66
C	monotone	0.87	17.9	1.50	0.00005	3.83
Java	randwalk	7.26	39.4	6.7	0.543	34.9
Java	monotone	2.86	34.4	5.0	~0	12.4
Java	constant	2.70	38.0	5.7	~0	12.2

The Java instruction count moves between 34 and 39 across repeats, because compiler and GC threads sit inside the counted process. The mispredict figure is stable to the third digit, and it is the one the conclusions rest on.

1. It is branches, and nothing else. C's compare-and-keep is branch-free, Java's is not: 0.543 mispredicts per bar against 0.00004. Instruction count is flat across the three shapes, so nothing but prediction changes with the data, and the mispredicts account for 22 of Java's 35 cycles per bar. That is the whole size- and shape-dependence in the issue body, now measured rather than inferred.

2. It is not missed vectorization. The C arm is not vectorized either, a running-min scan being loop-carried. Its 0.79 ns/bar is 17.9 instructions at 4.9 IPC. The Vector API is not the lever here.

3. Math.min is disqualified for a second and stronger reason. It is intrinsified at all three comparison sites (-XX:+PrintIntrinsics), and it still takes 0.398 mispredicts/bar, 45.4 instr/bar, 5.98 ns/bar. So the objection is not only that it propagates NaN and orders -0.0 below 0.0: C2 does not give branch-free min from it on this JDK. -XX:+UseCMoveUnconditionally does nothing either, at 7.74 ns/bar against a 6.8 to 7.5 band.

A candidate emission, measured

The three passes emitted as counted, x4-unrolled loops over a hoisted base, which is what TA_UNROLL(4) already gives the C arm and the Java emitter drops:

shape	base	unrolled	vs C
randwalk	7.26	7.14	9.0x
monotone	2.86	2.14	2.5x

Output checksum bit-identical to base. It buys ILP rather than fewer instructions, retiring slightly more, so it closes part of the residual and none of the tail.

Proposed re-scope of the deliverables

• D1 is answered. A disassembly is no longer the entry ticket. It is wanted now for exactly one open question: why the intrinsified Math.min still mispredicts. I have no reading of that and will not theorise without it.
• D2's "within 2x" is not reachable. 2x is 1.6 ns/bar; the best variant measured is 2.14 with zero mispredicts, and what is left is branch-free min, which C2 declines to emit. Proposed replacement: 2.5x on predictable input, with the random-walk tail recorded as a known cost rather than a target.
• D3 unchanged.

Over to you

@kevinlincg, three items, in the order we would spend them:

1. The counter signature on a second microarchitecture. Your 4.52x against our 9.3x is the branch predictor, and the table above is Zen 4 only. Mispredicts per bar for MIN at 100k, randwalk against monotone, on the i7-10700K would confirm or break the mechanism.
2. The unroll as a generator change. A Java TA_UNROLL equivalent plus counted-loop emission pays across the whole Java corpus rather than these seven functions, and --xlang-hash already gates the bit-identity. Say if you want it, otherwise we take it.
3. The disassembly for item D1 above, if you get an appetite for building hsdis.

Not release-blocking either way: 0.8.1 is a C release, and #172 does not list performance among the Maven Central blockers.