Principle:ClickHouse ClickHouse SIMD Character Search
| Knowledge Sources | |
|---|---|
| Domains | String_Processing, SIMD |
| Last Updated | 2026-02-08 00:00 GMT |
Overview
Using parallel processing capabilities of modern CPUs to search for multiple characters simultaneously across 16-byte chunks of string data.
Description
SIMD character search exploits vector instructions to check 16 characters against a set of target characters in a single operation. The key insight is that instead of looping through each character and checking if it matches any of the search targets (O(n×m) comparisons), SIMD instructions can compare all 16 characters of a chunk against all search targets in parallel, producing a bit mask indicating matches. This transforms the problem from sequential comparison to parallel pattern matching.
The implementation uses two strategies: SSE2 for small character sets (creating comparison masks with OR operations) and SSE4.2 `pcmpestri` instruction for larger sets (dedicated string comparison instruction). The SSE4.2 instruction is particularly elegant - it was designed exactly for this use case and can handle up to 16 search characters natively.
Usage
Use SIMD character search when parsing structured text formats where delimiter detection is a bottleneck. This is the right choice for high-throughput data processing, log parsing, CSV/TSV processing, or any application that scans large text volumes for special characters. Choose standard library functions for small strings or when portability to exotic platforms is required.
Theoretical Basis
Performance Analysis:
Naive approach:
- For string of length n searching for m characters
- Complexity: O(n×m) comparisons
- Example: 1000-char string, 3 delimiters = 3000 comparisons
SIMD approach (SSE2):
- Process 16 characters per iteration
- Complexity: O(n/16 × m) SIMD operations + O(n) for remainder
- Example: 1000-char string, 3 delimiters = ~200 SIMD operations
- Speedup: ~15x for medium strings
SIMD approach (SSE4.2):
- Process 16 characters per iteration
- Complexity: O(n/16) SIMD operations (m is handled internally)
- Example: 1000-char string, any number of delimiters ≤16 = ~63 SIMD operations
- Speedup: ~48x for medium strings with multiple search chars
Why It Works:
Modern CPUs have dedicated execution units for SIMD operations that operate in parallel with scalar units. The `pcmpestri` instruction (SSE4.2) performs an implicit string comparison that would require many scalar instructions. The bit mask output directly indicates which positions matched, avoiding branching.
Optimization Thresholds:
- 1-4 characters: SSE2 is optimal
- 5-16 characters: SSE4.2 is optimal
- Strings < 16 bytes: SIMD overhead may not be worth it
- Strings > 64 bytes: SIMD provides consistent 5-10x speedup
Practical Considerations:
The approach handles:
- Unaligned memory access (SIMD supports unaligned loads)
- Partial chunks at string end (compare only valid bytes)
- Non-null-terminated strings (explicit end pointer)
- Negative searches (find characters NOT in set)
Cache effects are favorable since the algorithm processes strings sequentially, maintaining good cache locality.