You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Joe McDonnell (Jira)" <ji...@apache.org> on 2026/02/18 01:05:00 UTC
[jira] [Created] (IMPALA-14753) SIMD optimizations for string search
Joe McDonnell created IMPALA-14753:
--------------------------------------
Summary: SIMD optimizations for string search
Key: IMPALA-14753
URL: https://issues.apache.org/jira/browse/IMPALA-14753
Project: IMPALA
Issue Type: Task
Components: Backend
Affects Versions: Impala 5.0.0
Reporter: Joe McDonnell
In be/src/benchmarks/string-search-benchmark.cc, it compares our current implementation in be/src/runtime/string-search.h (which came from Python) to one that calls out to strstr in libc. Running this today, I get these results:
{noformat}
$ bin/run-jvm-binary.sh taskset -c 0 setarch `uname -m` -R be/build/latest/benchmarks/string-search-benchmark
Machine Info: 12th Gen Intel(R) Core(TM) i9-12900K
String Search: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile
(relative) (relative) (relative)
---------------------------------------------------------------------------------------------------------
Python 165 168 169 1X 1X 1X
LibC 1.37e+03 1.39e+03 1.4e+03 8.31X 8.26X 8.25X
Null Terminated SSE 924 932 937 5.59X 5.56X 5.54X
Non-null Terminated SSE 764 774 778 4.63X 4.61X 4.59X{noformat}
This suggests that string search would benefit from SIMD optimizations. Further, there are libraries that claim to be faster than strstr (e.g. [https://github.com/ashvardanian/StringZilla] ).
Our current code is based on Cython code in faststring.h: [https://github.com/python/cpython/blob/main/Objects/stringlib/fastsearch.h]
The Cython code has since added an implementation of Crochemore and Perrin's (1991) Two-Way algorithm. This can avoid certain pathological cases.
--
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