# StringZilla > SIMD and GPU-accelerated strings ## Introduction So most string-processing code still looks like `for (i = 0; i < length; ++i) if (text[i] == 'x') โ€ฆ` โ€” a tangle of loops, branches, and per-character lookups, where the surrounding control flow often costs more than the character-level logic itself, whether the text is ASCII or UTF-8 encoded Unicode. Worse, chewing through one byte or codepoint at a time squanders the hardware: a modern CPU carries dozens of 16-64 byte architectural registers, and hundreds of physical ones to feed out-of-order execution. StringZilla reaches for those [SIMD][faq-simd] and [SWAR][faq-swar] instructions directly, offering one of the widest, fastest, and most portable collections of text-processing primitives anywhere. StringZilla is the GodZilla of string libraries, accelerating exact and fuzzy matching, hashing, edit distances, sorting, segmentation, and even random-string generation, with allocation-free lazily-evaluated iterators throughout. - It can be __3x faster than LibC__ doing substring search on Arm servers, and __9x on Apple Silicon__, where the system `strstr` is weaker. - It can be __10-70x faster than ICU__, both ICU4C and its Rust successor ICU4X, in UTF-8 handling, case folding, segmentation, and tokenization. - It can be __over 10x faster than NVIDIA's own libraries__ for on-GPU Levenshtein edit distances. - It comes with built-in custom __WebAssembly__ backend for sandboxed WASI, DBMS, & LLM environments, custom __RVV__ backend for RISC-V CPUs, __PowerPC__ backend for IBM Power servers, __LoongArch__ for Chinese domestic chips, and more! Reach for it from your language of choice: - ๐Ÿ‚ __[C](#c--c):__ Upgrade LibC's `` to `` in C 99 - ๐Ÿ‰ __[C++](#c--c):__ Upgrade STL's `` to `` in C++ 20 - ๐Ÿงฎ __[CUDA](https://www.unum.cloud/docs/stringzilla/c.md):__ Score batches on a device with engines built for its capabilities in CUDA C++ 20 - ๐Ÿ __[Python](#python):__ Upgrade your `str` to faster `String` - ๐Ÿฆ€ __[Rust](#rust):__ Use the `StringZilla` traits crate - ๐Ÿฆซ __[Go](#go):__ Use the `StringZilla` cGo module - ๐ŸŽ __[Swift](#swift):__ Use the `String+StringZilla` extension - ๐ŸŸจ __[JavaScript](#javascript):__ Use the `StringZilla` library - ๐Ÿ’œ __[C#](#c):__ Zero-copy over `ReadOnlySpan`, NativeAOT-friendly - โ˜• __[Java](#java):__ Pure FFM API over `MemorySegment`, no JNI - ๐Ÿš __[Shell][faq-shell]__: Accelerate common CLI tools with `sz-` prefix - ๐Ÿ“š Researcher? Jump to [Algorithms & Design Decisions](#algorithms--design-decisions) - ๐Ÿ’ก Thinking to contribute? Look for ["good first issues"][first-issues] - ๐Ÿค And check the [guide](https://github.com/ashvardanian/StringZilla/blob/main/CONTRIBUTING.md) to set up the environment - Want more bindings or features? Let [me](https://github.com/ashvardanian) know! __Who is this for?__ - For data-engineers parsing large datasets, like the [CommonCrawl](https://commoncrawl.org/), [RedPajama](https://github.com/togethercomputer/RedPajama-Data), or [LAION](https://laion.ai/blog/laion-5b/). - For software engineers optimizing strings in their apps and services. - For bioinformaticians and search engineers looking for edit-distances for [USearch](https://www.unum.cloud/docs/usearch.md). - For [DBMS][faq-dbms] devs, optimizing `LIKE`, `ORDER BY`, and `GROUP BY` operations. - For hardware designers, needing a SWAR baseline for string-processing functionality. - For students studying SIMD/SWAR applications to non-data-parallel operations. ## Performance Throughput and timings on two CPUs, grouped by operation. Only the languages that ship a counterpart appear under each heading. `StringZilla.C` is the C kernel called directly; `StringZilla.Py` is the same kernel through the CPython binding, so the gap between them is the cost of crossing the interpreter boundary. ```text Xeon4 M5 Pro โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ Unicode case-insensitive substring search (GB/s) Python icu.StringSearch 0.06 0.14 StringZilla.C sz_utf8_uncased_search_best 12.26 8.66 StringZilla.Py sz.utf8_uncased_search 11.55 8.56 Find the first occurrence of a random word, โ‰… 5 bytes (GB/s) LibC strstr 19.8 3.3 STL C++ std::string::find 8.5 10.2 Python str.find 2.3 2.9 StringZilla.C sz_find_best 19.6 34.6 StringZilla.Py sz.find 17.3 31.1 Split lines separated by \n or \r (GB/s) LibC strcspn 8.6 3.5 STL C++ std::string::find_first_of 1.0 3.8 Python re.finditer 0.30 0.60 StringZilla.C sz_find_byteset_best 12.9 22.1 StringZilla.Py sz.split_byteset_iter 10.4 20.2 ``` > Treat these as a first impression, not a benchmark suite. > The Unicode numbers were obtained on a 128 MB slice of multilingual XLSum. > `Xeon4` is an Intel Sapphire Rapids with GCC and `glibc`, and `M5 Pro` an 18-core Apple Silicon with Apple clang and `libc++`. > The two CPUs therefore differ in standard library as much as in ISA, which is most of the gap in the `strstr`, `strcspn`, and `std::string::find_first_of` rows; the StringZilla rows build from the same source on both. > These will not reproduce exactly; the links below carry the methodology and the per-library breakdowns. The batch engines are timed per family and per backend, CPU beside GPU, in [`levenshtein/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/levenshtein/README.md), [`overlap/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/overlap/README.md), and [`substrings/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/substrings/README.md). Most StringZilla modules ship ready-to-run benchmarks for C, C++, Python, and more. Grab them from `./bench`, and see [`CONTRIBUTING.md`](https://github.com/ashvardanian/StringZilla/blob/main/CONTRIBUTING.md), [`test/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/test/README.md), and [`bench/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/bench/README.md) for instructions. For wider head-to-heads against Rust and Python favorites, browse the __[StringWars][stringwars]__ repository. To inspect collision resistance and distribution shapes for our hashers, see __[HashEvals][hashevals]__. [stringwars]: https://github.com/ashvardanian/StringWars [hashevals]: https://github.com/ashvardanian/HashEvals ## Quickstart Each binding has its own install command, import line, and dedicated guide, all collected in the per-language sections below. The batch engines ship inside the same package and the same crate as the single-string kernels, so there is nothing extra to install for them. ### Python `pip install stringzilla` · guide: [`python/README.md`](https://www.unum.cloud/docs/stringzilla/python.md) ```python import stringzilla as sz text = sz.String("the quick brown fox") text.find("brown") # 10 text.split() # sz.Strings(['the', 'quick', 'brown', 'fox']) sz.hash("hello") # fast 64-bit hash ``` The Python package upgrades `str` and `bytes` with SIMD search, sorting, hashing, UTF-8 segmentation, and Unicode case-folding, plus the batch engines that score one prepared set of queries against many collections of candidates. ### C & C++ Link `stringzilla::static` through CMake `FetchContent`, or `find_package(stringzilla)` an installed build, or go header-only in C · guide: [`include/stringzilla/README.md`](https://www.unum.cloud/docs/stringzilla/c.md) ```c #include sz_capability_t capabilities = sz_cap_serial_k; sz_capabilities_enabled_cpu(&capabilities); // what this CPU runs and this binary holds sz_cptr_t match = NULL; sz_find_best(haystack, h_length, "brown", 5, &match, capabilities, NULL); // pointer to the match, or NULL ``` ```cpp #include namespace sz = ashvardanian::stringzilla; sz::string_view_t("the quick brown fox").find("brown"); // 10 ``` The library covers search, hashing, sorting, comparison, set intersection, collection conversions like escaping, normalization and Arrow-compatible tapes, and lazy UTF-8 segmentation, plus the engines for edit distances, window overlap, and multi-pattern search, each with a host arm, a CUDA and ROCm one, and a Metal one. ### Rust `cargo add stringzilla` · guide: [`rust/README.md`](https://www.unum.cloud/docs/stringzilla/rust.md) ```rust use stringzilla as sz; assert_eq!(sz::find("the quick brown fox", "brown"), Some(10)); let digest = sz::hash("hello"); // fast 64-bit hash ``` The crate adds SIMD search, sorting, hashing, and UTF-8 segmentation to any `AsRef<[u8]>`, plus the `LevenshteinEngine`, `OverlapEngine` and `SubstringsEngine` batch engines, whose device arms come with the `cuda` feature. ### JavaScript `npm install stringzilla` · guide: [`javascript/README.md`](https://www.unum.cloud/docs/stringzilla/javascript.md) ```javascript import sz from "stringzilla"; sz.find(Buffer.from("the quick brown fox"), Buffer.from("brown")); // => 10n sz.hash(Buffer.from("hello")); // 64-bit BigInt ``` The Node-API addon runs on Node, Bun, and Deno, exposing zero-copy search, hashing, SHA-256, and Unicode case-folding over `Buffer` objects. ### Swift Add the Swift Package Manager dependency · guide: [`swift/README.md`](https://www.unum.cloud/docs/stringzilla/swift.md) ```swift import StringZilla let i = "the quick brown fox".findFirst(substring: "brown") // Index of "brown" let h = "hello".hash() // fast 64-bit hash ``` The Foundation-free package extends `String` with SIMD search, comparison, hashing, Unicode case-folding, normalization, and word and line segmentation, on Linux and embedded targets as well as Apple platforms. ### Go `go get github.com/ashvardanian/stringzilla/golang` · guide: [`golang/README.md`](https://www.unum.cloud/docs/stringzilla/go.md) ```go import sz "github.com/ashvardanian/stringzilla/golang" sz.Index("the quick brown fox", "brown") // 10 sz.Hash("hello", 0) // fast 64-bit hash ``` The cgo module exposes byte-level search, counting, checksums, SHA-256, and UTF-8 case-folding to Go. ### C# Build from source · guide: [`csharp/README.md`](https://www.unum.cloud/docs/stringzilla/csharp.md) · __not yet on NuGet__ ```csharp using StringZilla; Sz.IndexOf("the quick brown fox"u8, "brown"u8); // 10 Sz.Hash("hello"u8); // fast 64-bit hash ``` Zero-copy over `ReadOnlySpan` (and Unity's `NativeArray`); `net8.0`, NativeAOT-friendly. Exposes search, hashing, SHA-256, UTF-8 segmentation, case-folding, normalization, sorting, and allocation-free splitting and iteration. ### Java Build from source with `gradle` · guide: [`java/README.md`](https://www.unum.cloud/docs/stringzilla/java.md) · __not yet on Maven Central__ ```java import com.stringzilla.StringZilla; StringZilla.indexOf("the quick brown fox".getBytes(), "brown".getBytes()); // 10 StringZilla.hash("hello".getBytes()); // fast 64-bit hash ``` Pure [Foreign Function & Memory API](https://openjdk.org/jeps/454) (JDK 22+), __no JNI__. Zero-copy over `byte[]` and `MemorySegment` โ€” including Lucene `BytesRef` and Spark `UTF8String` backing memory. Lazy `Iterable`/`Stream` splitting and iteration, with zero-allocation cursors as the escape hatch. ## Why StringZilla There are several other excellent libraries with overlapping subsets of operations and somewhat different design philosophies. LibC obviously provides a good baseline for basic memory operations, but its APIs vary widely in quality, and its Arm implementations often trail its x86 ones. ICU and ICU4X implement the Unicode standard to a letter, but don't exploit hidden invariants in the Unicode ruleset to vectorize those operations. RapidFuzz comes with a very good set of string-similarity algorithms and is already well vectorized on CPUs, but leaves batched cross-products symmetries and massive GPU speedups on the table. xxHash and aHash provide great non-cryptographic hashes, but may not cover all of the hashing use cases, or leverage the wider AES and predicated instructions available on modern CPUs. Because StringZilla mirrors the familiar standard APIs, adoption is mostly a search-and-replace. ```text Standard StringZilla โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ Python Find a substring "...".find(x) sz.find("...", x) Sort strings sorted(items) sz.Strings(items).sorted() Split on a separator "...".split(sep) sz.String("...").split(sep) Case-fold for matching "...".casefold() sz.utf8_uncased_fold("...") Streaming SHA-256 hashlib.sha256() sz.Sha256() C++ Find a substring std::string::find sz::string_t::find Sort a collection std::sort of indices sz::argsort Intersect string sets std::set_intersection sz::intersect Hash map, string keys std::unordered_map sz::hash + sz::equal_to ``` ## Functionality StringZilla is compatible with most modern CPUs, and provides a broad range of functionality. Its C surface comes in 2 shapes: 1. Single-string kernels, taking a pointer and a length, and answering with an offset, a digest, or an order. 2. Stateful engines, preparing a batch of queries once and scoring it against many batches of candidates. An engine is prepared by `sz__engine_init(engine, โ€ฆ, capabilities, allocator, stream)` for the device its stream belongs to, and every later round runs there, so choosing a device is choosing the mask an engine is built with and the stream it queues on, rather than flipping a global. Each round is a single verb, like `sz_levenshtein_distances`, taking a trailing stream: null on the CPU, and on a GPU the stream it enqueues on before returning for the caller to join. Both shapes are designed to be extremely portable: - [x] across both little-endian and big-endian architectures. - [x] across 32-bit and 64-bit hardware architectures. - [x] across operating systems and compilers. - [x] across ASCII and UTF-8 encoded inputs. Not all features are available across all bindings. Consider contributing if you need a feature that's not yet implemented. | | Maturity | C | C++ | Python | Rust | JS | Swift | Go | C# | Java | | :----------------------------- | :------: | :-: | :-: | :----: | :--: | :-: | :---: | :-: | :-: | :--: | | Substring Search | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Character Set Search | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Sorting & Sequence Operations | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โœ… | โœ… | | Set Intersection & Joins | ๐Ÿง | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โœ… | โœ… | | Lazy Ranges, Compressed Arrays | ๐ŸŒณ | โŒ | โœ… | โœ… | โœ… | โŒ | โšช | โšช | โœ… | โœ… | | One-Shot & Streaming Hashes | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Cryptographic Hashes | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Small String Class | ๐Ÿง | โœ… | โœ… | โŒ | โšช | โŒ | โŒ | โŒ | โŒ | โŒ | | Random String Generation | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โœ… | โœ… | | Unicode Case Folding | ๐Ÿง | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Uncased UTF-8 Search | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | TR29 Word Boundary Detection | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โšช | โœ… | โœ… | | TR29 Grapheme Segmentation | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โœ… | โœ… | | TR29 Sentence Segmentation | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โœ… | โœ… | | UAX14 Line-Break Detection | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โœ… | โœ… | | Unicode Normalization | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Codepoint Counting & Indexing | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | โœ… | | Batch Edit Distances | ๐ŸŒณ | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โšช | โšช | | Batch Window Overlap | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โšช | โšช | | Batch Multi-Pattern Search | ๐Ÿšง | โœ… | โœ… | โœ… | โœ… | โšช | โšช | โšช | โšช | โšช | > ๐ŸŒณ parts are used in production. > ๐Ÿง parts are in beta. > ๐Ÿšง parts are under active development, and are likely to break in subsequent releases. > โœ… are implemented. > โšช are considered. > โŒ are not intended. ## Algorithms & Design Decisions StringZilla aims to optimize some of the slowest string operations. Some popular operations, however, like equality comparisons and relative order checking, almost always complete on some of the very first bytes in either string. In such operations vectorization is almost useless, unless huge and very similar strings are considered. StringZilla implements those operations as well, but won't result in substantial speedups. Where vectorization stops being effective, batching takes over: an engine prepares a batch of queries once and scores every candidate against all of them, on the host or on a GPU. The library owns no thread pool and starts no thread of its own, so a caller wanting more than one core builds one engine per worker and shards the candidate range itself. ### Exact Substring Search Substring search algorithms are generally divided into: comparison-based, automaton-based, and bit-parallel. Different families are effective for different alphabet sizes and needle lengths. The more operations are needed per-character - the more effective SIMD would be. The longer the needle - the more effective the skip-tables are. StringZilla uses different exact substring search algorithms for different needle lengths and backends: - When no SIMD is available - SWAR (SIMD Within A Register) algorithms are used on 64-bit words. - Boyer-Moore-Horspool (BMH) algorithm with Raita heuristic variation for longer needles. - SIMD backends compare characters at multiple strategically chosen offsets within the needle to reduce degeneracy. On very short needles, especially 1-4 characters long, brute force with SIMD is the fastest solution. On mid-length needles, bit-parallel algorithms are effective, as the character masks fit into 32-bit or 64-bit words. Either way, if the needle is under 64-bytes long, on haystack traversal we will still fetch every CPU cache line. So the only way to improve performance is to reduce the number of comparisons. > For 2-byte needles, see `sz_find_2byte_serial_` in `include/stringzilla/find/serial.h`: https://github.com/ashvardanian/StringZilla/blob/a6402dd71d01a8967a62bcc45a900477e0232f60/include/stringzilla/find/serial.h#L231-L273 Going beyond that, to long needles, Boyer-Moore (BM) and its variants are often the best choice. It has two tables: the good-suffix shift and the bad-character shift. Common choice is to use the simplified BMH algorithm, which only uses the bad-character shift table, reducing the pre-processing time. We do the same for mid-length needles up to 256 bytes long. That way the stack-allocated shift table remains small. > For mid-length needles (โ‰ค256 bytes), see `sz_find_horspool_upto_256bytes_serial_` in `include/stringzilla/find/serial.h`: https://github.com/ashvardanian/StringZilla/blob/a6402dd71d01a8967a62bcc45a900477e0232f60/include/stringzilla/find/serial.h#L449-L500 In the C++ Standards Library, the `std::string::find` function uses the BMH algorithm with Raita's heuristic. Before comparing the entire string, it matches the first, last, and the middle character. Very practical, but can be slow for repetitive characters. Both SWAR and SIMD backends of StringZilla have a cheap pre-processing step, where we locate unique characters. This makes the library a lot more practical when dealing with non-English corpora. > The offset selection heuristic is implemented in `sz_locate_needle_anomalies_` in `include/stringzilla/find/serial.h`: https://github.com/ashvardanian/StringZilla/blob/a6402dd71d01a8967a62bcc45a900477e0232f60/include/stringzilla/find/serial.h#L35-L96 All those, still, have $O(hn)$ worst case complexity. To guarantee $O(h)$ worst case time complexity, the Apostolico-Giancarlo (AG) algorithm adds an additional skip-table. Preprocessing phase is $O(n + \sigma)$ in time and space. On traversal, performs from $(h/n)$ to $(3h/2)$ comparisons. It however, isn't practical on modern CPUs. The Galil rule is a simpler and more relevant optimization, if many matches must be found. Other algorithms previously considered and deprecated: - Apostolico-Giancarlo algorithm for longer needles. _Control-flow is too complex for efficient vectorization._ - Shift-Or-based Bitap algorithm for short needles. _Slower than SWAR._ - Horspool-style bad-character check in SIMD backends. _Effective only for very long needles, and very uneven character distributions between the needle and the haystack._ _Faster "character-in-set" check needed to generalize._ > ยง Reading materials. > [Exact String Matching Algorithms in Java](https://www-igm.univ-mlv.fr/~lecroq/string). > [SIMD-friendly algorithms for substring searching](http://0x80.pl/articles/simd-strfind.html). ### Exact Multiple Substring Search Few algorithms for multiple substring search are known. Most are based on the Aho-Corasick automaton, which is a generalization of the KMP algorithm. The naive implementation, however: - Allocates disjoint memory for each Trie node and Automaton state. - Requires a lot of pointer chasing, limiting speculative execution. - Has a lot of branches and conditional moves, which are hard to predict. - Matches text a character at a time, which is slow on modern CPUs. There are several ways to improve the original algorithm. One is to use sparse DFA representation, which is more cache-friendly, but would require extra processing to navigate state transitions. StringZilla takes that route in [`substrings`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/substrings/README.md), compiling a needle vocabulary once into a goto-completed Aho-Corasick automaton and reusing it across every later round of haystacks. The automaton is split into two tiers โ€” a dense goto-completed row per frequently-visited state, one target per byte class, and a double array for the rest โ€” so a step is one load with no failure-following at runtime. It matches raw bytes or applies full Unicode case folding to both sides, runs on the host or on a CUDA device, and answers counts, located matches, rewritten haystacks, or BM25 scores out of the one walk. Where only near-duplicate detection or candidate filtering is needed, the window-overlap machinery described below is the cheaper tool. ### Levenshtein Edit Distance Levenshtein distance is the best known edit-distance for strings, that checks, how many insertions, deletions, and substitutions are needed to transform one string to another. It's extensively used in approximate string-matching, spell-checking, and bioinformatics. The computational cost of the Levenshtein distance is $O(n * m)$, where $n$ and $m$ are the lengths of the string arguments. To compute that, the naive approach requires $O(n * m)$ space to store the "Levenshtein matrix", the bottom-right corner of which will contain the Levenshtein distance. The algorithm producing the matrix has been simultaneously studied/discovered by the Soviet mathematicians Vladimir Levenshtein in 1965, Taras Vintsyuk in 1968, and American computer scientists - Robert Wagner, David Sankoff, Michael J. Fischer in the following years. Several optimizations are known: 1. __Space Optimization__: The matrix can be computed in $O(min(n,m))$ space, by only storing the last two rows of the matrix. 2. __Divide and Conquer__: Hirschberg's algorithm can be applied to decompose the computation into subtasks. 3. __Automata__: Levenshtein automata can be effective, if one of the strings doesn't change, and is a subject to many comparisons. 4. __Shift-Or__: Bit-parallel algorithms transpose the matrix into a bit-matrix, and perform bitwise operations on it. The last approach is the one StringZilla takes, and the one the great [RapidFuzz][rapidfuzz] library takes as well. It's less known, than the others, derived from the Baeza-Yates-Gonnet algorithm, extended to bounded edit-distance search by Manber and Wu in 1990s, and further extended by Gene Myers in 1999 and Heikki Hyyro between 2002 and 2004. Every query is packed into match masks 64 symbols to a machine word once per batch, and every candidate then streams one symbol per step against all of them, so the preparation a one-shot distance repeats per pair is paid exactly once and the register width buys candidates per step rather than cells per step. The anti-diagonal traversal gives long byte pairs intra-pair parallelism within the device collection API. It doesn't change the number of trivial operations, but performs them in a different order, removing the data dependency, that occurs when computing the insertion costs. It __evaluates diagonals instead of rows__, exploiting the fact that all cells within a diagonal are independent, and can be computed in parallel. We'll store 3 diagonals instead of the 2 rows, and each consecutive diagonal will be computed from the previous two. Substitution costs will come from the sooner diagonal, while insertion and deletion costs will come from the later diagonal.
Row-by-Row Algorithm
Computing row 4: 
    โˆ…  A  B  C  D  E
 โˆ…  0  1  2  3  4  5
 P  1  โ–‘  โ–‘  โ–‘  โ–‘  โ–‘
 Q  2  โ–   โ–   โ–   โ–   โ– 
 R  3  โ–   โ–   โ–ก  โ†’  .
 S  4  .  .  .  .  .
 T  5  .  .  .  .  .
Anti-Diagonal Algorithm
Computing diagonal 5: 
    โˆ…  A  B  C  D  E
 โˆ…  0  1  2  3  4  5
 P  1  โ–‘  โ–‘  โ–   โ–   โ–ก
 Q  2  โ–‘  โ–   โ–   โ–ก  โ†˜
 R  3  โ–   โ–   โ–ก  โ†˜  .
 S  4  โ–   โ–ก  โ†˜  .  .
 T  5  โ–ก  โ†˜  .  .  .
Legend:
0,1,2,3... = initialization constants    โ–‘ = cells processed and forgotten    โ–  = stored cells    โ–ก = computing in parallel    โ†’ โ†˜ = movement direction    . = cells to compute later
This results in much better vectorization for intra-core parallelism, and parallelizes over the long text's tile-columns, which is the axis the bit-parallel recurrence cannot touch. > ยง Reading materials. > [Faster Levenshtein Distances with a SIMD-friendly Traversal Order](https://ashvardanian.com/posts/levenshtein-diagonal). [rapidfuzz]: https://github.com/rapidfuzz/RapidFuzz ### Escaping, Normalizing & Gathering Collections Strings in data pipelines travel in columns: log streams, Arrow arrays, Pandas series, the nodes of a parsed document. StringZilla converts a whole collection in one call, reading any layout, from Arrow `String` and `LargeString` tapes to an accessor over arbitrary records, and writing an Arrow-compatible tape it sizes exactly once. Escaping covers JSON, JSON in ASCII the way Python's `json.dumps` writes it, RFC 4180 CSV, hexadecimal, HTML, URL percent-encoding, and terminal-safe logs that neutralize bidirectional overrides, and unescaping reverses each, naming the first malformed string. Every kernel skips the bytes that need no work with the SIMD byte-set search and measures its output exactly before writing it. Every conversion is also atomic: it leaves the output tape holding the whole result, or fails with the tape exactly as it was, so a refused allocation or a malformed string never strands a half-converted column. Normalization adds NFKC_Casefold to the four UAX #15 forms, the caseless key that search engines match on, folding clean runs with the case-folding kernels and rewriting only the segments that change. Single-threaded on an Apple M5 Pro, over 4 MB of English sentences, the NEON kernels move: - JSON escaping at 3.37 GB/s and unescaping at 3.33 GB/s, 2.8ร— and 3.2ร— the serial code. - CSV escaping at 2.78 GB/s and unescaping at 3.96 GB/s, 2.3ร— and 2.6ร— the serial code. - HTML escaping at 2.99 GB/s and unescaping at 2.84 GB/s, 2.5ร— and 2.4ร— the serial code. - Gathering into a tape at 14.8 GB/s, the speed of `memcpy`. - NFC normalization at 1.66 GB/s and NFKC_Casefold at 0.61 GB/s over multilingual XL-Sum articles, 2.1ร— and 1.8ร— the serial code. ### Hashing StringZilla implements a high-performance 64-bit hash function inspired by the "AquaHash", "aHash", and "GxHash" design and optimized for modern CPU architectures. It passes the rigorous SMHasher test suite, including the `--extra` flag with no collisions. The core algorithm operates on a __dual state__ that runs two independent mixers over the same bytes and folds them together at the end: - __AES State__: Initialized with the seed `XOR`-ed against ฯ€ constants and advanced with one AES encryption round per block, providing the strong avalanche behavior. - __Sum State__: Initialized from a second slice of the ฯ€ constants and advanced as an additive byte sum under a fixed permutation, cheap to compute and complementary to the AES mixing. Because the AES round is the backbone, the per-ISA backends lean on each platform's cryptographic instructions rather than emulating them: AES-NI and VAES on x86, SHA-NI on Goldmont, NEON-AES, NEON-SHA, and SVE2-AES on Arm, and RVV-crypto on RISC-V, in the `include/stringzilla/hash/{neonaes,neonsha,sve2aes,rvvcrypto}.h` files. To keep the streaming path off the stack, the incremental construction uses an __in-register streaming-state merge__: each incoming run is slid into a resident register with a masked load and a blend, so partial blocks never spill to memory. For strings โ‰ค64 bytes, a minimal state processes data in 16-byte blocks. Longer strings employ a 4ร— wider state (512 bits) that processes 64-byte chunks, maximizing throughput on modern superscalar CPUs. The algorithm can be expressed in pseudocode as: ```text function sz_hash(text: u8[], length: usize, seed: u64) -> u64: pi: u64[16] = [0x243F6A8885A308D3, 0x13198A2E03707344, 0xA4093822299F31D0, 0x082EFA98EC4E6C89, 0x452821E638D01377, 0xBE5466CF34E90C6C, 0xC0AC29B7C97C50DD, 0x3F84D5B5B5470917, 0x9216D5D98979FB1B, 0xD1310BA698DFB5AC, 0x2FFD72DBD01ADFB7, 0xB8E1AFED6A267E96, 0xBA7C9045F12C7F99, 0x24A19947B3916CF7, 0x0801F2E2858EFC16, 0x636920D871574E69] shuffle: u8[16] = [0x04, 0x0b, 0x09, 0x06, 0x08, 0x0d, 0x0f, 0x05, 0x0e, 0x03, 0x01, 0x0c, 0x00, 0x07, 0x0a, 0x02] # Permutation order for the sum state # Both states are `lanes` ร— 128 bits wide: one lane for short inputs, four for long ones. The AES half seeds # from the low 512 bits of ฯ€, the sum half from the high 512 bits, each XOR-ed against the seed. lanes: usize = 1 if length โ‰ค 64 else 4 aes: u128[lanes] = [seed โŠ• pi[2*lane], seed โŠ• pi[2*lane + 1] for lane in 0..lanes-1] sum: u128[lanes] = [seed โŠ• pi[2*lane + 8], seed โŠ• pi[2*lane + 9] for lane in 0..lanes-1] # One AES round and one shuffle-add per 16-byte block. Short inputs are zero-padded to 1-4 blocks; # long inputs stream 64-byte chunks, one block per lane, so the four lanes stay independent. for each chunk: u8[16 * lanes] in split_into_chunks(text, length, 16 * lanes): for lane in 0..lanes-1: aes[lane] = AESENC(aes[lane], chunk[lane]) sum[lane] = SHUFFLE(sum[lane], shuffle) + chunk[lane] if lanes > 1: aes, sum = fold_to_one_lane(aes), fold_to_one_lane(sum) # Collapse the 512-bit states back to 128 # Finalization: mix the length into the key, then AES-mix the two states together for SMHasher compliance key: u128 = [seed + length, seed] mixed: u128 = AESENC(sum, aes) return low_u64(AESENC(AESENC(mixed, key), mixed)) ``` This allows us to balance several design trade-offs. First, it allows us to achieve a high port-level parallelism. Looking at AVX-512 capable CPUs and their ZMM instructions, on each cycle, we'll have at least 2 ports busy when dealing with long strings: - `VAESENC`: 5 cycles on port 0 on Intel Ice Lake, 4 cycles on ports 0/1 on AMD Zen4. - `VPSHUFB_Z`: 3 cycles on port 5 on Intel Ice Lake, 2 cycles on ports 1/2 on AMD Zen4. - `VPADDQ`: 1 cycle on ports 0/5 on Intel Ice Lake, 1 cycle on ports 0/1/2/3 on AMD Zen4. When dealing with smaller strings, we design our approach to avoid large registers and maintain the CPU at the same energy state, thereby avoiding downclocking and expensive power-state transitions. Unlike some AES-accelerated alternatives, the length of the input is not mixed into the AES block at the start to allow incremental construction, when the final length is not known in advance. Also, unlike some alternatives, with "masked" AVX-512 and "predicated" SVE loads, we avoid expensive block-shuffling procedures on non-divisible-by-16 lengths. > ยง Reading materials. > [Stress-testing hash functions for avalance behaviour, collision bias, and distribution](https://github.com/ashvardanian/HashEvals). ### SHA-256 Checksums In addition to the fast AES-based hash, StringZilla implements hardware-accelerated SHA-256 cryptographic checksums, following the [FIPS 180-4 specification](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf). Where the AES hash leans on the AES round instructions, SHA-256 leans on the dedicated SHA extensions: `SHA256RNDS2` and `SHA256MSG1`/`SHA256MSG2` on x86 from Goldmont onward, and the `SHA256H`/`SHA256SU0` family on Arm, with SWAR, LASX, RVV, and WebAssembly fallbacks rounding out the set. The API is a three-call streaming state โ€” `sz_sha256_state_init_best`, `sz_sha256_state_update_best`, `sz_sha256_state_digest_best` โ€” so arbitrarily long inputs can be absorbed in chunks without buffering the whole message. Each backend is also exposed under its own suffix, like `sz_sha256_state_update_neonsha`, for the same manual-dispatch reasons as the rest of the library. Digesting one message is a serial dependency chain โ€” 32 dependent `SHA256RNDS2` at 4 cycles each โ€” so no wider instruction set can accelerate it, and the SHA-NI path already sits within 15% of that hardware floor. That is also why there is no Ice Lake tier for it: SHA-NI has no VEX or EVEX encoding, so `goldmont` is the widest single-message kernel there will ever be. Independent messages are a different story: they compress in parallel lanes, sixteen at a time on AVX-512 and eight on AVX2, which is what `sz_sha256_multistate_update_best` exposes. That lane-parallel form nearly triples the hash rate of dedicated SHA-NI silicon on token-sized inputs, and still leads by half again on line-sized ones. Lanes retire independently, so a batch of mixed lengths stays vectorized to each lane's own last block rather than dropping to scalar when one lane runs short. A group still costs as much as its longest member, so feeding inputs in length order is the caller's lever โ€” `sz_sort_order_best` produces that ordering, and per-backend numbers are in [`include/stringzilla/hash/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/hash/README.md). ### AES-256 Encryption Most cipher libraries are built for a socket: a stream arrives in order, gets authenticated, and is consumed once. Columnar and block-storage formats are not sockets. They seek โ€” a reader wants row group four hundred out of a million-row file and has no interest in the preceding gigabyte, so a cipher that can only start from byte zero forces the whole file through the AES units to answer a question about the middle of it. StringZilla implements AES-256 in two modes, following [FIPS 197][faq-fips197] for the cipher and [NIST SP 800-38D][faq-gcm] for authentication, and treats seeking as the first-class case. Counter mode is __seekable__: `sz_aes256_ctr_xor_best` takes an absolute `byte_offset`, so decryption starts wherever the reader is, at the cost of authentication. Galois/counter mode adds a tag over the ciphertext and any associated data, and gives up seeking to get it. Which trade a format wants is the format's decision, so both are exposed rather than one being wrapped in the other. The two share a key schedule but not a key struct. `sz_aes256_key_t` is the bare round-key schedule that counter mode needs, while `sz_aes256_gcm_key_t` adds the hash subkey powers Hยน through Hโธ, so bulk encryption never carries a hundred and twenty-eight bytes it will not read. Both one-shot and streaming forms exist, and the streaming state carries __two__ sixteen-byte rhythms across chunk boundaries โ€” one for the keystream block and one for the hash block โ€” so a five-byte chunk followed by an eleven-byte chunk produces the same bytes and the same tag as one sixteen-byte chunk. Streaming splits by __type__ rather than by a flag: `sz_aes256_gcm_encryptor_t` seals and `sz_aes256_gcm_decryptor_t` opens. The Galois hash absorbs ciphertext in both directions, so a shared state that could be pointed the wrong way would make that a runtime question; separate types make it a compile error instead. Authenticated decryption returns `sz_authentication_failed_k` on a forged tag and zero-fills its output, so a caller who ignores the status finds nothing usable rather than forged plaintext. The streaming decrypt is called `sz_aes256_gcm_decryptor_update_unverified_best` because it structurally emits bytes before anything is authenticated, and the name is the warning. Backends cover AES-NI and PCLMUL, VAES and VPCLMULQDQ, Arm crypto extensions and SVE2-AES, RISC-V `Zvkned` with `Zvkg`, Power `vcipher` with `vpmsumd`, and a WebAssembly path that has no cipher instructions at all and emulates the round function through a constant-time tower-field substitution โ€” where the 256-byte lookup table a serial implementation reaches for is itself the side channel. On realistic record sizes the authenticated path outruns both Ring and OpenSSL, in either direction, and unauthenticated counter mode is faster still. Counter mode's margin is an artifact of coverage rather than of arithmetic: OpenSSL ships hand-written AVX-512 assembly for Galois/counter mode and the cipher-block chaining variants, but not for counter mode, so that comparison is a vectorized kernel against a sixteen-byte one. Key setup runs the other way, since an AES-256 schedule is real work where adopting a stream-cipher key is a copy, so workloads that churn through short-lived keys favour the ChaCha implementations. Per-backend numbers are in [`include/stringzilla/cipher/README.md`](https://github.com/ashvardanian/StringZilla/blob/main/include/stringzilla/cipher/README.md). [faq-fips197]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197-upd1.pdf [faq-gcm]: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf ### Random Generation StringZilla implements a fast [Pseudorandom Number Generator][faq-prng] inspired by the "AES-CTR-128" algorithm, reusing the same AES primitives as the hash function. Unlike "NIST SP 800-90A" which uses multiple AES rounds, StringZilla uses only one round of AES mixing for performance while maintaining reproducible output across platforms. The generator operates in counter mode with `AESENC(nonce + lane_index, nonce โŠ• pi_constants)`, rotating through the first 512 bits of ฯ€ for each 16-byte block. The only state required to reproduce an output is a 64-bit `nonce`, which is much cheaper than a Mersenne Twister. [faq-prng]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator ### Sorting For lexicographic sorting of string collections, StringZilla exports pointer-sized nโ€‘grams ("pgrams") into a contiguous buffer to improve locality, then recursively QuickSorts those pgrams with a 3โ€‘way partition and dives into equal pgrams to compare deeper characters. Very small inputs fall back to insertion sort. - Average time complexity: O(n log n) - Worst-case time complexity: quadratic (due to QuickSort), mitigated in practice by 3โ€‘way partitioning and the nโ€‘gram staging ### Unicode 17, UTF-8 & Wide Characters Most StringZilla operations are byte-level, so they work well with ASCII and UTF-8 content out of the box. In some cases, like edit-distance computation, the result of byte-level evaluation and character-level evaluation may differ. - An engine built with `sz_levenshtein_runes_k` scores `"ฮฑฮฒฮณฮด"` against `"ฮฑฮณฮด"` as 1 โ€” one unicode symbol. - An engine built with `sz_levenshtein_bytes_k` scores the same pair as 2 โ€” one unicode symbol is two bytes long. Java, JavaScript, Python 2, C#, and Objective-C, however, expose strings as UTF-16 โ€” a variable-length encoding whose code units are two bytes, so anything outside the Basic Multilingual Plane takes two of them. Because those languages index by code unit rather than by codepoint, this leads [to all kinds of offset-counting issues][wide-char-offsets] when facing four-byte long Unicode characters. StringZilla's own bindings for those languages sidestep the problem entirely by operating on the UTF-8 bytes directly, and internally it uses proper 32-bit "runes" to represent unpacked Unicode codepoints, ensuring correct results in all operations. If you need to transcode between UTF-8, UTF-16, and UTF-32 at the boundary, [simdutf](https://github.com/simdutf/simdutf) is the right tool. Moreover, StringZilla implements the Unicode 17.0 standard, being practically the only library besides ICU and PCRE2 to do so, but with order(s) of magnitude better performance. [wide-char-offsets]: https://josephg.com/blog/string-length-lies/ ### Case Folding & Uncased Search StringZilla provides Unicode-aware uncased substring search that handles the full complexity of Unicode case folding. This includes multi-character expansions: | Character | Codepoint | UTF-8 Bytes | Case-Folds To | Result Bytes | | :-------- | :-------- | :---------- | :------------ | :----------- | | `รŸ` | U+00DF | C3 9F | `ss` | 73 73 | | `๏ฌƒ` | U+FB03 | EF AC 83 | `ffi` | 66 66 69 | | `ฤฐ` | U+0130 | C4 B0 | `i` + `โ—Œฬ‡` | 69 CC 87 | The search returns byte offsets and lengths in the original haystack, correctly handling length differences. For example, searching for `"STRASSE"` (7 bytes) in `"StraรŸe"` (7 bytes: 53 74 72 61 C3 9F 65) succeeds because both case-fold to `"strasse"`. Note that Turkish `ฤฐ` and ASCII `I` are distinct: `ฤฐstanbul` case-folds to `iฬ‡stanbul` (with combining dot), while `ISTANBUL` case-folds to `istanbul` (without). They will not match each other โ€” this is correct Unicode behavior for Turkish locale handling. Under the hood, folding uses register-resident lookup tables for the common single-codepoint folds and dedicated expansion paths for the multi-byte ones. Uncased search folds on the fly, so the haystack is never pre-folded into a second buffer; the matcher tracks the byte-length mismatch whenever a folded form differs in length from its source, returning offsets into the original text. The folding paths live in the `utf8_uncased*` files. ### UTF-8 Decoding & Unicode Segmentation Codepoint decoding walks the input in register-wide chunks, classifying each lead byte by its continuation-byte count through a register-resident lookup table rather than branching byte by byte. It runs under a __fill-and-drain__ contract: a decode-once step fills a buffer of runes, and a separate drain step emits them, which keeps the hot loop tight and lets callers consume runes at their own pace. Ill-formed input is handled without derailing the stream, re-syncing on the maximal-subpart rule and substituting exactly one U+FFFD before continuing. The decoder lives in `include/stringzilla/utf8_runes/`, declared in `c/stringzilla/utf8_runes.h`. UAX-29 word, grapheme, and sentence boundaries, together with UAX-14 line-break opportunities, are found in a single pass. Each codepoint is classified against register-resident property tables and the boundary rules are applied directly, so combining marks, emoji zero-width-joiner sequences, and regional-indicator flags are all handled without a second traversal. The segmenters live in the `utf8_wordbreaks*`, `utf8_graphemes*`, `utf8_sentences*`, and `utf8_linebreaks*` files. ### Unicode Normalization Normalization implements the UAX-15 NFC, NFD, NFKC, and NFKD forms through canonical and compatibility decomposition, canonical-combining-class reordering, and recomposition. Quick-check flags short-circuit the work, so text that is already in the requested form is passed through without the expensive decomposition and reordering passes. The normalizers live in the `utf8_norm*` files. ### Set Intersection StringZilla intersects two deduplicated string collections through a power-of-two open-addressing hash table. The hash is seeded for adversarial resistance and the probe sequence runs under a bounded collision budget, so the intersection completes in linear time and space rather than degrading on crafted inputs. The implementation lives in `include/stringzilla/intersect/`, declared in `c/stringzilla/intersect.h`. ### Window Overlap For near-duplicate detection and candidate filtering, StringZilla slides Rabin-Karp rolling-hash windows of several widths over each query at once, and sorts every width's window hashes of one query into that query's own B-tree. A candidate then streams through the forest, hashing its own windows and probing, so nothing is stored per candidate and the candidates may change round to round while the queries and the widths stay. A window hash is a prefix difference, one modular multiply-add at any width and any offset, against a 32-bit prime chosen for collision weight rather than for size. The measure is asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping the sides changes the score when either repeats a window. The implementation lives in `include/stringzilla/overlap/`, one backend per capability, declared in `c/stringzilla/overlap.h`. ### GPU Edit Distances On the GPU a candidate's recurrence is a dependency chain, so it stays on one thread, and the parallelism comes from the candidates on `blockIdx.x` and from the queries on `blockIdx.y`. The verticals live in the thread's own registers while the match masks are read-only and shared, every thread indexing the same plane by the class of the byte it is stepping, so the rows stay hot in cache instead of being rebuilt per candidate. Myers is add-with-carry and bitwise operations over 64-bit words, all of which the device runs at its integer rate, so each vendor has one GPU tier rather than a ladder of them: `cuda`, `rocm` and `metal`. Long byte pairs use an internal tiled wavefront across tile columns on CUDA, ROCm and Metal; long rune queries use dynamic Myers state. The CUDA and ROCm kernels share `include/stringzilla/levenshtein/simt.cuh`, each vendor launches them from its own host code in `cuda.cuh` and `rocm.cuh`, compiled into the library by `src/capabilities/cuda.cu` and `src/capabilities/rocm.hip`, and the Metal ones live beside them in `metal.h` and `metal.metal`, compiled by `src/capabilities/metal.c`. ## Dynamic Dispatch Due to the high-level of fragmentation of SIMD support in different CPUs, StringZilla names its backends after select CPU generations and instruction-set extensions. The full v5 set spans the serial SWAR fallback, x86 (Westmere, Goldmont, Haswell, Skylake, Ice Lake), Arm (NEON, NEON-AES, NEON-SHA, SVE, SVE2, SVE2-AES), RISC-V (RVV, RVV-crypto), LoongArch (LASX), IBM Power (PowerVSX), and WebAssembly (v128 and relaxed v128). The libraries compile every one of them the toolchain builds, as one probe per kit under `probes/` finds, at the architecture's baseline flags, so one binary runs on any CPU of its architecture and picks among them at runtime. GPUs add one capability per vendor, `cuda`, `rocm` and `metal`, which `sz_capabilities_enabled_cuda` and its ROCm and Metal twins report for one device, named by that runtime's ordinal. In C, `sz_capabilities_detected_cpu` reports what the CPU runs as a bitmask, `sz_capabilities_compiled_cpu` what the binary holds kernels for, and `sz_capabilities_enabled_cpu` both at once, while `sz_capabilities_name` spells any mask into a buffer of `STRINGZILLA_CAPABILITIES_NAME_CAPACITY` bytes. Every verb has a dispatch point, like `sz_find_best`, which takes such a mask and a stream, and runs the best capability the mask shares with the verb's list, `serial` first on the CPU. The stream is null on the CPU, and on a GPU names the device, null meaning the default one, while `sz_stream_init_cuda(ordinal, &stream)` and its ROCm and Metal twins make one on any other. Every dispatch point returns a status, `sz_missing_kernel_k` when no capability in the mask has the kernel. ```c sz_capability_t capabilities = sz_cap_serial_k; sz_capabilities_enabled_cpu(&capabilities); // detected on this CPU and compiled into this binary sz_cptr_t match = NULL; sz_find_best(text, length, pattern, 3, &match, capabilities, NULL); // the best capability sz_find_best(text, length, pattern, 3, &match, capabilities & ~sz_cap_sve_k, NULL); // anything but SVE sz_find_best(text, length, pattern, 3, &match, sz_cap_serial_k, NULL); // the SWAR reference ``` Each capability kernel is also callable directly, with the same arguments short of the mask. Use it to guarantee constant performance, or to explore how different algorithms scale on your hardware. Header-only C builds, with `STRINGZILLA_HEADER_ONLY=1`, compile the kernels into your translation unit for exactly that, while their dispatch points return `sz_missing_library_k`, so the C++ layer falls back to the serial kernels and the bindings link the library. ```c sz_find_westmere(text, length, pattern, 3, &match, NULL); // Intel Westmere+ SSE4.2 sz_find_haswell(text, length, pattern, 3, &match, NULL); // Intel Haswell+ AVX2 sz_find_skylake(text, length, pattern, 3, &match, NULL); // Intel Skylake+ AVX-512 sz_find_neon(text, length, pattern, 3, &match, NULL); // Arm NEON 128-bit sz_find_sve(text, length, pattern, 3, &match, NULL); // Arm SVE 128/256/512/1024/2048-bit ``` Picking a capability costs about a nanosecond per call: noise for long inputs, but not for hot short-string paths, like a sort's comparator or a per-token byte search. There, call a capability's kernel directly, like `sz_order_neon` or `sz_find_byte_haswell`, or resolve one once through `sz_find_kernel_punned`, and call it many times: ```c sz_kernel_order_t order = NULL; sz_capability_t capability = 0; sz_find_kernel_punned(sz_kernel_order_k, capabilities, (sz_kernel_punned_t *)&order, &capability); sz_ordering_t ordering; order("apple", 5, "banana", 6, &ordering, NULL); ``` It picks exactly what the dispatch point picks for the same mask, and returns `sz_missing_kernel_k` when no capability in the mask has the kernel. Each family exports its own finder over its kinds, like `sz_compare_find_kernel`, and `sz_find_kernel_punned` covers every family through one entry point. The kind names the verb, `sz_kernel__k`, and the kernel is cast to that verb's pointer type, `sz_kernel__t`. In C++, every wrapper that takes a mask defaults to `sz::default_capabilities()`, the enabled CPU mask, and `sz::device_t` answers the same three questions for any device and prepares a CPU thread through `configure_thread`. Similarly, in Python, `sz.Capability` flags carry the same masks, and any call can be narrowed: ```python import stringzilla as sz sz.cpu_capabilities_enabled() # e.g. sz.find("haystack", "st", capabilities=sz.Capability.SERIAL) # one call on the scalar kernel ``` [usearch]: /docs/usearch/ [ucall]: /docs/ucall/ [uform]: /docs/uform/ [simsimd]: https://github.com/ashvardanian/SimSIMD [faq-simd]: https://en.wikipedia.org/wiki/Single_instruction,_multiple_data [faq-swar]: https://en.wikipedia.org/wiki/SWAR [faq-shell]: https://github.com/ashvardanian/StringZilla-CLI [first-issues]: https://github.com/ashvardanian/StringZilla/issues [faq-dbms]: https://en.wikipedia.org/wiki/Database