Production Case Study: Why ripgrep Is So Fast (Aho-Corasick, Boyer-Moore & SIMD Teddy)

1. Architecture of a High-Throughput Search Pipeline

A production code/log search tool (ripgrep, GNU grep, Intel Hyperscan) is structured as a multi-stage funnel designed to keep the inner loop purely vectorized and branch-free:

1. AST Literal Extraction: Given a regex $R$, the compiler analyzes the syntax tree to extract a small set of required prefix or inner literals $L(R)$. For example, \b(?:foo|bar)_baz\d+ yields the exact prefix set $\{\texttt{"foo\_baz"}, \texttt{"bar\_baz"}\}$ (or their common suffix $\texttt{"\_baz"}$).
2. Prefilter Selection:
   • $|L| = 1$ (Single Literal): Dispatches to Packed-Pair SIMD (_mm256_cmpeq_epi8 on the two rarest bytes in the literal, inspired by Horspool's guard byte) with a Two-Way linear-time verifier.
   • $2 \le |L| \le 64$ (Small Multi-Pattern): Dispatches to SIMD Teddy, which uses the SSSE3/AVX2 in-register parallel table lookup instruction pshufb / vpshufb (_mm256_shuffle_epi8) on the low and high 4-bit nibbles of each text byte to test up to 8 pattern buckets across 32 byte positions simultaneously.
   • $|L| > 64$ (Large Multi-Pattern): Dispatches to an Aho-Corasick automaton (using a contiguous precomputed byte-transition table near the root and compact transitions deeper in the trie).
3. Line-Boundary Expansion & Regex Verification: Only when the SIMD prefilter flags a match at byte offset $k$ does ripgrep scan backward/forward for the enclosing '\n' bytes and run the full lazy-DFA / Thompson NFA on that single line.

2. Inside SIMD Teddy: Nibble Bitmasks via vpshufb

How can a CPU test whether 32 text bytes match any of 8 arbitrary characters in just a few instructions? An AVX2 _mm256_cmpeq_epi8 only compares against one broadcast byte. Teddy exploits the fact that _mm256_shuffle_epi8(table, index) treats each half of a 256-bit register as a 16-entry lookup table indexed by the lower 4 bits ($0..15$) of each byte in index!

• Each byte $b \in [0, 255]$ is split into its low nibble $b_{\text{lo}} = b \mathbin{\&} \text{0x0F} \in [0, 15]$ and high nibble $b_{\text{hi}} = (b \gg 4) \mathbin{\&} \text{0x0F} \in [0, 15]$.
• We group our patterns into 8 buckets $0..7$ (one bit per bucket in a uint8 mask). For pattern prefix byte $p$ in bucket $k$, we set bit $k$ in table_lo[p & 0x0F] and bit $k$ in table_hi[p >> 4].
• At runtime, for 32 input bytes $T[i..i+31]$, two parallel shuffles compute res = _mm256_and_si256(shuffle(table_lo, T_lo), shuffle(table_hi, T_hi)). Byte lane $j$ of res has bit $k$ set if and only if $T[i+j]$ matches both the low nibble and high nibble of a pattern in bucket $k$! Doing this across the first 2 or 3 bytes of each pattern (with shifted alignment alignr) eliminates almost all false positives before leaving SIMD registers.

3. Visual Trace: SIMD Teddy Nibble-Mask Lookup (vpshufb)

4. Reference Implementation: Teddy Nibble-Mask Matcher

#include <array>
#include <cstdint>
#include <cstring>
#include <string_view>
#include <vector>

// Portable 2-byte Teddy Nibble Fingerprint Engine (models vpshufb bucket filtering)
class Teddy2BytePrefilter {
public:
    // Up to 8 patterns (1 bit per pattern bucket in uint8_t mask)
    explicit Teddy2BytePrefilter(const std::vector<std::string_view>& patterns)
        : patterns_(patterns) {
        lut_lo_[0].fill(0); lut_hi_[0].fill(0);
        lut_lo_[1].fill(0); lut_hi_[1].fill(0);
        for (size_t b = 0; b < patterns.size() && b < 8; ++b) {
            uint8_t bit = static_cast<uint8_t>(1u << b);
            for (size_t pos = 0; pos < 2; ++pos) {
                uint8_t ch = static_cast<uint8_t>(patterns[b][pos]);
                lut_lo_[pos][ch & 0x0F] |= bit;
                lut_hi_[pos][ch >> 4]   |= bit;
            }
        }
    }

    // Scans text and returns (offset, pattern_id) matches
    std::vector<std::pair<size_t, size_t>> find_all(std::string_view text) const {
        std::vector<std::pair<size_t, size_t>> hits;
        if (text.size() < 2) return hits;

        uint8_t prev_m0 = 0;
        for (size_t i = 0; i < text.size(); ++i) {
            uint8_t b = static_cast<uint8_t>(text[i]);
            // Parallel nibble table lookup (in AVX2: 2x _mm256_shuffle_epi8 + _mm256_and_si256)
            uint8_t m0 = lut_lo_[0][b & 0x0F] & lut_hi_[0][b >> 4];
            uint8_t m1 = lut_lo_[1][b & 0x0F] & lut_hi_[1][b >> 4];

            // Bucket bit k is set in cand iff text[i-1] matched pos 0 AND text[i] matched pos 1
            uint8_t cand = prev_m0 & m1;
            prev_m0 = m0;

            while (cand != 0) {
                int bucket = __builtin_ctz(cand);
                cand &= static_cast<uint8_t>(cand - 1);
                size_t start = i - 1;
                std::string_view pat = patterns_[bucket];
                if (start + pat.size() <= text.size() &&
                    std::memcmp(text.data() + start, pat.data(), pat.size()) == 0) {
                    hits.emplace_back(start, static_cast<size_t>(bucket));
                }
            }
        }
        return hits;
    }

private:
    std::vector<std::string_view> patterns_;
    std::array<std::array<uint8_t, 16>, 2> lut_lo_{};
    std::array<std::array<uint8_t, 16>, 2> lut_hi_{};
};