Zoltán Borók-Nagy created IMPALA-15426:
------------------------------------------
Summary: Use SIMD in StringSearch (LIKE '%x%', instr, locate,
replace)
Key: IMPALA-15426
URL: https://issues.apache.org/jira/browse/IMPALA-15426
Project: IMPALA
Issue Type: Improvement
Components: Backend
Reporter: Zoltán Borók-Nagy
StringSearch::Search() (be/src/runtime/string-search.h:81) is a Horspool-style
loop with a
bloom filter that checks one haystack position at a time. It runs per row for:
* LIKE '%x%' (like-predicate.cc:247, called through a function pointer, so
codegen does
not help);
* instr()/locate();
* replace() (string-functions-ir.cc:527/920);
* parse_url.
h3. Proposed fix
When (haystack length − needle length) ≥ 15, compare the first and the last
needle byte
against 16 haystack positions at a time with SSE2, and verify candidates
inline. For the
final block, use an overlapping load, not a scalar tail. Keep the current
scalar path for
short haystacks and on aarch64 (a NEON port can follow). RSearch() is unchanged.
h3. Measurements
Standalone replica with realistic data, ns per row:
||Data||Needle||Current||New||Speedup||
|TPC-H p_name (33 B)|'green'|39.9|10.4|3.9x|
|TPC-H o_comment (49 B)|'special', 'requests'| | |2.4–2.8x|
|URLs (150 B)|'.php', 'checkout', …| | |3.5–7x|
|Logs / JSON (0.5–1.5 KB)| | | |4.6–11x|
|any|1-byte needle| | |about 1.0x (0.97–1.00x)|
|p_name / o_comment|20-byte needle| | |1.06–1.7x|
There was no regression beyond noise. The new code was fuzzed on 10M random
cases
against a naive search, with needles at page ends next to a PROT_NONE guard
page and
under ASAN: 0 mismatches. A memmem()-based variant was also tried; it only
reached
0.93–2.5x and lost on 33-byte strings.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
