David Mollitor created SPARK-59967:
--------------------------------------
Summary: Scan 8 bytes at a time in UTF8String.contains and binary
contains
Key: SPARK-59967
URL: https://issues.apache.org/jira/browse/SPARK-59967
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.2.0
Reporter: David Mollitor
{{UTF8String.contains}} (used by {{contains()}} and by {{LIKE '%...%'}} after
{{{}LikeSimplification{}}}) and {{ByteArrayMethods.contains(byte[], byte[])}}
(used by {{contains()}} on binary) search one byte at a time. Every position
does a bounds-checked {{{}getByte{}}}, and every position that matches the
first byte of the needle pays a full {{matchAt}} / {{arrayEquals}} call.
This moves the search into a shared {{ByteArrayMethods.contains(base, offset,
length, subBase, subOffset, subLength)}} that both methods call. On platforms
with unaligned access it checks 8 positions per step:
* XOR the 8-byte word at each position with the needle's first byte repeated,
and the word at (position + needle length - 1) with its last byte repeated.
* An exact zero-byte mask over the OR of the two marks the positions where
both bytes match; only those positions compare the remaining bytes.
* The final word overlaps the previous one, so there is no byte-at-a-time tail.
Platforms without unaligned access use a byte loop that also checks the first
and last bytes.
Local JMH results (JDK 17, ns per row):
||Rows||Needle||master||new||Speedup||
|128 bytes|not present|129|24|5.5x|
|128 bytes|starts with a space (frequent first byte)|325|24|13.9x|
|128 bytes|found in the middle|99|23|4.2x|
|1024 bytes|not present|~1055|188|~5.6x|
|16 bytes|not present|10.2|4.7|2.2x|
|128 bytes|rows of all 'a', needle "aQa" (every position a
candidate)|621|206|3.0x|
|16 bytes|needle as long as the row (one position to check)|3.1|3.2|unchanged|
JDK 25 showed the same pattern.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
