logo

4x speed-up by switching from regex to Nom for parsing

102 points mtkennerly
View on Reddit ↗

This is just anecdotal, and I'm sure there are a lot of factors that make it an unfair comparison, but I thought it was interesting anyway and wanted to share my experience.

I recently switched Regashii (a Windows .reg file parser/writer) from regex to Nom. I'm one of those twisted people who think that regex is nice and intuitive to work with, but I wasn't happy with the performance, and I confirmed from cargo-flamegraph that regex was where it spent most of its time, so I tried Nom on a whim to see how much of a difference it would make. I've used Haskell's Parsec before, but otherwise hadn't done much with parser combinators. I chose Nom simply because it seemed to be the most popular and I found its API pretty straightforward.

For context, the regex parsing was structured like this: (A) First perform an initial regex find/replace to remove comments and concatenate split lines, and then (B) iterate over each line separately and run them through a series of regexes to extract values (short-circuiting on the first match).

These are the improvements I found, parsing a 520 MB export of the full registry and compiling in release mode:

  • As a baseline, with the regex approach: 20 seconds
  • After converting step B to Nom (but keeping the line-by-line approach): 8 seconds
  • After converting both steps A and B to Nom: 6 seconds

When I initially searched on Google for regex vs Nom performance, I found a quote (from 2018, so I suppose it's outdated now) that said "sometimes, nom can be almost as fast as regex", so I was surprised to get a 4x speed-up. Probably varies case by case, but certainly worth it for me.

For anyone who wants to see the code, I migrated in this commit and then this commit. I think it went pretty smoothly. The main hiccup I had was when I stopped splitting the text by line up front, which meant that any of my Nom-based parser functions could accidentally read too far, so I had to be more careful about explicitly reading until the next line break or line continuation.