Step 1) Install pyre2 2) import re2 as re 3) 10x faster regex

by axiak • 16 years ago

97 27 16 years ago

natmaster• 16 years ago

What kind of licensing does this have?

It would be interesting to see if this could make it in Python 3.2 (It's supposed to include the Unladen Swallow stuff, so might as well take more awesomeness from Google.)

mcav• 16 years ago

The 3-clause BSD license...

http://github.com/axiak/pyre2/blob/master/LICENSE

axiak3• 16 years ago

BSD (as does the google RE2 C++ module)

dododo• 16 years ago

note it depends upon cython: i suppose it's more likely it will make it into cython rather than python 3.2.

axiak3• 16 years ago

Like the libxml module which uses Cython, the compiled CPP module is distributed along with it, so you don't actually need Cython to install it or compile it. But you would need Cython to do any development on it.

kingkilr2• 16 years ago

It won't. It doesn't implement the entire regular expression language Python supports.

kvs2• 16 years ago

Please note that RE2 doesn't support backtracking.

dkarl• 16 years ago

Could a regex library parse a regular expression and decide reasonably quickly which engine to use?

logic• 16 years ago

If you're not familiar with re2, you may be familiar with a couple of other little projects that the author, Russ Cox, is involved with: Go (http://golang.org/) and Plan 9 (http://swtch.com/plan9port/).

Also, here's a great bit of technical history behind Russ' re2 implementation, and why pyre2 will never be completely compatible with Python's re (without fallback):

http://swtch.com/~rsc/regexp/regexp1.html

http://swtch.com/~rsc/regexp/regexp2.html

http://swtch.com/~rsc/regexp/regexp3.html

pfedor• 16 years ago

Google Code Search was his intern project: http://googlecode.blogspot.com/2006/10/search-worlds-public-...

ww520• 16 years ago

I'm curious. How much of a speedup in regex when using DFA instead of NFA? I believe most regex implementation use NFA but there are well known algorithms to convert NFA to DFA. It should be worth the try.

ori_b4• 16 years ago

The problem is that in the worst case, converting an NFA to a DFA gives an overhead of 2^n, while keeping it as an NFA only incurs an overhead of m (where m is the regex length).

So, in the worst case (ie, under algorithmic complexity attacks), the NFA implementation is O(m * n), while the complexity of the DFA implementation is - I believe - O(2^m * n)

koenigdavidmj• 16 years ago

And fortunately, if re2 can not handle one of the regexen that you throw at it, then it will pass it down to Python's original re module (NFA_based). Perfectly seamless.

sandGorgon• 16 years ago

Could this be uploaded to pypi, so that it is available via pip ?

pip install pyre2 -E /tmp/testing

maxiak• 16 years ago

If you read the readme under installation, you'll find that it is.

pip install re2 -E /tmp/testing

democritus• 16 years ago

I tried using pyre2 and experienced runaway memory usage. I was using re.split. The behaviour went away when I switched to the standard re module. (without changing my code.)

Did anyone else experience this?

The code in question was:

(a, b) = re.split("\n\s*\n", text, maxsplit=1)

Thank you for any insights you may have regarding this.

Step 1) Install pyre2 2) import re2 as re 3) 10x faster regex

Related Stories