Two-input merges with many equal keys are 11-19% slower since #7

perfloop-oss/kway-go · Uncatalogued performance

https://perfloop.ai/t/oss/case_zfxz19a84b

Verdict

VERIFIED · settled 2026-11-04 · pull request opened as achille-roussel/kway-go#8

What happened: The paired measurements met the required improvement.

Hypothesis

Two-input batched merges may spend more time on equal keys after comparison results were cached. The submitter reports an 11–19% slowdown with a cheap integer comparator, despite fewer comparisons. This could affect callers merging duplicate-rich sorted batches; the timings, precise cause, and consumer prevalence remain unconfirmed.

The source subject is merge2 at merge.go:223–627. MergeSliceFunc is a documented library operation for sorted slice iterators (README.md:25–32; merge.go:155–169), and its two-input branch directly calls merge2 at merge.go:165. The implementation separates an equal-head loop at merge.go:246–281, an unequal-winner loop at merge.go:343–392, and a cached-comparison loop at merge.go:393–599. Failed lookaheads and gallop boundaries supply comparison signs that reenter the decision through the cached label (merge.go:462–477, 520–535, 552–564). The submitted mechanism is extra per-iteration tie-loop overhead from this restructuring, not additional comparator calls; its exact generated-code cause is still a question.

The submitter reports interleaved base 03efeb5 / head 09f03c9 pairs, using the same test file on both arms. Each merge consumed two sources of 8192 sorted random integers in [0,R), in batches of 128, using cmp.Compare[int]. Their reported per-merge results are: - R=4: 59.4 → 66.9 microseconds (+12.7%). - R=16: 60.7 → 72.4 microseconds (+19.3%). - R=64: +14.7%. - R=256: +17.9%. - R=1024: +11.4%.

They report the slowdown in 11–12 of 12 pairs for each of those ranges. A separate n=20 run reportedly gave +11.65%, with head slower in 18/20 comparisons. R=8192, described as having few ties, reportedly showed no change. They also report identical outputs over 40k differential cases. Comparator calls reportedly fell 0–6.7% at head. In their R=16 profile, time attributed to the comparator closure increased from 480 to 740 ms despite fewer calls. These are attributed reports for the Case to check, not measurements acquired in this run. Worse code generation from the larger merge2 is one suggested explanation, not an established cause.

The complete requested outcome also retains #7's gains on alternating runs and expensive comparators. The submitter reports MergeSliceAlternatingRuns with bytes.Compare at -7% to -18%, all-equal keys at -19%, and random integers at -7.9%; those gains must be kept rather than trading them away to improve mixed, tie-heavy inputs. These are distinct regression-control workloads, not evidence of the benefiting cheap-comparator workload's cost. The existing alternating-runs benchmark uses two one-batch byte-key inputs (merge_test.go:1162–1224). TestMergeSliceAlternatingRunComparisons checks comparison counts in both winner directions (merge_test.go:517–567), and TestMergeSliceCachedComparisons covers tie order and batch boundaries (merge_test.go:569–664). Both focused tests passed on the unchanged checkout in this run; that establishes neither the slowdown nor the reported gains. The requested new tie-heavy benchmark and full go test -race ./... remain Case work.

Upstream overlap is https://github.com/achille-roussel/kway-go/pull/7, “Cache merge comparator boundary results.” The current provider record confirms it was merged by the owner at 09f03c94401894397b0d6e20350ed9d653151a66, the accepted HEAD, from base 03efeb5e0449000479e0f55f1ac7b8f028bc1893 and PR head 7a7a4969eb8cd9d40fc7058db18dbc0a1194f7a1. Its inspected patches implement the cached signs and add the comparison tests and alternating-runs benchmarks. This report is a regression investigation of that merged implementation while preserving its benefits, not a request to repeat its comparison-count reduction. The current complete open-PR page returned no candidates; #7's discussion returned no comments, and its inspected body linked no separate issue. Those observations do not establish that no other upstream evidence exists or that maintainers have agreed to a particular repair.

The smallest useful next check is a paired base/head end-to-end benchmark with the reported 8192-element sources, 128-element batches, cheap comparator, and key-range sweep, recording merge time separately from comparator counts and checking outputs. A reproducible time increase without more comparisons would support the proposed overhead; absence of that signal would weigh against it on the measured setup. If it reproduces, a focused R=16 profile and generated-code comparison can distinguish loop-state cost from comparator code generation before a broad implementation. The exact base is not present in this checkout's local history and must be obtained before the paired comparison. The submitter's CPU and Go version are unspecified. The proposed scalar Go control-flow work has no ISA-extension or CPU-generation requirement; timing conclusions must retain the actual measured environment rather than imply a universal speedup. No named consumer, production input distribution, or operation cadence has been established.

Change to test: Remove the tie-heavy per-iteration overhead in merge2 while keeping cached-sign gains on alternating runs and expensive comparators, for example by using the cached path only when it skips a comparison or keeping ties in a tight loop. Add a cheap-comparator two-input tie-heavy benchmark beside BenchmarkMergeSliceAlternatingRuns, preserve the reported alternating-byte, all-equal-key and random-integer gains, keep TestMergeSliceAlternatingRunComparisons and TestMergeSliceCachedComparisons passing, and run go test -race ./... .

Where it lives

perfloop-oss/kway-go · merge.go

Evidence

MergeSliceFunc duplicate integers · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 62456 51218 −18.6% (−11591) −14084 to −10005 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc duplicate integers · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 66661 52041 −22.5% (−15013) −16950 to −12219 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc duplicate integers · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 69182 54894 −20.8% (−14396) −17937 to −12139 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc duplicate integers · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 74721 61126 −18.2% (−13577) −15093 to −11430 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc duplicate integers · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 91305 79556 −12.8% (−11712) −14808 to −8772 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc equal integers · 36 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 49622 50942 +2.5% (+1243) +213 to +2220 loss ≤ 0.05 × |baseline median| PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc random integers · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 155897 156476 +807 −7428 to +4714 loss ≤ 0.05 × |baseline median| PASSED
B/op 2504 2504 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 329 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 17406 18064 +3.6% (+621) +398 to +861 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 18 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 38274 37049 −1398 −3008 to +523 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 87 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 88242 90325 +2357 −57 to +4227 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 47 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 140781 142618 +1548 −4103 to +6478 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 54 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 174736 175959 +1730 −4087 to +7986 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 37 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 215660 216288 −1353 −7899 to +10029 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

MergeSliceFunc alternating byte runs · 18 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 297709 295576 −1299 −15673 to +10544 loss ≤ 0.05 × |baseline median| PASSED
B/op 6984 6984 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 19 19 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

Checks: 2 of 2 passed. Verification: no defect found.

Timeline