← All workEntry 5 of 6
  • C#
  • .NET 8
  • BenchmarkDotNet

grep-sharp

grep, rebuilt from the parser up, to understand what a regex engine actually does.

§1

The question

Regex engines trade speed for flexibility. How do you compile a pattern into something fast, and when is the simple approach the faster one?

§2

How it works

  1. Patternshunting-yard → RPN
  2. NFAThompson construction
  3. DFAbuilt lazily, cached
  4. Matchesor literal fast path
Fig. 1  Patterns are parsed to postfix, compiled to an NFA, and turned into DFA states on demand. Plain-text patterns skip all of it.

A heuristic looks at each pattern and chooses a literal fast path, NFA simulation, or the cached DFA. DFA states are only built when the input actually reaches them, so memory stays small.

§3

Results

2–3 msto search 1 MB of text with the literal fast path

SearchTime
1 MB, plain text, fast path2–3 ms
1 MB, plain text, NFA8–9 ms
10 MB, automatic strategy80–100 ms
Character classes (was 63 ms)12–15 ms

← from my own benchmark runs

§4

What I learned

  • Automata theory pays off in very practical ways
  • Measure before optimising: BenchmarkDotNet showed where the time went