PCRE Performance Project

About

The aim of PCRE-sljit project is speeding up the pattern matching speed of Perl Compatible Regular Expressions library (ftp download). The task is achieved by using sljit, a just-in-time (JIT) compilation library to translate machine code from the internal byte-code representation generated by pcre_compile(). PCRE-sljit offers similar matching speed to DFA based engines (like re2) on common patterns but still keep PERL compatibility (see here).

This work has been released as part of PCRE 8.20 and above. The JIT was improved a lot in 8.32, and a new so called native interface was introduced. See the results.

About performance optimizations

Always do profiling! PCRE-JIT can only help you, if matching regular expressions takes at least 4-5% of the total runtime. Otherwise you might not see any performance increase (or you will see performance drops) due to the changes of the binary layout. It is unfortunately less known, that inserting nops can increase or decrease the runtime of any program by up to 3%, due the the CPU cache layout, branch prediction mechanisms, etc. In artificial cases, the runtime change can be even bigger (±50% for example). When any function is modified, even if the change is small, it affects the entire binary layout, since the entry offset of other functions will be changed as well (especially those, which are placed after this function in the executable by the linker). Therefore when the ratio of matching regular expressions is very low, you might experience a slight performance drop when using PCRE-JIT.

Usage

Because of compatibility reasons the JIT compilation must be explicitly requested by software. First of all PCRE must be compiled with --enable-jit. (Note: JIT compiler availability can be checked runtime by passing PCRE_CONFIG_JIT to pcre_config().) The next step is performing the JIT compilation by passing PCRE_STUDY_JIT_COMPILE, PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE or PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE to pcre_study(). Regardless of the success of JIT compilation, the returned extra data can be passed to pcre_exec(), which use the machine code when approprite, or fallback to the interpreted code path (Note: a few patterns are not supported by the JIT compiler). Passing PCRE_INFO_JIT to pcre_fullinfo() can be used to check whether the JIT compilation is successful. If the JIT compilation is succesful pcre[16|32]_jit_exec can be used to reach even better performance. It is also mandatory to use pcre_free_study() to free the machine code when the JIT compilation is succesful. Otherwise pcre_free_study() is optional for compatibility reasons, but we suggest to use it all the time.

Detailed info about the JIT compiler can be found in pcrejit.3, which is part of the PCRE documentation. It is advisable to read the "CONTROLLING THE JIT STACK" section there.

Motivation

The importance of pattern matching has been significantly grown in the last decade. The increased computation power allows running more complex regular expressions in an acceptable time frame. However, this is not the only way to speed up regular expressions. The developers of JavaScript engines realized that their just-in-time compilation engines are able to considerably improve the runtime of pattern matching. Thus, JIT based regular expression engines were developed like irregexp from Google and YARR (Yet Another Regex Runtime) from Apple. However, these engines are heavily tied to their JavaScript engine (V8 from Google and JavaScriptCore from Apple), and other software cannot benefit from this shiny new technology, until now. The aim of this work is to extend a widely used regular expression library (PCRE) with a JIT compiler engine, which can be easly adopted by any software already using PCRE.

How does it work?

First, a regular expression is compiled into an internal representation by pcre_compile(). The internal representation (usually called MIR - Middle Level Representation) is a sequence of byte-codes. Each byte-code is basically a command, which tells the next step for the interpreter inside pcre_exec(). The JIT compiler translates MIR to machine code when the appropriate flags are passed to pcre_study(). The returned pcre_extra data contains a pointer to a machine executable function if the machine code generation was successful.

Why is it faster?

JIT compilers totally eliminate the continual reparsing of MIR. Even if the MIR code is much simpler than the original pattern string, the execution engine is full of ifs and switches, and executing them consumes considerable time. The compiled machine code only contains those machine instructions whose are absolutely necessary for this particular pattern, and nothing more.

This advantage is also a limitation since JIT compiler does not support the changing of compile time flags. One such flag is the newline type (PCRE supports many of them). PCRE allows overwriting the compile time newline flags when pcre_exec() is called. This is not supported by the JIT compiler, and the regular expression will be fallbacks to the interpreter.

Compile time overhead

Deciding when to use or not use JIT compiling is an important question. Since JIT is a heavyweight optimization we should never forget about the compile time overhead. Thus, the total runtime can be bigger if we use the compiled expression only once on a small input.

The following values measured on an Intel 2.67GHz with GCC 4.4.5 in 64 bit mode
Note: ns means nanosecond (10-9), and Int. means interpreter (pcre_exec())

PatternCompile time
(ns)
JIT compile time
(ns)
JIT compile /
compile time
abc264793230.05
a+(b*)[c|d]??e+?9251718618.58
\A.*\K[^a-z!]{8,}\Z9251150112.43
\b((.)\w{3,}\2{0,3})$10572174720.57
(?P<cap>\p{N}+|(?(R)a|(?R)))\113223086923.35
^(?![a-zA-Z]*?[[:alpha:]]++)\P{L&}15202042513.44

Results

The following patterns are searched on a non-utf8 input and an utf8 input. The utf8 input was shorter so it was repeated 4 times (with a simple memcpy()).

The performace is measured on an Intel 2.67GHz with GCC 4.4.5 in both 32 and 64 bit mode. The unit of the runtime values are milliseconds (ms) which is 10-3 second. The PCRE library was compiled with -O3 and -static compiler options to get the best performance form the compiler.

Description of the colums
  • Pattern: the pattern string. The light blue lines are caseless, the light yellow lines are caseful matches.
  • Int. (ms): interpreter (normal pcre_exec(...)) runtime in milliseconds.
  • JIT (ms): JIT compiled machine code runtime in milliseconds.
  • Runtime ratio: Interpreter runtime / JIT runtime.
  • Runtime save %: Runtime saved by the JIT compiler. Equals to 1 - (JIT runtime / Interpreter runtime)

PatternInt.
(ms)
JIT
(ms)
Runtime
ratio
Runtime
save %
how to60401.5033.3%
^how to150207.5086.7%
how( to|ever)60302.0050.0%
walk|get|she|make240703.4370.8%
[Ww]alk|[Gg]et|[Ss]he|[Mm]ake250902.7864.0%
(?:ba|lu|ro)+(?:r|ck)*210703.0066.7%
(?:ba|lu|ro)+(r|ck)*210703.0066.7%
\w+our\w*16804104.1075.6%
(?:^\w+$)|\b(\W)\1+\b16303105.2681.0%
"[A-Z][a-z]*(?:(?:[,\s]|\R)(\s|\R)*[a-z]+){0,4}?[.!]"90402.2555.6%
\b(?:(?=\w+ro\w+)(?=\w+th\w+)\w+hr\w+)\b12003004.0075.0%
\b(?(?=\w+sh)\w+a|\w+uo)\w+\b18703705.0580.2%
\b\WX{0,3}(?:(?:V?I{1,3})|V|IV|IX)\W\b8201804.5678.0%
((\w)+?)\.\b(\s)*?\w43805408.1187.7%
(.{1,3})(\w*?\1)(?2)606015303.9674.8%
-?-?-?-?-?-?-?-?-?-?-?-----------$6001006.0083.3%
Average:12192604.1670.6%
Non-utf8 input on a 32 bit x86 machine.

PatternInt.
(ms)
JIT
(ms)
Runtime
ratio
Runtime
save %
how to60401.5033.3%
^how to180404.5077.8%
how( to|ever)60203.0066.7%
walk|get|she|make300803.7573.3%
[Ww]alk|[Gg]et|[Ss]he|[Mm]ake2801002.8064.3%
(?:ba|lu|ro)+(?:r|ck)*220802.7563.6%
(?:ba|lu|ro)+(r|ck)*240803.0066.7%
\w+our\w*20203605.6182.2%
(?:^\w+$)|\b(\W)\1+\b20603406.0683.5%
"[A-Z][a-z]*(?:(?:[,\s]|\R)(\s|\R)*[a-z]+){0,4}?[.!]"80402.0050.0%
\b(?:(?=\w+ro\w+)(?=\w+th\w+)\w+hr\w+)\b13403004.4777.6%
\b(?(?=\w+sh)\w+a|\w+uo)\w+\b20603605.7282.5%
\b\WX{0,3}(?:(?:V?I{1,3})|V|IV|IX)\W\b9401605.8883.0%
((\w)+?)\.\b(\s)*?\w566052010.8890.8%
(.{1,3})(\w*?\1)(?2)720016204.4477.5%
-?-?-?-?-?-?-?-?-?-?-?-----------$6801006.8085.3%
Average:14612654.5772.4%
Non-utf8 input on a 64 bit x86 machine.

PatternInt.
(ms)
JIT
(ms)
Runtime
ratio
Runtime
save %
die der10101.00 0.0%
ist|der|die|und100205.0080.0%
\b\w+\b2201401.5736.4%
(?:da|ge|om)+(?:n|me)*60203.0066.7%
\b(?(?=\w+ro)\w+pa|\w+lle)\w+\b5603001.8746.4%
\b(\W)\1+\b|(^(?=.*kl)(?=.*no).{15,40}$)6802003.4070.6%
^.{4,32}(\P{N})\1{2,}.{4,32}(?<![nuk])$240604.0075.0%
^(\w{3,})(?!\1).*\h.*\1$500021802.2956.4%
((\w{2,8},?(\P{Z}|\R)){1,2}\.\s?)$432013803.1368.1%
\b\w*?((.){1,3}\w*\2)\w*?(?1)17207002.4659.3%
\w*?(b{2,3})\w*?c11204002.8064.3%
\P{Lu}\P{L&}{0,12}[\s\-]{1,4}..[\P{L}\P{N}]{4}3001003.0066.7%
\b(\B([c-h])\B|[a-z]+?(?1)[a-z])9002803.2168.9%
Average:11724462.8358.4%
Utf8 input on a 32 bit x86 machine.

PatternInt.
(ms)
JIT
(ms)
Runtime
ratio
Runtime
save %
die der10101.00 0.0%
ist|der|die|und100303.3370.0%
\b\w+\b2201102.0050.0%
(?:da|ge|om)+(?:n|me)*80204.0075.0%
\b(?(?=\w+ro)\w+pa|\w+lle)\w+\b5402302.3557.4%
\b(\W)\1+\b|(^(?=.*kl)(?=.*no).{15,40}$)6401703.7673.4%
^.{4,32}(\P{N})\1{2,}.{4,32}(?<![nuk])$200504.0075.0%
^(\w{3,})(?!\1).*\h.*\1$414017102.4258.7%
((\w{2,8},?(\P{Z}|\R)){1,2}\.\s?)$409010803.7973.6%
\b\w*?((.){1,3}\w*\2)\w*?(?1)14905502.7163.1%
\w*?(b{2,3})\w*?c11302903.9074.3%
\P{Lu}\P{L&}{0,12}[\s\-]{1,4}..[\P{L}\P{N}]{4}270803.3870.4%
\b(\B([c-h])\B|[a-z]+?(?1)[a-z])7502403.1268.0%
Average:10503513.0662.2%
Utf8 input on a 64 bit x86 machine.

Conclusion

JIT compiling is a powerful technology, which is able to speed up interpreted execution including Java, JavaScript, ActionScript (with NanoJIT) or regular expression engines.

Contribution

I would like to encourage all of you to join the PCRE Performance Project, and make PCRE faster than ever. My email address is hzmester (at) freemail (dot) hu.

Special thanks

First and foremost, the author thanks Philip Hazel for his continual help and support.

Sorted as familiy name in alphabetic order:
Giuseppe D'Angelo-QRegularExpression in Qt 5 and above.
Victor Julien-Suricata project (http://www.openinfosecfoundation.org/).
Sheri Pierce-Testing and feedback.
Petr Pisar

Last modification: 09.07.2014