David Mollitor created SPARK-59062:
--------------------------------------
Summary: Word-at-a-time single-byte search for UTF8String.contains
Key: SPARK-59062
URL: https://issues.apache.org/jira/browse/SPARK-59062
Project: Spark
Issue Type: Improvement
Components: Spark Core
Affects Versions: 4.1.0
Reporter: David Mollitor
h2. Summary
{{UTF8String.contains}} searches for a substring by scanning one byte at a
time. For a
single-byte needle -- the common case produced by {{LIKE '%x%'}} (which the
optimizer rewrites to {{Contains}}) with an ASCII character. This can use a
word-at-a-time (SWAR / memchr-style) scan that tests 8 bytes per iteration.
h2. Current behavior
For a 1-byte needle the loop evaluates {{getByte(i) == first && matchAt(...)}}
at every
position. The {{matchAt}} call is redundant for a single byte, and the
byte-at-a-time scan reads through {{Platform.getByte}} (Unsafe), which the JIT
cannot auto-vectorize, so it processes one byte per iteration.
h2. Proposed change
Add {{ByteArrayMethods.containsByte(Object base, long offset, long length, byte
target)}}. It broadcasts the target byte across a word and, for each 8-byte
word, applies the classic exact "a word contains a zero byte" test.
The test is exact (no false positives), so only the presence of a match is
reported, not its position; this keeps the scan independent of byte order.
Alignment handling mirrors the existing {{arrayEquals}}.
{{UTF8String.contains}} takes a {{numBytes == 1}} fast path that delegates to
it and thereby also drops the redundant {{matchAt}} call.
h2. Benchmark
Local microbenchmark, needle absent (i.e. full scan), nanoseconds per call:
|| Region size || Current (byte-at-a-time) || This PR (SWAR) || Speedup ||
| 16 B | 5.2 | 2.7 | 1.9x |
| 64 B | 14.4 | 6.0 | 2.4x |
| 256 B | 54.1 | 17.3 | 3.1x |
| 1 KB | 177.4 | 62.6 | 2.8x |
| 16 KB | 2691.3 | 963.5 | 2.8x |
| 64 KB | 10753.5 | 3974.6 | 2.7x |
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
