[jira] [Created] (IMPALA-15426) Use SIMD in StringSearch (LIKE '%x%', instr, locate, replace)

["Zoltán Borók-Nagy (Jira)" <ji...@apache.org>]

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: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org