Benchmark Regexp Against Manual Parsing in Go Code

Regular expressions are the first tool people reach for to pull fields out of text, and in Go they are also one of the most common entries at the top of a CPU profile for log processors, scrapers and request routers. The question is not whether regexp is slow, because 1.2 µs for a seven field log line is fine for a thousand lines and expensive for ten million. The question is what you give up and gain by writing the parser by hand. This article takes one real format, an access log line, parses it three ways, and measures each, then measures the traps (compiling in a loop, using a regexp for a prefix test) and states when a regexp is still the right answer.

For the reasons behind the cost see why regular expressions in Go are safe but often slow. Related searching techniques are in fast string search, and the benchmarking method in benchmarking a Go function properly. The cornerstone is the Go performance guide.

The task

A line in common log format:

203.0.113.7 - - [10/Oct/2000:13:55:36 -0700] "GET /library/go-sort-benchmark?ref=feed HTTP/1.1" 200 18342

Extract the method, the request path, the status code and the byte count. Three implementations, and a check at the start of the program that all three return the same entry:

1. regexp, a compiled pattern with four capture groups and FindStringSubmatch.
2. strings functions: find the quoted request with IndexByte, split the pieces with Fields, convert with Atoi.
3. A hand written scan that walks the line with IndexByte and slices, with no splitting and no intermediate slices.

package main

import (
	"flag"
	"fmt"
	"regexp"
	"sort"
	"strconv"
	"strings"
	"testing"
)

func init() {
	testing.Init()
	flag.Set("test.benchtime", "150ms")
}

type entry struct {
	Method string
	Path   string
	Status int
	Bytes  int
}

const line = "203.0.113.7 - - [10/Oct/2000:13:55:36 -0700] \"GET /library/go-sort-benchmark?ref=feed HTTP/1.1\" 200 18342"

var re = regexp.MustCompile(`^\S+ \S+ \S+ \[[^\]]+\] "(\w+) (\S+) [^"]*" (\d{3}) (\d+)$`)

func byRegexp(s string) (entry, bool) {
	m := re.FindStringSubmatch(s)
	if m == nil {
		return entry{}, false
	}
	st, _ := strconv.Atoi(m[3])
	by, _ := strconv.Atoi(m[4])
	return entry{m[1], m[2], st, by}, true
}

func byStrings(s string) (entry, bool) {
	i := strings.IndexByte(s, '"')
	if i < 0 {
		return entry{}, false
	}
	j := strings.IndexByte(s[i+1:], '"')
	if j < 0 {
		return entry{}, false
	}
	req := s[i+1 : i+1+j]
	rest := strings.Fields(s[i+j+2:])
	if len(rest) != 2 {
		return entry{}, false
	}
	parts := strings.Fields(req)
	if len(parts) < 2 {
		return entry{}, false
	}
	st, err := strconv.Atoi(rest[0])
	if err != nil {
		return entry{}, false
	}
	by, err := strconv.Atoi(rest[1])
	if err != nil {
		return entry{}, false
	}
	return entry{parts[0], parts[1], st, by}, true
}

func byScan(s string) (entry, bool) {
	i := strings.IndexByte(s, '"')
	if i < 0 {
		return entry{}, false
	}
	j := strings.IndexByte(s[i+1:], '"')
	if j < 0 {
		return entry{}, false
	}
	req := s[i+1 : i+1+j]
	sp := strings.IndexByte(req, ' ')
	if sp < 0 {
		return entry{}, false
	}
	method := req[:sp]
	path := req[sp+1:]
	if k := strings.IndexByte(path, ' '); k >= 0 {
		path = path[:k]
	}
	tail := s[i+j+2:]
	if len(tail) < 2 || tail[0] != ' ' {
		return entry{}, false
	}
	tail = tail[1:]
	k := strings.IndexByte(tail, ' ')
	if k < 0 {
		return entry{}, false
	}
	st, err := strconv.Atoi(tail[:k])
	if err != nil {
		return entry{}, false
	}
	by, err := strconv.Atoi(tail[k+1:])
	if err != nil {
		return entry{}, false
	}
	return entry{method, path, st, by}, true
}

func median(f func(b *testing.B)) (float64, int64, int64) {
	const runs = 5
	xs := make([]float64, 0, runs)
	var r testing.BenchmarkResult
	for i := 0; i < runs; i++ {
		r = testing.Benchmark(f)
		xs = append(xs, float64(r.T.Nanoseconds())/float64(r.N))
	}
	sort.Float64s(xs)
	return xs[runs/2], r.AllocedBytesPerOp(), r.AllocsPerOp()
}

var sink entry
var sinkOK bool
var sinkRE *regexp.Regexp
var sinkB bool

func main() {
	a, _ := byRegexp(line)
	b, _ := byStrings(line)
	c, _ := byScan(line)
	fmt.Printf("same result from all three: %v\n  %+v\n\n", a == b && b == c, a)

	fmt.Println("parse one access log line into method, path, status, bytes")
	for _, x := range []struct {
		name string
		f    func(string) (entry, bool)
	}{{"regexp.FindStringSubmatch", byRegexp}, {"strings.Fields and Index", byStrings}, {"hand written scan", byScan}} {
		ns, by, al := median(func(tb *testing.B) {
			tb.ReportAllocs()
			for tb.Loop() {
				sink, sinkOK = x.f(line)
			}
		})
		fmt.Printf("  %-28s %8.0f ns %6d B/op %3d allocs\n", x.name, ns, by, al)
	}

	fmt.Println()
	fmt.Println("the same regexp, but compiled inside the loop")
	ns, by, al := median(func(tb *testing.B) {
		tb.ReportAllocs()
		for tb.Loop() {
			r := regexp.MustCompile(`^\S+ \S+ \S+ \[[^\]]+\] "(\w+) (\S+) [^"]*" (\d{3}) (\d+)$`)
			sinkB = r.MatchString(line)
		}
	})
	fmt.Printf("  %-28s %8.0f ns %6d B/op %3d allocs\n", "MustCompile then match", ns, by, al)

	fmt.Println()
	fmt.Println("yes or no questions, no capture")
	id := "7f3a9c2e-5b41-4d8e-9a06-1c2b3d4e5f60"
	uuidRE := regexp.MustCompile(`^[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}$`)
	isUUID := func(s string) bool {
		if len(s) != 36 {
			return false
		}
		for i := 0; i < 36; i++ {
			c := s[i]
			switch i {
			case 8, 13, 18, 23:
				if c != '-' {
					return false
				}
			default:
				if !(c >= '0' && c <= '9' || c >= 'a' && c <= 'f') {
					return false
				}
			}
		}
		return true
	}
	for _, x := range []struct {
		name string
		f    func(string) bool
	}{{"regexp MatchString (UUID)", uuidRE.MatchString}, {"loop over bytes (UUID)", isUUID},
		{"strings.HasPrefix", func(s string) bool { return strings.HasPrefix(s, "7f3a") }},
		{"regexp ^7f3a", regexp.MustCompile(`^7f3a`).MatchString}} {
		ns, by, al := median(func(tb *testing.B) {
			tb.ReportAllocs()
			for tb.Loop() {
				sinkB = x.f(id)
			}
		})
		fmt.Printf("  %-28s %8.0f ns %6d B/op %3d allocs\n", x.name, ns, by, al)
	}
}

same result from all three: true
  {Method:GET Path:/library/go-sort-benchmark?ref=feed Status:200 Bytes:18342}

parse one access log line into method, path, status, bytes
  regexp.FindStringSubmatch        1246 ns    160 B/op   2 allocs
  strings.Fields and Index          125 ns     80 B/op   2 allocs
  hand written scan                  37 ns      0 B/op   0 allocs

the same regexp, but compiled inside the loop
  MustCompile then match           8639 ns  18904 B/op 194 allocs

yes or no questions, no capture
  regexp MatchString (UUID)         235 ns      0 B/op   0 allocs
  loop over bytes (UUID)             46 ns      0 B/op   0 allocs
  strings.HasPrefix                   2 ns      0 B/op   0 allocs
  regexp ^7f3a                       30 ns      0 B/op   0 allocs

Results

The hand written scan was 34 times faster than the regexp and the strings version 10 times faster. A 1.2 µs parse works out to about 800,000 lines per second on one core; the scan did 27 million. The allocation counts are small for all three. The regexp allocated 160 bytes for the capture slice and the returned []string, and the time went on the matching engine itself. Go's regexp guarantees time linear in the input by running a finite automaton (a backtracking engine would be faster on this pattern and exposed to catastrophic inputs), and that guarantee is paid for per byte on every call.

The strings version sits in the middle and is the one most people should write. It is readable, it uses only standard functions, and it was 10 times faster. The two allocations come from Fields building slices.

The hand written scan is only worth it on a hot path. It is about 40 lines, it encodes the format in control flow, and each assumption (one space after the closing quote, a numeric status) is a place for a bug. Write it when a profile shows parsing taking a large share of time, and write a test that feeds it every malformed line you can think of, with the regexp version as the oracle. The lab's first line, same result from all three: true, is that test in miniature.

Trap: compiling inside the loop

Compiling a pattern parses it, builds a program and allocates the structures the matcher needs. For this pattern that was 194 allocations and 18.9 KB, and 8,639 ns, seven times the cost of the match. Compile once, in a package level variable:

var lineRE = regexp.MustCompile(`^\S+ \S+ \S+ \[[^\]]+\] "(\w+) (\S+) [^"]*" (\d{3}) (\d+)$`)

A *regexp.Regexp is safe for concurrent use, so one variable serves every goroutine. The mistake usually hides in a helper function called per request (func isValid(s string) bool { return regexp.MustCompile(...).MatchString(s) }). The CPU profile shows it as regexp/syntax.Parse and regexp.compile near the top (CPU profiles). regexp.MatchString(pattern, s), the package level helper, compiles on every call, which is the same trap in one line.

Trap: a regexp for a question a string function answers

A prefix test with strings.HasPrefix took 2 ns; the same question asked with an anchored regexp took 30 ns, 15 times more. A byte loop for the UUID shape was 5 times faster than the regexp. The same holds for strings.Contains, strings.Index, strings.EqualFold, strings.Cut and strconv: if a standard function expresses the check, it will beat a regexp, and be easier to read.

When a regexp is the right tool

• The pattern is data. A user, a configuration file or a rule set supplies it, so there is nothing to hand write.
• The grammar has alternation, repetition and optional parts and you would be writing a state machine. Eight lines of regexp beat eighty lines of code that has to be tested as carefully.
• The rate is low. Validating a form field, parsing a command line argument, matching a route at startup. Microseconds do not matter.
• You need the safety guarantee on untrusted patterns or inputs. Go's engine cannot be driven into exponential time, which is the property most other languages' engines lack.
• You are prototyping. Start with the regexp, prove the behaviour, then replace it behind the same function signature if the profile says so.

Replace one when: it shows in a profile at several percent of CPU, it runs per line or per request at high volume, and the format is fixed and simple.

Making a regexp cheaper without replacing it

1. Compile once, at package level.
2. Use MatchString when you do not need captures, FindStringSubmatchIndex when you can slice the original string yourself, and avoid FindAllString on huge inputs.
3. Anchor the pattern (^, $) so the engine does not try every start position.
4. Put a literal prefix in the pattern; the engine uses it to skip ahead.
5. Avoid .* at the start, and avoid capture groups you do not use (use (?:...)).
6. Pre filter with a strings.Contains for a rare literal before running the regexp on every line.

Checklist

• Compile at package level; never in a function that runs per request.
• Use strings and strconv where they say what you mean; they were 10 times faster here.
• Hand write the parser only when a profile justifies it, and test it against the regexp.
• A regexp for a prefix or a substring is 15 times slower than the function made for it.
• Keep regexp for variable patterns, complex grammars and low rates.

The syntax and guarantees are described in the regexp package documentation and the RE2 syntax reference.