Building Rexa: A Multi-Engine Regex Engine in Go That Outperforms the Standard Library

Repository: github.com/HimClix/rexa

Install: go get github.com/himclix/rexa@v0.1.0

Introduction

Regular expressions are one of those foundational tools that every language provides but few get right. In Go, the standard regexp package makes a deliberate tradeoff: it guarantees linear-time matching by implementing a RE2-style engine, but this comes at the cost of missing widely-used features and, counterintuitively, slower performance than scripting languages that delegate to optimized C libraries.

I spent several weeks building rexa — a pure-Go regex engine that resolves both problems simultaneously. It beats Go’s standard library on every benchmark I’ve tested (2x to 50x faster) while adding the PCRE features that Go developers have been requesting for over eight years.

This article documents the complete technical journey: the problem analysis, the architectural decisions, the engine implementations, the optimization process, and the correctness challenges I encountered along the way.

The Problem Space

Problem 1: Performance Gap

To understand why Go’s regex is slow, you need to understand what it’s doing differently from everyone else.

Most languages — Python, Ruby, Perl, Java, JavaScript — use backtracking engines derived from Henry Spencer’s original implementation. These engines compile a regex into a tree of opcodes and execute them recursively, backtracking when a branch fails. For typical patterns on typical inputs, this is fast. For pathological patterns (like (a+)+$ on "aaa...!") it's exponentially slow — but most developers never hit those cases.

Go’s regexp package, based on Russ Cox's RE2 engine, takes a different approach. It uses the Thompson NFA simulation algorithm, which simulates all possible NFA states simultaneously. This guarantees O(n·m) worst-case time (where n is input length, m is pattern size) — no exponential blowup, ever. The price: every character of input requires O(m) work to update all active NFA states, even in the common case.

The performance impact is measurable. On the Benchmarks Game regex-redux benchmark, Go’s regex is 5–10x slower than Python. This seems paradoxical — Go is a compiled language, Python is interpreted. The explanation: Python’s re module delegates to C's PCRE library, which has decades of optimization including JIT compilation. Go's regexp is a pure-Go implementation that prioritizes correctness guarantees over raw speed.

Nightfall AI, a security company that processes millions of regex matches per second for their data loss prevention product, benchmarked Go’s regexp against alternatives. Their finding: "the default Go regexp library was definitely the slowest and most memory intensive" — 30-40x slower than Google RE2 (via cgo) and Intel Hyperscan, and consuming up to 7x more memory.

The open issue golang/go#26623 tracks performance improvements to Go’s regex, but the Go team has been explicit that they won’t sacrifice the engine’s simplicity for speed: “Russ Cox, the author of both regexp and RE2, has expressed his desire to prevent regexp from becoming as over-engineered as RE2.”

Problem 2: Missing Features

Go issue #18868, opened in January 2017, has accumulated 180+ comments from developers requesting lookahead and lookbehind support. The Go team’s position is firm:

“The current regexp package gives you a guarantee: it will make a single scan over the input and run in O(n) time, where n is the size of the input. We aren’t going to break that guarantee in order to provide some feature.”

The missing features include:

• Lookahead (?=X) — assert that what follows matches X, without consuming input
• Negative lookahead (?!X) — assert that what follows does NOT match X
• Lookbehind (?<=X) — assert that what precedes matches X
• Negative lookbehind (?<!X) — assert that what precedes does NOT match X
• Backreferences \1, \k<name> — match the same text that a capture group already matched
• Atomic groups (?>X) — match X without allowing backtracking into it
• Possessive quantifiers X++, X*+ — greedy match that never backtracks

These aren’t exotic features. They’re supported by every major regex flavor: PCRE, Java, .NET, Python, Ruby, JavaScript, and Perl. Developers porting code from any of these languages hit the wall immediately.

The real-world impact is concrete. Telegraf developers reported being “impacted by the non support of regex lookaheads or lookbehinds” in their log parsing pipeline. Configuration files, data extraction patterns, and validation rules that work in every other language simply don’t work in Go.

The Theoretical Constraint

The Go team’s position isn’t arbitrary. There’s a genuine theoretical constraint:

• Regular expressions (in the formal CS sense) — concatenation, alternation, Kleene star — can be matched in O(n·m) time by NFA simulation. This is what Go’s regexp supports.
• Lookaheads and lookbehinds (without backreferences) can also be matched in polynomial time. A 2024 paper proved O(n·m) for JavaScript regex matching without backreferences.
• Backreferences make the matching problem NP-complete (proven via reduction from 3-SAT). There is no polynomial-time algorithm for general backreference matching unless P=NP. Every engine that supports backreferences — PCRE2, Java, .NET — uses exponential-time backtracking.

The question becomes: is it possible to support PCRE features safely — getting the performance benefits for patterns that don’t need backtracking, while bounding the worst case for patterns that do?

The answer is yes. And the key is a multi-engine architecture.

Why Existing Solutions Fall Short

Before building rexa, I evaluated every Go regex alternative:

dlclark/regexp2 — Feature-complete but slow and unsafe

regexp2 is a port of .NET's System.Text.RegularExpressions engine to Go. It supports the full PCRE feature set including lookaheads, lookbehinds, and backreferences.

The problem is twofold:

1. It’s slower than Go’s stdlib. In benchmarks by Rustem Kamalov, “almost all alternative solutions give a speedup of 8–130x, except for Regexp2, which turns out to be slower than the standard library.”
2. It uses unbounded backtracking. Patterns like (a+)+$ on adversarial input exhibit catastrophic backtracking — O(2^n) time. In a server processing user-provided regex (log parsers, search engines, WAF rules), this is a denial-of-service vector. regexp2 provides a timeout mechanism, but this is a wall-clock timeout, not a step-bounded limit — it doesn't provide deterministic behavior.

wasilibs/go-re2 — Fast but featureless

go-re2 wraps Google's C++ RE2 engine via WebAssembly, avoiding cgo while getting near-native RE2 performance. For large inputs and complex patterns, it's 8-40x faster than Go's stdlib.

But it provides the same feature set as Go’s regexp — no lookaheads, no backreferences. It solves the speed problem but not the feature problem.

go-pcre — The cgo trap

go-pcre wraps the C PCRE library. It's fast (PCRE has JIT compilation) and feature-complete. But it requires cgo, which introduces serious practical problems:

• go build no longer works standalone. You need a C compiler and the PCRE development headers installed on every build machine.
• Cross-compilation breaks. GOOS=linux GOARCH=arm64 go build — the standard Go cross-compile workflow — doesn't work with cgo without a cross-compilation C toolchain.
• Docker scratch/distroless images can’t be used. The binary dynamically links against libc and libpcre. You need a full OS image.
• CI complexity. Every OS/architecture combination in your CI matrix needs libpcre-dev or equivalent installed.
• go install fails for users. Anyone running go install github.com/your/tool without libpcre gets a build error.

For library code that others import, cgo is a non-starter.

The Gap

The landscape has a clear gap, as illustrated here:

Feature-complete (PCRE)
                           │
                  regexp2   │   go-pcre
                  (slow,    │   (fast, but
                   unsafe)  │    cgo required)
                           │
    ───────────────────────┼───────────────────────
                           │
                  regexp    │   go-re2
                  (slow,    │   (fast, but
                   safe)    │    Wasm dep)
                           │
                    RE2 feature set only

rexa targets the empty quadrant: fast, feature-complete, pure Go, and safe.

Architecture Overview

The central design decision in rexa is the multi-engine architecture. Instead of one execution strategy for all patterns, rexa analyzes each pattern at compile time and selects the fastest engine that can handle it correctly.

High-Level Architecture

                         ┌──────────────────────┐
                         │   rexa.Compile(pat)  │
                         └──────────┬───────────┘
                                    │
                    ┌───────────────▼───────────────┐
                    │      Compilation Pipeline     │
                    │                               │
                    │  ┌────────┐  ┌────────┐       │
                    │  │ Lexer  ├──► Parser │       │
                    │  └────────┘  └───┬────┘       │
                    │              ┌───▼────┐       │
                    │              │  AST   │       │
                    │              └───┬────┘       │
                    │         ┌───────▼────────┐    │
                    │         │   Compiler     │    │
                    │         │  (Thompson's   │    │
                    │         │  construction) │    │
                    │         └───────┬────────┘    │
                    │         ┌───────▼────────┐    │
                    │         │   Optimizer    │    │
                    │         │  (prefix, DFA  │    │
                    │         │   analysis)    │    │
                    │         └───────┬────────┘    │
                    └─────────────────┼─────────────┘
                                      │
                              ┌───────▼────────┐
                              │    Program     │
                              │   ([]Inst +    │
                              │    metadata)   │
                              └───────┬────────┘
                                      │
                    ┌─────────────────▼─────────────────┐
                    │         Meta Engine               │
                    │    (selects fastest engine        │
                    │     based on program analysis)    │
                    └──┬──────┬──────┬────── ┬──────────┘
                       │      │      │       │
              ┌────────▼ ┐ ┌──▼────┐ ┌▼─────┐ ┌▼──────────┐
              │ Literal  │ │ Lazy  │ │ Pike │ │ Bounded   │
              │ Scanner  │ │ DFA   │ │ VM   │ │ Backtrack │
              │          │ │       │ │      │ │           │
              │ Boyer-   │ │ O(n)  │ │O(n·m)│ │O(bounded) │
              │ Moore    │ │amort. │ │      │ │           │
              │ O(n/m)   │ │       │ │      │ │           │
              └──────────┘ └───────┘ └──────┘ └───────────┘
                  ▲             │          ▲         ▲
                  │             │ cache    │         │
                  │             │ overflow │ one-pass│
                  │             └──────────┘ failed  │
                  │     prefilter                    │
                  └──── boost ── any engine can ─────┘
                                 use literal
                                 prefix scan

Engine Selection Logic

The meta engine applies these rules in order:

1. Is the pattern a pure literal?
   → Literal Scanner (Boyer-Moore / strings.Index)

2. Does the pattern contain backreferences (\1, \k<name>)?
   → Bounded Backtracker

3. Does the pattern contain word boundaries (\b, \B)?
   → Pike VM (boundaries need position context)

4. Otherwise:
   → Lazy DFA (with Pike VM fallback for captures)

Each engine can also fall back to the next tier:

• Lazy DFA cache overflow → Pike VM
• DFA abandoned (too many resets) → Pike VM
• Any engine for FindString → DFA finds position, Pike VM extracts boundaries

Data Flow

User calls: re.MatchString("input")
                │
                ▼
    ┌─ Is literal? ── Yes ──► strings.Index ──► return bool
    │
    ├─ Has DFA? ──── Yes ──► LazyDFA.SearchBool ──► return bool
    │                            │
    │                         (cache hit: O(1) per char)
    │                         (cache miss: compute + cache)
    │                         (abandoned: fall to Pike VM)
    │
    └─ Pike VM ──────────────► SearchBool ──► return bool
                                  │
                               (machine pool: 0 allocs)
                               (bitset dedup: O(n·m))

User calls: re.FindString("input")
                │
                ▼
    ┌─ Is literal? ── Yes ──► strings.Index ──► return s[start:end]
    │
    ├─ Has DFA? ──── Yes ──► LazyDFA.SearchInto (find position)
    │                            │
    │                            ▼
    │                    PikeVM.Match at position (extract boundaries)
    │                            │
    │                            ▼
    │                    return input.SliceString(start, end)
    │
    └─ Pike VM Search ──► return match boundaries

Deep Dive: The Compilation Pipeline

Stage 1: Lexer

The lexer (syntax/lexer.go) converts a pattern string into a flat stream of tokens. It handles:

• Single-character escapes: \n, \t, \r, \\, \.
• Character class shorthands: \d, \D, \w, \W, \s, \S
• Unicode property escapes: \p{L}, \p{Nd}, \P{Lu}, \pL
• Quantifier parsing: {3}, {3,}, {3,7}
• Group prefix parsing: (?:, (?=, (?!, (?<=, (?<!, (?>, (?P<name>, (?i)
• Backreference parsing: \1 through \9

The lexer is position-tracking — every token carries the byte offset of its source, which enables precise error messages:

rexa: syntax error at position 5 in `(abc`: unclosed group

Stage 2: Parser

The parser (syntax/parser.go) uses recursive descent to convert tokens into an AST. The grammar:

Plaintext

Regex      → Alternate
Alternate  → Concat ('|' Concat)*
Concat     → Repeat+
Repeat     → Atom Quantifier?
Quantifier → ('*' | '+' | '?' | '{n,m}') ('?' | '+')?
Atom       → Literal | '.' | CharClass | Group | Anchor | Backref

Operator precedence is implicit in the grammar structure: alternation binds loosest, then concatenation, then quantifiers bind tightest.

The parser also manages:

• Capture group indexing — assigns sequential indices to () groups
• Named capture registration — maps (?P<name>...) names to indices
• Flag propagation — (?i) sets case-insensitive for subsequent nodes, (?i:...) scopes it

Stage 3: Compiler (Thompson’s Construction)

The compiler (compiler/nfa.go) transforms the AST into a linear instruction program using Thompson's construction. Each AST node compiles to a fragment — a small subgraph with a start instruction and a list of unpatched output edges:

OpLiteral('a')  →  InstRune{Rune:'a', Out:?}

OpConcat(A, B)  →  compile(A), compile(B), patch A.out → B.start

OpAlternate(A, B) →  InstSplit{Out:A.start, Out1:B.start}
                      merge A.out and B.out

OpStar(A)  →  InstSplit{Out:A.start, Out1:?}
              patch A.out → split
              (greedy: Out=body, lazy: Out=skip)

The key insight in Thompson’s construction: the resulting NFA has exactly one instruction per AST node, so program size is O(m) where m is the pattern size.

Stage 4: Optimizer

The optimizer (compiler/optimize.go) runs several analysis passes on the compiled program:

• Literal prefix extraction — walks from the start instruction following only InstRune instructions. If a contiguous literal prefix exists (e.g., "http://" from http://\w+), it's stored for prefilter use.
• IsLiteral detection — if the entire program is a sequence of InstRune → InstMatch with no splits, groups, or classes, the pattern is flagged as a pure literal.
• Anchor analysis — detects ^ at start (AnchoredStart), presence of $/\b (HasAnchors), and whether only start anchors are present (OnlyStartAnchor). This determines DFA eligibility.
• HasEndAnchor detection — for the lazy DFA, patterns with $ need end-of-input validation after DFA matching.

Deep Dive: The Execution Engines

Engine 1: Literal Scanner

For patterns that are pure literal strings (no metacharacters), regex machinery is pure overhead. The literal scanner bypasses all automaton logic and uses strings.Index — Go's built-in string search that uses an optimized Rabin-Karp implementation.

The fast path in rexa.go:

func (re *Regexp) MatchString(s string) bool {
    if lit := re.meta.Literal(); lit != nil {
        _, _, ok := lit.SearchString(s, 0)
        return ok
    }
    // ... fall through to DFA/Pike VM
}

SearchString operates directly on the raw string bytes. No Input struct allocation, no rune conversion, no result struct. The function returns three scalars that live on the stack.

Complexity: O(n/m) average case (Boyer-Moore skip logic), O(n) worst case.

Result: 7.5 ns per match vs stdlib’s 190 ns — 25x faster, 0 allocations.

Engine 2: Lazy DFA

The lazy DFA is the most complex engine and the primary source of rexa’s speed advantage over stdlib.

How it works

A DFA (Deterministic Finite Automaton) processes one character at a time with a single table lookup — O(1) per character. But converting an NFA to a DFA can produce O(2^m) states (where m is the NFA size), making upfront construction prohibitively expensive for large patterns.

The lazy DFA avoids this by building states on demand during matching:

             ┌──────────────────────────────────┐
             │         Lazy DFA State           │
             │                                  │
             │  nfaStates: [2, 5, 7]            │  ← set of NFA PCs
             │  isMatch: false                  │
             │  ascii: [128]*dfaState           │  ← transition table
             │  asciiDone: [2]uint64            │  ← which slots computed
             │  next: map[rune]*dfaState        │  ← non-ASCII overflow
             │                                  │
             └──────────────────────────────────┘

For each (state, character) pair:

• Check the ASCII transition table (128-entry array, indexed by character). O(1) lookup.
• If not computed yet, compute the epsilon closure of the NFA states reachable by consuming that character. O(m) per new state.
• Cache the result. Future lookups for the same pair are O(1).

The cache is bounded (default 10K states). If it fills up:

• Flush the entire cache
• Rebuild from scratch on subsequent matches
• If flushing happens 5+ times, abandon the DFA and fall back to Pike VM

This graceful degradation means the lazy DFA never hangs or consumes unbounded memory, even on pathological patterns.

ASCII Fast Path

For the 99% of real-world input that’s ASCII, transitions use a fixed 128-entry array instead of a hash map:

Go

if r < 128 {
    idx := int(r)
    word := idx / 64
    bit := uint(idx % 64)
    if from.asciiDone[word]&(1<<bit) != 0 {
        return from.ascii[idx]  // single array lookup
    }
    // compute and cache
}

Two uint64 bitfields (asciiDone) track which ASCII slots have been computed, avoiding the need for nil checks.

Start State Caching

The epsilon closure for the start state is computed once and cached on the LazyDFA struct. Without this optimization, every call to matchAt would recompute the closure — the profiler showed this was 50% of all DFA allocations.

Arena Allocation

NFA state sets ([]int) for each DFA state are allocated from a contiguous arena ([]int slab) instead of individual make([]int, n) calls. This reduces GC pressure and improves cache locality.

Complexity: O(n) amortized time, O(min(2^m, cache_cap)) bounded space.

Engine 3: Pike VM

The Pike VM implements the standard Thompson NFA simulation algorithm with capture group tracking, based on Rob Pike’s implementation.

Two thread lists

The VM maintains two thread lists: current (threads being processed at the current input position) and next (threads that consumed a character and are waiting for the next position):

Position 0: current = [thread@inst3, thread@inst7, thread@inst12]
             Process each thread:
               inst3 matches 'a' → add to next
               inst7 doesn't match → die
               inst12 matches 'a' → add to next

Position 1: current = next, next = []
             Process each thread...

A bitset prevents duplicate threads (same instruction PC) in a list, ensuring O(n·m) time instead of exponential.

Machine Pool

The Pike VM’s per-match state (bitsets, thread lists) is allocated from a sync.Pool:

type machine struct {
    seenA, seenB *bitset.BitSet  // dedup bitsets
    lightA, lightB []lightThread  // thread lists (no-capture path)
    threadA, threadB []thread     // thread lists (capture path)
    input Input                   // reusable input slot
}

On the MatchString path, the machine is borrowed from the pool, used, and returned — 0 heap allocations after warmup.

The goto stepDone Optimization

For correct alternation semantics (cat|catalog should match "cat", not "catalog"), the first thread to reach InstMatch at any step must win. The Pike VM breaks out of the inner thread loop on the first match using goto stepDone, but continues to subsequent steps until next is empty:

case compiler.InstMatch:
    caps := CopySlots(t.captures)
    caps[0].End = sp
    matched = &MatchResult{Matched: true, Captures: caps}
    goto stepDone  // stop processing lower-priority threads

This ensures the highest-priority thread’s match is recorded, while still allowing other threads to advance for future steps.

Engine 4: Bounded Backtracker

For patterns with backreferences, atomic groups, or lookarounds, the bounded backtracker uses a classic frame-stack approach:

type btFrame struct {
    pc       int            // instruction pointer
    pos      int            // input position
    captures []CaptureSlot  // capture state
}

The engine pushes frames onto the stack for each choice point (InstSplit) and pops them on failure. The key difference from regexp2: every step increments a counter, and the engine stops when the counter exceeds the configured limit.

r.steps++
if r.steps > r.limit {
    return &MatchResult{Matched: false, Err: ErrBacktrackLimit}
}

Default limit: 1,000,000 steps. Configurable via CompileOptions{BacktrackLimit: N}. Set to -1 for unlimited (use only with trusted patterns).

Lookaround Implementation

Lookaheads spawn a sub-runner at the current position:

(?=X) at position 5:
  1. Save position (5)
  2. Create sub-runner, try matching X from position 5
  3. If X matches → continue outer match from position 5 (zero-width)
  4. If X fails → backtrack in outer matcht

Lookbehinds scan backward by trying the reversed sub-pattern at positions 0 through current:

(?<=X) at position 5:
  For tryPos = 0 to 5:
    Run sub-pattern X starting at tryPos
    If it matches AND ends at position 5 → lookbehind succeeds

This is O(n·m) for lookbehinds, which is acceptable given that lookbehinds are typically used with short, fixed-width patterns.

The Optimization Journey

Starting Point: 4,500x Slower Than stdlib

The initial implementation — lexer, parser, Thompson NFA compiler, Pike VM — worked correctly but was spectacularly slow:

\d+ on 20KB input:  rexa 364ms  vs  stdlib 82μs  →  4,500x slower

The Pike VM was allocating ~40,000 objects per FindString call: a new []CaptureSlot for every thread at every input position, plus MatchResult structs, Input structs, and bitsets.

Phase 1: Lazy DFA (535x improvement on \d+)

Adding the lazy DFA transformed search patterns from O(n²·m) (Pike VM tries every starting position) to O(n) (DFA scans through input in one pass):

Before: 364ms  →  After: 680μs  →  535x faster

Phase 2: Start State Caching (3x improvement)

Profiling showed that epsilonClosure was called at every search position to recompute the start state. Caching it eliminated 2/3 of all DFA allocations:

Before: 680μs / 30K allocs  →  After: 175μs / 10K allocs

Phase 3: Value-Return matchAt (eliminated 99.97% of DFA allocs)

The DFA’s matchAt returned *MatchResult — a heap allocation on every call. Changing it to return (bool, int, int) eliminated nearly all allocations:

Before: 175μs / 10K allocs  →  After: 43μs / 3 allocs

Phase 4: sync.Pool Machine Reuse (0 allocs for MatchString)

Pre-allocating bitsets and thread lists in a pooled machine struct made the MatchString path completely allocation-free:

Match: Before 297ns / 9 allocs  →  After 43ns / 0 allocs

Phase 5: ASCII Input Fast Path

For ASCII-only inputs (99% of real-world use), RuneAt returns rune(s[pos]) instead of materializing a []rune slice. SliceString returns s[start:end] (zero-copy substring).

Phase 6: Literal Bypass

For MatchString and FindString on literal patterns, rexa bypasses the engine entirely and calls strings.Index on the raw string. No Input struct, no MatchResult, no engine dispatch.

Correctness: The Hard Part

Every optimization introduced subtle bugs. Here are the ones that taught me the most.

Bug 1: DFA Returns Longest Match

The DFA always finds the longest match at a position because it runs until no more transitions are possible. But regex semantics require:

• Alternation priority: cat|catalog on "catalog" should return "cat" (first alternative wins)
• Lazy quantifiers: a.*?b on "aXbYb" should return "aXb" (shortest match)

Fix: The DFA finds the match position fast, then the Pike VM re-runs at that position to determine the correct boundaries.

Bug 2: Pike VM Thread Priority

The Pike VM’s addThread function for InstSplit was using Greedy/Lazy flags to determine which branch to explore first. But the compiler already encodes priority in the Out/Out1 wiring — for greedy splits, Out = body (preferred), Out1 = skip; for lazy, Out = skip (preferred), Out1 = body.

The fix: always process Out first, then Out1. The compiler's wiring handles the semantics.

Bug 3: Anchors in DFA

The DFA’s epsilon closure overapproximates zero-width assertions (^, $, \b) by always including the successor. This means ^abc$ would match anywhere in the DFA.

Fix: Handle anchors at the search level:

• ^ → only try position 0 (AnchoredStart flag)
• $ → validate match end equals input length (hasEndAnchor flag)
• \b → disable DFA, use Pike VM

Bug 4: Non-Multiline $ Matching Before \n

$ without the multiline flag should only match at end-of-text, not before \n. The initial implementation matched before \n unconditionally (multiline behavior), causing ^$ to incorrectly match "\n".

Fix: InstEndLine checks pos == input.Length() only. Multiline (?m) support (matching before \n) is deferred to a future version.

Benchmark Results

All benchmarks on Apple M3 Pro, Go 1.26, go test -bench -benchmem:

Benchmark              rexa          Go stdlib     Factor
──────────────────────────────────────────────────────────────
Literal (44KB text)    7.5 ns/0 B    190 ns/0 B    25x faster
Literal Long (44KB)    7.6 ns/0 B    371 ns/0 B    49x faster
\d+ search (20KB)      43 μs/464 B   82 μs/0 B     1.9x faster
Email search (20KB)    57 μs/337 B   106 μs/0 B    1.9x faster
IPv4 search (20KB)     31 μs/208 B   96 μs/0 B     3.1x faster
Anchored match (16ch)  43 ns/0 B     243 ns/0 B    5.7x faster

rexa beats Go’s standard library on every benchmark, while supporting features the standard library cannot match.

Lessons Learned

• Profile before optimizing. Every optimization I did was guided by go tool pprof. Without profiling, I would have optimized the wrong thing. The biggest wins came from eliminating allocations that I didn't even know existed.
• Correctness before performance. Every performance optimization introduced a correctness bug. The DFA longest-match issue, the thread priority bug, the anchor semantics — all were invisible until I wrote a comprehensive stdlib parity test.
• The multi-engine approach is essential. No single execution strategy is optimal for all patterns. The literal scanner, lazy DFA, Pike VM, and bounded backtracker each handle a class of patterns that the others can’t handle efficiently.
• Go’s escape analysis is your enemy and your friend. Understanding when the compiler stack-allocates vs heap-allocates is the difference between 0 allocs/op and 9 allocs/op. go build -gcflags='-m' is indispensable.
• Bounded backtracking is the right answer for backreferences. The Go team is right that unbounded backtracking is dangerous. regexp2's approach is unsafe. But bounded backtracking — with a configurable step limit and clear error reporting — gives developers the features they need with deterministic behavior.

What’s Next

• v0.2.0: One-pass DFA for O(n) capture extraction on unambiguous patterns
• v0.3.0: Arena allocator for zero-alloc FindString path
• v0.4.0: (?m) multiline flag support
• v1.0.0: Full stdlib parity including all edge cases

Repository: github.com/HimClix/rexa

README: github.com/HimClix/rexa#readme

Install: go get github.com/himclix/rexa@v0.1.0

Contributions welcome — see CONTRIBUTING.md.