david-mollitor-db opened a new pull request, #58284:
URL: https://github.com/apache/spark/pull/58284
### What changes were proposed in this pull request?
Migrate the production `BinaryType` comparison call sites off the hand-rolled
word-at-a-time `ByteArray.compareBinary(byte[], byte[])` onto the
`java.util.Arrays.compareUnsigned(byte[], byte[])` intrinsic, which the JIT
compiles to
vectorized (SIMD) code on JDK 9+:
- **`CodegenContext.genComp`** (`case BinaryType`) — the generated
row/ordering comparators
used by `GenerateOrdering` (ORDER BY, sort-merge join keys, array/map
element comparison).
- **`PhysicalBinaryType.ordering`** — the interpreted
`Ordering[Array[Byte]]`.
This mirrors the sibling `genComp`/`genEqual` path, which already emits
`java.util.Arrays.equals` for `BinaryType`, so it extends an existing
pattern.
The now-unused 2-arg `ByteArray.compareBinary(byte[], byte[])` overload is
retained as a
benchmark baseline, with a JavaDoc pointing callers to
`Arrays.compareUnsigned`. The off-heap
overload (base object + offset) is unchanged and still used by `UTF8String`
/ `BinaryView`.
`ByteArrayBenchmark` gains an old-vs-intrinsic A/B case per size bucket.
### Why are the changes needed?
`Arrays.compareUnsigned` is a JDK intrinsic that vectorizes the comparison,
and it is faster than
the hand-rolled `Unsafe` word-at-a-time loop for the realistic `BinaryType`
value range
(hashes, UUIDs, digests, blobs, i.e. `>= 8` bytes). It is also simpler and
less error-prone than
maintaining a bespoke comparison, and it matches the intrinsic already used
on the equality path.
**Semantics are unchanged.** The previous implementation compared bytes as
unsigned (`& 0xFF`) and
returned the length difference on a common prefix — exactly
`Arrays.compareUnsigned`'s contract.
The returned magnitude on a mismatch may differ, but the sign is identical,
and all callers are
`Ordering`s that only use the sign.
### Does this PR introduce _any_ user-facing change?
No.
### How was this patch tested?
Existing tests, unmodified, validate the unchanged semantics:
- `OrderingSuite` (catalyst) — including "SPARK-21344: BinaryType comparison
...", which asserts
`compare(Array(1), Array(-1)) < 0` (unsigned). Exercises the generated
comparator with the new
intrinsic.
- `ByteArraySuite` (common/unsafe) — `testCompareBinary` unsigned assertions.
Performance was measured with the updated `ByteArrayBenchmark` (old
hand-rolled
`ByteArray.compareBinary` vs the `java.util.Arrays.compareUnsigned`
intrinsic). Best time in ms,
lower is better; speedup = old / intrinsic. Measured locally on an AWS box,
so treat the absolute
numbers as indicative and the ratios as the takeaway.
OpenJDK 17.0.20:
| Input size | `compareBinary` (ms) | `Arrays.compareUnsigned` (ms) |
Speedup |
|---------------|----------------------|-------------------------------|---------|
| 2-7 byte | 188 | 228 |
0.82x |
| 8-16 byte | 449 | 209 |
2.15x |
| 16-32 byte | 466 | 216 |
2.16x |
| 512-1024 byte | 611 | 433 |
1.41x |
| 512 byte slow | 1599 | 1183 |
1.35x |
OpenJDK 21.0.12:
| Input size | `compareBinary` (ms) | `Arrays.compareUnsigned` (ms) |
Speedup |
|---------------|----------------------|-------------------------------|---------|
| 2-7 byte | 188 | 216 |
0.87x |
| 8-16 byte | 371 | 199 |
1.86x |
| 16-32 byte | 368 | 198 |
1.86x |
| 512-1024 byte | 485 | 442 |
1.10x |
| 512 byte slow | 1684 | 1288 |
1.31x |
The intrinsic wins for all input sizes `>= 8` bytes, with the largest gains
in the 8-32 byte
range. "512 byte slow" is the worst case where both arrays differ only in
the last byte, forcing a
full-length scan. The only regression is sub-8-byte arrays (~13-18% slower):
for anything under
8 bytes, `Arrays.compareUnsigned` falls back to a byte-at-a-time loop (no
full 8-byte word to
vectorize over), which is exactly the regime the hand-rolled word-at-a-time
comparison was
designed for. Since realistic `BinaryType` values are `>= 8` bytes, the
vectorized path dominates
in practice.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Code (Opus 4.8)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
