from Hacker News

Regular Expression Matching Can Be Simple and Fast (2007)

by prabhupant on 6/29/19, 3:32 AM with 33 comments

• by feniv on 6/29/19, 7:02 AM

  The author, Russ Cox, has a whole series of articles on the topic of regex - https://swtch.com/~rsc/regexp/

  The rust Regex crate docs even refer to his posts as a reference since the rust version is based on his efficient RE2 Regex implementation at Google.

• by dang on 6/29/19, 7:13 AM

  Threads from 2018: https://news.ycombinator.com/item?id=16341519

  2015: https://news.ycombinator.com/item?id=9374858

  2009: https://news.ycombinator.com/item?id=820201

  also 2009: https://news.ycombinator.com/item?id=466845

• by Quarrel on 6/29/19, 7:44 AM

  But if you want faster, (but more complicated):

  https://github.com/intel/hyperscan

• by DigitalTerminal on 6/29/19, 10:23 AM

  Also relevant is Google V8's Irregexp: https://blog.chromium.org/2009/02/irregexp-google-chromes-ne.... They claim 3x speedups.

• by pier25 on 6/29/19, 3:02 PM

  A bit off topic, but here are some Regex benchmarks that might be of interest:

  https://github.com/mariomka/regex-benchmark

  Surprisingly JS is about 10 times faster than Go.

• by yxhuvud on 6/29/19, 3:57 PM

  What I wonder is if the regexps could be preprocessed in a way so that the fast variant is used for all or at least most cases where it it possible to use it.

• by abainbridge on 6/29/19, 6:54 AM

  Is there any information about the performance when not looking for things like when a?a?a?aaa matches aaaaaa?

• by hyperpallium on 6/29/19, 7:57 AM

  Now you have an exponential space problem.