[
https://issues.apache.org/jira/browse/SPARK-59967?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-59967:
-----------------------------------
Labels: pull-request-available (was: )
> 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
> Priority: Minor
> Labels: pull-request-available
>
> {{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]
