Is there any regular expression engine which do Just-In-Time compiling?

Question

My Questions is

Is there any regular expression engine which do Just-In-Time compiling during regex pattern parsing and use when matching/replacing the texts? or where can I learn JIT for i386 or x64 architecture?

Why I need that is,

I recently trying to benchmark python's built-in regex engine with normal C codes with around 10M data.

I found that for normal replace (for example ab to zzz) is relatively fast like just 2 to 3 times different to C

but for [a-z]c tooks around 5 to 8 times slower than C,

and with grouping (for example - ([a-z])(c) to AA\2\1BB ) its tooks 20 to 40 times slower than C.

Its not Just-In-Time compiling yet, but I think If I could do just In time compling, It could faster a lot more.

ps: I use profiling for each regex patterns during compling patterns, for eg, profile 1 for simple one like ab, profile 2 for range [a-z]c, profile 3 with grouping ([a-z])(c), each profile has seperate codes, so no extra cost needed when matching, and replacing simple patterns.

Any Ideas would be appreciated, Thanks in advance.

Update 1:

I have tried with psyco, and Its doesnot improve the speed that much. May be because I am doing text replacing against big data, not looping many times. If I am not wrong, Python's re.sub running it in natively already I think, so pysco cannot improve the speed that much.

Update 2:

I have tried with boost regex wrapped into python, but its even slower than python's regex, so It seems like the bottleneck is in python's string processing and Jan Goyvaerts also pointing me that point in the answer.

Update

I like to convert regex pattern ab[a-z]c to machine codes, like following equivlent C codes.

*s points to 10M Long Texts

do{
    if(*s=='a' && s[1]=='b' && s[2]>='a' && s[2]<='z' && s[3]=='c') return 1;
}while(*s++);
return 0;

any ideas?

Answer 1

I'm no Python expert, but you could give Psycho a try:

http://www.ibm.com/developerworks/library/l-psyco.html

http://psyco.sourceforge.net/

Answer 2

So if I understand you correctly, you use a programming language that by default does not do just-in-time compiling and now you are looking for a regex library that does precisely that?

I think you should compile all of your python code to binary using e.g. Psyco

http://www.devshed.com/c/a/Python/How-Python-Runs-Programs/4/

also discussed here:

http://stackoverflow.com/questions/138521/is-it-feasible-to-compile-python-to-machine-code

and here:

http://stackoverflow.com/questions/205062/is-it-possible-to-compile-python-natively-beyond-pyc-byte-code

If these solutions either don't work or are still not fast enough and if you absolutely want to write the rest of your application in python, there is the boost python c++ library:

http://www.boost.org/doc/libs/1_41_0/libs/python/doc/index.html

The boost.python library allows full interoperability between python and c++. Then, you could use the boost.regex c++ regex matcher:

http://www.boost.org/doc/libs/1_41_0/libs/regex/doc/html/index.html

Answer 3

The regular expression engine in Firefox compiles some (not all!) regular expressions to machine code. I believe Safari and Chrome do too.

Answer 4

I don't see it in your question, so I ask: Did you test with precompiled regular expressions e.g. "re.compile(pattern)" ??

Since compiled regexes should be faster. OK, it is not JIT, but most of the time you are fine with simply precompiled ones!

See here:

re.compile

Answer 5

Another idea: When you have a library (in C) that is more optimal than the Python regex module or that does just-in-time compilation of Regexes, then you could write your own regex module for python that does just wrap your C-Library.

That of course is somewhat more work and only recommended when you really, really need the speed.

You could also try Cython (personally I did not use it yet, but it sounds rather good) to do the job of wrapping.

As much as I understand your problem now, the Python surrounding is not your problem (so I doubt whether psyco will help) -- also the preparation of the regex-run is not your problem, but the run itself must be top-speed. That of course depends on the library you use and how good it can handle large strings. I would think, that the standard python regex-lib is not optimized for such long strings and top-of-the-notch speed.

Answer 6

I may be wrong, but I believe that Python's regex module is in C, so any suggestion to compile Python (like using Psycho) would not make much difference---what you're actually comparing is the performance of one C regex library (Python's) with another (whatever library you are using).

Answer 7

The only regex engine that I know that can compile regular expressions into executable code is the one in .NET when you pass RegexOptions.Compiled. That causes the Regex class to emit MSIL which can then be JITted like any other .NET code.

Whether than makes the .NET regex engine faster than others is a totally different matter. When searching and replacing using relatively simple regular expressions on large data sets, string handling becomes far more important. .NET strings are immutable, so much will depend on how many times the string needs to be reallocated.

Hand-coding the operation will always be faster, because the code isn't equivalent. The regex code maintains certain information about the regex match and the capturing groups which your code does not. In most situations, the extra time you spend hand-coding the search-and-replace instead of using a regex isn't worth the effort, particularly if you factor in that switching to a different regex is trivial when your requirements change, while rewriting the search-and-replace using procedural code takes much more time.

In my experience, PCRE is one of the fastest regex engines around. It doesn't include a ready-made search-and-replace, however.

Answer 8

Thompson had a paper published in the communications of the ACM in 1968 that described a working JIT compiler for regular expressions into IBM 7094 code. I don't know what language(s) he used; Fortran or LISP would be the obvious suspects, with LISP being especially suspect since it already had JIT compiling.