6 ms·

PIRE – really fast single-pass regex matching

34 points by alexkon 16y ago

alexkon 16y ago
Here are the results of some sample benchmarks. These are the same as those used in the paper "Regular Expression Matching in the Wild" by Russ Cox [1]. 500 MB file, regex: .*$ pcre 31.67 MB/s re2 242.28 MB/s pire 756.32 MB/s 500 MB file, regex: ABCDEFGHIJKLMNOPQRSTUVWXYZ$ pcre 153.67 MB/s re2 653.76 MB/s pire 755.98 MB/s 2 MB file, regex: (\d{3}-|$\d{3}$\s+)(\d{3}-\d{4})$ re2 423,76 MB/s pire 775,89 MB/s Source: Yandex, the company where PIRE originated. [2] (Russian) [1] http://swtch.com/~rsc/regexp/regexp3.html http://swtch.com/~rsc/regexp/regexp3.html [2] http://clubs.ya.ru/company/replies.xml?item_no=30753 http://clubs.ya.ru/company/replies.xml?item_no=30753
- xentronium 16y ago
  There're two more interesting things mentioned in the article which originated in yandex: https://github.com/highpower/xiva https://github.com/highpower/xiva -- asynchronous web-server for server-side part of html5 websockets https://github.com/khanton/NwSMTP https://github.com/khanton/NwSMTP -- they say it's a "nginx for SMTP", a proxy server they use for providing ssl, rbl, antispam and antivirus checks.
jdludlow 16y ago
"Pire does not have any Perlish conditional regexps, lookaheads & backtrackings, greedy/nongreedy matches; neither has it any capturing facilities." Well that rules out nearly every use case I have for needing a regex in the first place.
- bartl 16y ago
  Probably the only use case I can think of, is for "does it match?" tests. Spam detection, like SpamAssassin, might benefit from it.
  - nowarninglabel 16y ago
    If that is the case, wouldn't we just use more specialized functions, I forget the boost_regex function for C++, but for PHP we can do strpos() instead strstr() to see simply if a string exists? In that case, I'm guessing the benchmarks would be closer.
    - xentronium 16y ago
      Substring location won't tell you if your string is an email, for example.
      - nowarninglabel 16y ago
        Yes, good point.
      - jonhohle 16y ago
        Neither will a regex [1] [1] http://www.regular-expressions.info/email.html http://www.regular-expressions.info/email.html
        iloveponies 16y ago
        That totally depends on the regex: http://www.ex-parrot.com/pdw/Mail-RFC822-Address.html http://www.ex-parrot.com/pdw/Mail-RFC822-Address.html
        jonhohle 16y ago
        From the page you linked: > This regular expression will only validate addresses that have had any comments stripped and replaced with whitespace (this is done by the module). There is filtering done before the regex is applied.
- Groxx 16y ago
  Greedy / non-greedy is one of the main things I use in regexes (well, second to capturing). That sucks. Though if it's non-capturing, I guess it makes sense. How many people do use regexes for boolean operations? I can only think of an instance or two where I have, aside from regular input validation.
  - jemfinch 16y ago
    Most uses of non-greedy matching can be replaced with faster, clearer, and more precise inverted character classes, in my experience.
- amalcon 16y ago
  I was actually building something very similar to this, though I stopped about six months ago due to time constraints. The goal was to be able to check which of a set of regular expressions matches a given string, and then invoke PCRE or similar to get the subexpression capture. The end result: Django-style regex URL routing against an arbitrary number of expressions, in the same amount of time as routing against a single expression. Of course, I generally never use any of those features except the capture. (And greedy/nongreedy matching, but that is irrelevant if you're not doing a subexpression capture)
- sophacles 16y ago
  When dealing with very very large datasets, the ability to filter fast is important. So it becomes a 2-stage (actually n-stage...) problem: filter the raw data, and remove the parts that are known irrelevant (alternately include only the 'maybes'), then do the more intensive processing on the smaller resultant data-set. When done in parallel it looks a lot like map-reduce :)
thibaut_barrere 16y ago
The joys of naming: "pire" in french means "worst".
- robrenaud 16y ago
  Maybe it is an appropriate term here? Pire throws out the advanced/complex features of Perl compatible regular expressions, so the authors are arguably following the "Worse is Better"[1] paradigm. *Simplicity The design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design. [1] http://en.wikipedia.org/wiki/Worse_is_better http://en.wikipedia.org/wiki/Worse_is_better
talklittle 16y ago
Cool. A very similar (concept-wise, not yet sure about implementation-wise) DFA/NFA library in Java, developed by Anders Møller at Aarhus University: http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ I use this on Android and it performs substantially faster than java.util.regex, of course working within the constraints of DFA/NFA as opposed to the "Perlish" regular expressions. Edit: And dk.brics.automaton has its own C reimplementation. I wonder how the speed and functionality compare to PIRE? http://augeas.net/libfa/ http://augeas.net/libfa/

34 points by alexkon 16y ago

Here are the results of some sample benchmarks. These are the same as those used in the paper "Regular Expression Matching in the Wild" by Russ Cox [1]. 500 MB file, regex: .*$ pcre 31.67 MB/s re2 242.28 MB/s pire 756.32 MB/s 500 MB file, regex: ABCDEFGHIJKLMNOPQRSTUVWXYZ$ pcre 153.67 MB/s re2 653.76 MB/s pire 755.98 MB/s 2 MB file, regex: (\d{3}-|$\d{3}$\s+)(\d{3}-\d{4})$ re2 423,76 MB/s pire 775,89 MB/s Source: Yandex, the company where PIRE originated. [2] (Russian) [1] http://swtch.com/~rsc/regexp/regexp3.html http://swtch.com/~rsc/regexp/regexp3.html [2] http://clubs.ya.ru/company/replies.xml?item_no=30753 http://clubs.ya.ru/company/replies.xml?item_no=30753

xentronium 16y ago
There're two more interesting things mentioned in the article which originated in yandex: https://github.com/highpower/xiva https://github.com/highpower/xiva -- asynchronous web-server for server-side part of html5 websockets https://github.com/khanton/NwSMTP https://github.com/khanton/NwSMTP -- they say it's a "nginx for SMTP", a proxy server they use for providing ssl, rbl, antispam and antivirus checks.

jdludlow 16y ago

"Pire does not have any Perlish conditional regexps, lookaheads & backtrackings, greedy/nongreedy matches; neither has it any capturing facilities." Well that rules out nearly every use case I have for needing a regex in the first place.

bartl 16y ago
Probably the only use case I can think of, is for "does it match?" tests. Spam detection, like SpamAssassin, might benefit from it.
- nowarninglabel 16y ago
  If that is the case, wouldn't we just use more specialized functions, I forget the boost_regex function for C++, but for PHP we can do strpos() instead strstr() to see simply if a string exists? In that case, I'm guessing the benchmarks would be closer.
  - xentronium 16y ago
    Substring location won't tell you if your string is an email, for example.
    - nowarninglabel 16y ago
      Yes, good point.
    - jonhohle 16y ago
      Neither will a regex [1] [1] http://www.regular-expressions.info/email.html http://www.regular-expressions.info/email.html
      - iloveponies 16y ago
        That totally depends on the regex: http://www.ex-parrot.com/pdw/Mail-RFC822-Address.html http://www.ex-parrot.com/pdw/Mail-RFC822-Address.html
        jonhohle 16y ago
        From the page you linked: > This regular expression will only validate addresses that have had any comments stripped and replaced with whitespace (this is done by the module). There is filtering done before the regex is applied.
Groxx 16y ago
Greedy / non-greedy is one of the main things I use in regexes (well, second to capturing). That sucks. Though if it's non-capturing, I guess it makes sense. How many people do use regexes for boolean operations? I can only think of an instance or two where I have, aside from regular input validation.
- jemfinch 16y ago
  Most uses of non-greedy matching can be replaced with faster, clearer, and more precise inverted character classes, in my experience.
amalcon 16y ago
I was actually building something very similar to this, though I stopped about six months ago due to time constraints. The goal was to be able to check which of a set of regular expressions matches a given string, and then invoke PCRE or similar to get the subexpression capture. The end result: Django-style regex URL routing against an arbitrary number of expressions, in the same amount of time as routing against a single expression. Of course, I generally never use any of those features except the capture. (And greedy/nongreedy matching, but that is irrelevant if you're not doing a subexpression capture)
sophacles 16y ago
When dealing with very very large datasets, the ability to filter fast is important. So it becomes a 2-stage (actually n-stage...) problem: filter the raw data, and remove the parts that are known irrelevant (alternately include only the 'maybes'), then do the more intensive processing on the smaller resultant data-set. When done in parallel it looks a lot like map-reduce :)

thibaut_barrere 16y ago

The joys of naming: "pire" in french means "worst".

robrenaud 16y ago
Maybe it is an appropriate term here? Pire throws out the advanced/complex features of Perl compatible regular expressions, so the authors are arguably following the "Worse is Better"[1] paradigm. *Simplicity The design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design. [1] http://en.wikipedia.org/wiki/Worse_is_better http://en.wikipedia.org/wiki/Worse_is_better

talklittle 16y ago

Cool. A very similar (concept-wise, not yet sure about implementation-wise) DFA/NFA library in Java, developed by Anders Møller at Aarhus University: http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ I use this on Android and it performs substantially faster than java.util.regex, of course working within the constraints of DFA/NFA as opposed to the "Perlish" regular expressions. Edit: And dk.brics.automaton has its own C reimplementation. I wonder how the speed and functionality compare to PIRE? http://augeas.net/libfa/ http://augeas.net/libfa/