Decrypt Go: Why Is Go’s Regexp So Slow, and Why That’s Actually Smart

Go’s Regex is Slower than Python. That’s not a Bug. It’s the Most Important Design Decision in the Package.

A Benchmark that Should Bother You

Input: 1000 as followed by one b (1001 characters total). The match succeeds.

// Go 1.23.4, Intel Xeon Platinum, linux/amd64 
strings.Contains(s, "b")     27.71 ns/op    ← baseline 
regexp `b`                    90.20 ns/op    ← 3.3x slower 
regexp `(a+)+b`           11,292    ns/op    ← 408x slower

Now the part that really stings. Python, same machine, same pattern:

// Python 3.12, same machine 
Complex regex (a+)+b:  443.6 ns/op   ← 25x faster than Go's 11,292 ns

Recently, r/golang had a thread that blew up over this dataset. The comments section got pretty heated, with some people saying to switch to a third-party library, some saying to use `strings.contains`, and even some people saying outright: "Is the Go team bad at writing regular expressions?"

But that benchmark only tells half the story. The input matches (there’s a b at the end), so Python's backtracking engine finds one path and stops. Before you refactor everything, you need to understand why Go is slower, because the reason changes the decision entirely.

Benchmark source code: regexp_test.go | redos.go | redos_python.py

Two Philosophies of Regex

Every regex engine makes a fundamental choice between two algorithms.

Thompson NFA (what Go uses)

Ken Thompson described this in his 1968 paper. The idea: simulate all possible NFA states in parallel. At each character, advance every active state simultaneously.

Time complexity: O(m x n), where m is the pattern length and n is the input length. Always. No exceptions.

Backtracking (what PCRE, Python, Perl, Java, Ruby use)

Try the first option. If it fails, backtrack and try the next. Repeat until you find a match or exhaust all possibilities.

Time complexity: O(n) in the happy path. O(2^n) in the worst case.

That worst case is not hypothetical. It has a name: ReDoS, Regular Expression Denial of Service.

The ReDoS Bomb

Take the pattern (a+)+. Seems innocent. Now match it against "aaaaaaaaab" (9 a's followed by b).

I measured this. Same pattern (a+)+, input is pure as with no b, which forces full backtracking:

ReDoS: Go (linear) vs Python (exponential)

Pattern: (a+)+b   Input: "aaa...a" (no match, maximum backtracking) 
  
              Go (µs)    Python (µs)       Ratio 
n=10            1.9           96            50x 
n=20            2.3       67,698        29,000x 
n=25            2.9    2,169,774       750,000x 
n=29            3.0   35,110,024    11,700,000x

Read that last row again.

Go: 3 microseconds. Python: 35 seconds. On a 29-character string.

That’s an 11.7-million-x difference. Python’s growth factor is ~2x per character, textbook O(2^n). Go stays flat regardless of input length:

// Go ReDoS immunity — same pattern (a+)+b, non-matching input 
n=10     222.8 ns/op 
n=20     332.3 ns/op 
n=29     446.7 ns/op    ← linear growth, not exponential

// TestReDoSImmunity — must always pass in under 100ms 
func TestReDoSImmunity(t *testing.T) { 
    re := regexp.MustCompile(`(a+)+b`) 
    for _, n := range []int{10, 20, 25, 29} { 
        start := time.Now() 
        re.MatchString(strings.Repeat("a", n)) 
        if d := time.Since(start); d > 100*time.Millisecond { 
            t.Errorf("took too long: n=%d, duration=%v", n, d) 
        } 
    } 
} 
// PASS — all complete in microseconds

This is not a contrived example. In 2019, Cloudflare had a production outage caused by exactly this class of pattern. A single malformed WAF rule was triggered by a pathological input. CPU spiked to nearly 100% globally. They lost 80% of their traffic. The outage lasted 27 minutes.

“A leader in our Solutions Engineering group told me we had lost 80% of our traffic.” — Cloudflare Post-Mortem, July 2, 2019

Now go back to that earlier benchmark where Python’s complex regexp was faster than Go’s.

That benchmark used an input that matched, 1000 a’s followed by b. The backtracking engine found the match and stopped. In the happy path, backtracking wins.

But the happy path is also the attacker’s attack surface. Your regex engine doesn’t get to choose which inputs it receives.

Go’s regexp package is immune to this class of attack. Completely. By design.

The 11,292 ns you pay on a matched 1000-char input buys you the ~450 ns guarantee on a non-matching 29-char input, while Python takes 35 seconds on the same string.

How Go’s Regexp Actually Works

Most Go developers don’t realize this: Go’s regexp package has three internal engines, not one.

From src/regexp/exec.go:

// onepass: fast path, single linear scan. 
// Used when the regex can be rewritten as a one-pass NFA — 
// no ambiguity, no need to explore multiple states. 
func (re *Regexp) doOnePass(ir io.RuneReader, i input, pos, ncap int) []int 
  
// backtrack: medium path, bounded backtracking. 
// Used for small inputs where the backtrack depth is provably limited. 
func (re *Regexp) backtrack(i input, pos int, end int, ncap int) []int 
  
// The generic NFA: full Thompson simulation. 
// Always correct, always O(mn), always "slow". 
func (m *machine) match(i input, pos int) bool

When you call regexp.Compile, Go analyzes the pattern and picks the engine at match time:

onepass handles simple patterns with no ambiguity, as fast as a hand-written scanner. backtrack kicks in for more complex patterns on small inputs where the depth bound holds. NFA (full) covers everything else, linear time, guaranteed.

I benchmarked a+b (onepass-eligible) against (a+)+b (full NFA) on a 100-char input: 1,212 ns vs 1,228 ns. Nearly identical. Honestly a bit anticlimactic. But that's the whole point of the design. The onepass engine isn't really a speed optimization. It's a safety architecture. Even the slowest path (full NFA) stays linear. The selection happens at compile time, and the fallback is always safe. regexp.MustCompile(\d+) and regexp.MustCompile((a+)+) both carry the same linear-time guarantee.

Why Go Made This Choice

This design traces to Russ Cox.

In 2007, before Go existed, Cox wrote a series of blog posts that laid out the argument:

“Many of the regular expression implementations used today — in Perl, Python, PCRE — can be made to run in exponential time on simple patterns. […] The Thompson NFA guarantees linear time. It was published in 1968. Its performance has been forgotten.” — Russ Cox, Regular Expression Matching Can Be Simple And Fast, 2007

Cox later built RE2, a library that takes the Thompson NFA further with lazy DFA construction. RE2 is dramatically faster than Go’s standard library while preserving the linear-time guarantee. It’s also the basis for Google’s production regex infrastructure.

When Go’s regexp package was designed, the decision was explicit: correctness and safety over raw throughput. The package handles arbitrary user-supplied patterns without risk. You can expose it to untrusted input. The guarantee holds.

Most web frameworks, WAFs, and API gateways accept user-defined patterns. If they use a backtracking engine, they’re one crafted string away from a DoS.

When You Actually Need Speed

If you’ve profiled your application and regexp is a real bottleneck (not a theoretical one), here are your options in order of invasiveness.

How big are the gaps in practice? These numbers are from an Apple M4:

// Apple M4, darwin/arm64, go test -bench=. -benchmem -benchtime=3s 
BenchmarkEmailRegexp              312.40 ns/op    0 B/op    0 allocs/op 
BenchmarkEmailStrings               7.37 ns/op    0 B/op    0 allocs/op   ← 42x faster 
  
BenchmarkRegexpReplace            460.10 ns/op   96 B/op    5 allocs/op 
BenchmarkStringsFieldsJoin         75.71 ns/op   88 B/op    2 allocs/op   ← 6x faster 
  
BenchmarkCompileEachTime         1171.00 ns/op 1717 B/op   19 allocs/op 
BenchmarkCompileOnce              808.10 ns/op    0 B/op    0 allocs/op   ← plus 19 fewer allocs

Option 1: Don’t use regexp

// Before 
matched, _ := regexp.MatchString(`^https://`, url) 
  
// After — 42x faster for email-style patterns, zero allocation 
matched := strings.HasPrefix(url, "https://")

Email validation with regexp: 312 ns/op. Hand-written string check: 7.4 ns/op. For fixed strings, prefixes, suffixes, or contains checks, strings and bytes are always faster. This is the right answer most of the time.

Option 2: Compile once, reuse

// ❌ Compiles on every call — 1171 ns, 1717 B, 19 allocs per call 
func IsValid(s string) bool { 
    matched, _ := regexp.MatchString(`^\d{4}-\d{2}-\d{2}$`, s) 
    return matched 
} 
  
// ✅ Compile once at package level — 808 ns, 0 B, 0 allocs 
var datePattern = regexp.MustCompile(`^\d{4}-\d{2}-\d{2}$`) 
  
func IsValid(s string) bool { 
    return datePattern.MatchString(s) 
}

Every call that re-compiles a pattern does ~19 heap allocations for nothing. Fixing this alone resolves most “regexp is slow” complaints.

Option 3: Use go-re2 for high-throughput paths

import re2 "github.com/wasilibs/go-re2" // drop-in replacement, RE2 via WASM

go-re2 wraps the RE2 C++ library via WebAssembly. Community benchmarks show 5-10x improvement on complex patterns, still with linear-time guarantees. Profile your specific workload before switching.

Option 4: Reconsider the pattern itself

Sometimes the pattern is the problem. (a+)+ is pathological not because of the engine, but because it's ambiguous: many NFA paths lead to the same result. Rewriting it as a+b eliminates the ambiguity entirely, and Go's onepass engine handles it in a single scan.

Decision Matrix

Is the pattern a fixed string? 
    → strings.Contains / strings.HasPrefix / bytes.Index 
  
Is the pattern user-supplied (from an API, config, or user input)? 
    → Standard library, always. Never expose PCRE to untrusted input. 
  
Is regexp a measured bottleneck (profiler says so)? 
    → go-re2 as a drop-in replacement 
  
Do you need PCRE features (backreferences, lookahead)? 
    → regexp2 — but understand the ReDoS risk 
  
Everything else? 
    → Standard library. Compile once. Move on.

What to Take Away

Go’s regexp is slower in the average case. That’s the trade-off, and it’s deliberate. What you get is a guarantee that no input, no matter how crafted, can blow up your match time. Cloudflare learned what happens without that guarantee.

For most code, the performance gap doesn’t matter. Compile once, reuse, done. When it does matter: strings for fixed patterns, go-re2 for complex high-throughput paths, standard library whenever you're handling untrusted input.

I used to think 11 µs per match was a performance problem. After watching what happens to backtracking engines on adversarial input, I think it’s a bargain.