Substring search looks simple: find the first occurrence of a needle inside a haystack. Classic algorithms such as Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, and Two-Way matching focus on reducing redundant comparisons and preserving good asymptotic behavior. Those guarantees matter, but they do not automatically produce the fastest implementation on modern CPUs.
SIMD-friendly substring search starts from a different observation: comparing one byte is not much cheaper than comparing 16, 32, or 64 bytes when the data is already in vector registers. Instead of building a complex automaton or shift table for every pattern, a vectorized search can cheaply test many candidate positions at once, collapse the result to a bit mask, and perform exact comparison only where the mask says a match is plausible.
The most portable form uses a first-and-last-byte predicate. Broadcast the first byte of the needle into one vector and a selected trailing byte into another. Load two haystack vectors offset by the needle length, compare both vectors in parallel, AND the comparison results, and iterate over the set bits. This turns substring search into a filtering pipeline: SIMD finds candidate starting offsets, scalar code verifies only those candidates.
This topic teaches the pattern rather than one instruction set. The same idea appears in SSE2, AVX2, AVX-512, ARM NEON, AArch64, and SWAR implementations. It is especially useful in parsers, query engines, log scanners, text indexes, protocol analyzers, and runtimes where substring search sits on a hot path and needles are short enough that branchy textbook algorithms underuse the CPU.
A vectorized substring search does not prove a full match for every byte position. It first asks a cheaper question: “At which offsets do a few discriminating bytes match?” For a needle such as "cat", any real match must start with 'c' and have 't' two bytes later. If either byte differs, the candidate can be rejected without comparing the middle byte.
The SIMD loop evaluates that predicate for an entire vector width at once. With AVX2, one iteration can evaluate 32 possible starting positions. Most positions are rejected by the first-and-last-byte predicate, so expensive exact comparisons happen only for the small set of mask bits that survive.
Vector comparisons produce lane-wise results. A byte lane is all ones when equal and all zeros otherwise. A movemask instruction compresses those high bits into an ordinary integer bitset. The search loop can then use scalar bit operations such as count-trailing-zeros and clear-lowest-set-bit to enumerate candidate positions.
This is the bridge between SIMD data parallelism and scalar control flow. The vector path does wide rejection. The scalar path handles rare verification and returns the exact byte offset.
The generic predicate uses equality comparisons, bitwise AND, and movemask extraction. It maps well to SSE2, AVX2, AVX-512 masks, NEON-style vector compares, and SWAR zero-byte tests. Some x86 instruction sets also expose specialized string or sum-of-absolute-differences instructions such as PCMPESTRM and MPSADBW, but those are not automatically faster; the source measurements found the generic SIMD algorithm more reliable across machines.
Use vector instructions to generate a dense candidate mask, not to replace the entire string-matching algorithm. The exact verifier stays simple, while the vector predicate removes most positions before they reach scalar comparison.
For a needle of length k, choose two bytes that every match must contain at known offsets. The simplest choice is byte 0 and byte k - 1. Broadcast those bytes into vector registers, then load haystack data at the candidate start and at candidate start plus k - 1. Equal lanes in both vectors mark possible matches.
needle = "cat"
first = broadcast('c')
last = broadcast('t')
for i in range(0, haystack_len, vector_width):
a = load(haystack + i)
b = load(haystack + i + needle_len - 1)
mask = movemask((a == first) & (b == last))
verify_each_set_bit(mask)For the haystack fragment "a_cat_tries", the first-byte vector marks positions containing 'c', and the trailing-byte vector marks positions whose byte two characters later is 't'. The AND of those masks leaves the starting position for "cat". Positions where only one condition holds are discarded without calling memcmp.
A practical AVX2 implementation keeps the hot loop small: two unaligned vector loads, two byte equality comparisons, one bitwise AND, one movemask, and a scalar loop over set bits. The verifier can skip the first and selected trailing bytes because the vector predicate already proved they match.
size_t find_avx2(const char* s, size_t n,
const char* needle, size_t k) {
const __m256i first = _mm256_set1_epi8(needle[0]);
const __m256i last = _mm256_set1_epi8(needle[k - 1]);
for (size_t i = 0; i + k + 31 <= n; i += 32) {
__m256i a = _mm256_loadu_si256((const __m256i*)(s + i));
__m256i b = _mm256_loadu_si256((const __m256i*)(s + i + k - 1));
__m256i eq = _mm256_and_si256(
_mm256_cmpeq_epi8(a, first),
_mm256_cmpeq_epi8(b, last));
uint32_t mask = (uint32_t)_mm256_movemask_epi8(eq);
while (mask != 0) {
unsigned bit = __builtin_ctz(mask);
size_t pos = i + bit;
if (memcmp(s + pos + 1, needle + 1, k - 2) == 0) {
return pos;
}
mask &= mask - 1;
}
}
return SIZE_MAX;
}This sketch omits important production details: short-needle handling, tail processing, page-boundary safety, dispatch, and architecture-specific implementations. Its purpose is to show the core mechanism: vector rejection first, exact scalar verification second.
The first and last bytes are easy but not always best. If the haystack contains many repeated 'A' bytes and the needle is "AjohndoeA", both predicate bytes are common and the candidate mask becomes noisy. A better implementation chooses the second predicate byte as the farthest byte in the needle that differs from the first byte, or chooses bytes based on estimated selectivity.
Observability systems often scan large contiguous buffers for fixed tokens: severity labels, field names, separators, error markers, and trace identifiers. SIMD-friendly substring search accelerates the first-pass scan while preserving exact verification before a match is reported. This is useful when building custom log processors or query operators that cannot afford a full regex engine for simple literals.
HTTP, JSON, CSV, SQL, and binary-text hybrid protocols contain delimiters and keywords that are short, fixed, and frequent. A vectorized literal finder can locate candidate delimiters or keywords before a higher-level parser validates grammar. This keeps branch-heavy parsing code away from positions that obviously cannot begin a token.
Database filters, inverted-index builders, trigram indexes, and query engines sometimes need exact substring checks after coarser filters have selected candidate documents or rows. SIMD substring search is a good fit for that verification layer: the input is already narrowed, but the remaining buffers may be large enough that scalar byte-by-byte checks become visible.
Standard libraries need general-purpose behavior, memory safety, and stable performance for unknown inputs. Specialized application runtimes can trade some generality for throughput when lengths are known, buffers are padded, and short needles dominate. The source article explicitly notes that its routines receive lengths and may read past the logical end without guard handling; production libraries must close those gaps.
Keep one public API and several private kernels. Dispatch once based on CPU features and needle length, then call a kernel specialized for AVX2, SSE2, NEON, AArch64, SWAR, or scalar fallback. Avoid checking CPU features inside the hot loop.
using Finder = size_t (*)(const char*, size_t, const char*, size_t);
Finder select_finder(size_t needle_len, CpuFeatures cpu) {
if (needle_len == 0) return find_empty;
if (needle_len == 1) return find_byte;
if (cpu.avx2) return find_avx2;
if (cpu.sse2) return find_sse2;
if (cpu.neon) return find_neon;
return find_two_way_or_scalar;
}Very short needles deserve special handling. Length-one search is memchr. Length-two and length-three patterns can often be verified with a single unaligned word load or a small integer compare. Once the needle is long enough, the first-and-selected-byte predicate becomes attractive because it rejects candidates before calling a longer verifier.
The simple vector loop loads beyond the current vector start by k - 1 bytes. That is safe only if the implementation proves the load remains inside allocated memory or if the buffer includes readable padding. Production code usually handles a vectorized main loop followed by a scalar tail, uses masked loads where available, or arranges page-safe padding in the owning buffer.
Benchmark with needles and haystacks that match production. Uniform random text, English text, JSON logs, source code, binary payloads, and repeated-character buffers produce different candidate-mask densities. A predicate that looks excellent on random ASCII can degrade when both selected bytes are common delimiters.
memcmp calls.strstr across tested platforms, while MPSADBW and PCMPESTRM were inconsistent and sometimes slower.strstr can be unfair if the SIMD routine receives explicit lengths and the library routine must discover string ends.