Regular Expression Performance Comparison

The following tables provide comparisons between the following regular expression libraries:

The Boost regex library.

The GNU regular expression library.

Philip Hazel's PCRE library.

Details

Machine: Intel Pentium 4 2.8GHz PC.

Compiler: GNU C++ version 3.2 20020927 (prerelease).

C++ Standard Library: GNU libstdc++ version 20020927.

OS: Cygwin.

Boost version: 1.31.0.

PCRE version: 4.1.

As ever care should be taken in interpreting the results, only sensible regular expressions (rather than pathological cases) are given, most are taken from the Boost regex examples, or from the Library of Regular Expressions. In addition, some variation in the relative performance of these libraries can be expected on other machines - as memory access and processor caching effects can be quite large for most finite state machine algorithms. In each case the first figure given is the relative time taken (so a value of 1.0 is as good as it gets), while the second figure is the actual time taken.

Averages

The following are the average relative scores for all the tests: the perfect regular expression library would score 1, in practice anything less than 2 is pretty good.

Boost Boost + C++ locale POSIX PCRE
1.4503 1.49124 108.372 1.56255


Comparison 1: Long Search

For each of the following regular expressions the time taken to find all occurrences of the expression within a long English language text was measured (mtent12.txt from Project Gutenberg, 19Mb). 

Expression Boost Boost + C++ locale POSIX PCRE
Twain 3.49
(0.205s)
4.09
(0.24s)
65.2
(3.83s)
1
(0.0588s)
Huck[[:alpha:]]+ 3.86
(0.203s)
4.52
(0.238s)
100
(5.26s)
1
(0.0526s)
[[:alpha:]]+ing 1.01
(1.23s)
1
(1.22s)
4.95
(6.04s)
4.67
(5.71s)
^[^ ]*?Twain 1
(0.31s)
1.05
(0.326s)
NA 3.32
(1.03s)
Tom|Sawyer|Huckleberry|Finn 1.02
(0.125s)
1
(0.123s)
165
(20.3s)
1.08
(0.133s)
(Tom|Sawyer|Huckleberry|Finn).{0,30}river|river.{0,30}(Tom|Sawyer|Huckleberry|Finn) 1
(0.345s)
1.03
(0.355s)
NA 1.71
(0.59s)


Comparison 2: Medium Sized Search

For each of the following regular expressions the time taken to find all occurrences of the expression within a medium sized English language text was measured (the first 50K from mtent12.txt). 

Expression Boost Boost + C++ locale POSIX PCRE
Twain 1.8
(0.000519s)
2.14
(0.000616s)
9.08
(0.00262s)
1
(0.000289s)
Huck[[:alpha:]]+ 3.65
(0.000499s)
4.36
(0.000597s)
1
(0.000137s)
1.43
(0.000196s)
[[:alpha:]]+ing 1
(0.00258s)
1
(0.00258s)
5.28
(0.0136s)
5.63
(0.0145s)
^[^ ]*?Twain 1
(0.000929s)
1.03
(0.000957s)
NA 2.82
(0.00262s)
Tom|Sawyer|Huckleberry|Finn 1
(0.000812s)
1
(0.000812s)
60.1
(0.0488s)
1.28
(0.00104s)
(Tom|Sawyer|Huckleberry|Finn).{0,30}river|river.{0,30}(Tom|Sawyer|Huckleberry|Finn) 1.02
(0.00178s)
1
(0.00174s)
242
(0.421s)
1.3
(0.00227s)


Comparison 3: C++ Code Search

For each of the following regular expressions the time taken to find all occurrences of the expression within the C++ source file boost/crc.hpp was measured. 

Expression Boost Boost + C++ locale POSIX PCRE
^(template[[:space:]]*<[^;:{]+>[[:space:]]*)?(class|struct)[[:space:]]*(\<\w+\>([ ]*\([^)]*\))?[[:space:]]*)*(\<\w*\>)[[:space:]]*(<[^;:{]+>[[:space:]]*)?(\{|:[^;\{()]*\{) 1.04
(0.000144s)
1
(0.000139s)
862
(0.12s)
4.56
(0.000636s)
(^[ ]*#(?:[^\\\n]|\\[^\n_[:punct:][:alnum:]]*[\n[:punct:][:word:]])*)|(//[^\n]*|/\*.*?\*/)|\<([+-]?(?:(?:0x[[:xdigit:]]+)|(?:(?:[[:digit:]]*\.)?[[:digit:]]+(?:[eE][+-]?[[:digit:]]+)?))u?(?:(?:int(?:8|16|32|64))|L)?)\>|('(?:[^\\']|\\.)*'|"(?:[^\\"]|\\.)*")|\<(__asm|__cdecl|__declspec|__export|__far16|__fastcall|__fortran|__import|__pascal|__rtti|__stdcall|_asm|_cdecl|__except|_export|_far16|_fastcall|__finally|_fortran|_import|_pascal|_stdcall|__thread|__try|asm|auto|bool|break|case|catch|cdecl|char|class|const|const_cast|continue|default|delete|do|double|dynamic_cast|else|enum|explicit|extern|false|float|for|friend|goto|if|inline|int|long|mutable|namespace|new|operator|pascal|private|protected|public|register|reinterpret_cast|return|short|signed|sizeof|static|static_cast|struct|switch|template|this|throw|true|try|typedef|typeid|typename|union|unsigned|using|virtual|void|volatile|wchar_t|while)\> 1
(0.0139s)
1.01
(0.0141s)
NA 1.55
(0.0216s)
^[ ]*#[ ]*include[ ]+("[^"]+"|<[^>]+>) 1.04
(0.000332s)
1
(0.000318s)
130
(0.0413s)
1.72
(0.000547s)
^[ ]*#[ ]*include[ ]+("boost/[^"]+"|<boost/[^>]+>) 1.02
(0.000323s)
1
(0.000318s)
150
(0.0476s)
1.72
(0.000547s)

Comparison 4: HTML Document Search

For each of the following regular expressions the time taken to find all occurrences of the expression within the html file libs/libraries.htm was measured. 

Expression Boost Boost + C++ locale POSIX PCRE
beman|john|dave 1.03
(0.000367s)
1
(0.000357s)
47.4
(0.0169s)
1.16
(0.000416s)
<p>.*?</p> 1.25
(0.000459s)
1
(0.000367s)
NA 1.03
(0.000376s)
<a[^>]+href=("[^"]*"|[^[:space:]]+)[^>]*> 1
(0.000509s)
1.02
(0.000518s)
305
(0.155s)
1.1
(0.000558s)
<h[12345678][^>]*>.*?</h[12345678]> 1.04
(0.00025s)
1
(0.00024s)
NA 1.16
(0.000279s)
<img[^>]+src=("[^"]*"|[^[:space:]]+)[^>]*> 2.22
(0.000489s)
1.69
(0.000372s)
148
(0.0326s)
1
(0.00022s)
<font[^>]+face=("[^"]*"|[^[:space:]]+)[^>]*>.*?</font> 1.71
(0.000371s)
1.75
(0.000381s)
NA 1
(0.000218s)


Comparison 3: Simple Matches

For each of the following regular expressions the time taken to match against the text indicated was measured. 

Expression Text Boost Boost + C++ locale POSIX PCRE
abc abc 1.36
(2.15e-07s)
1.36
(2.15e-07s)
2.76
(4.34e-07s)
1
(1.58e-07s)
^([0-9]+)(\-| |$)(.*)$ 100- this is a line of ftp response which contains a message string 1.55
(7.26e-07s)
1.51
(7.07e-07s)
319
(0.000149s)
1
(4.67e-07s)
([[:digit:]]{4}[- ]){3}[[:digit:]]{3,4} 1234-5678-1234-456 1.96
(9.54e-07s)
1.96
(9.54e-07s)
44.5
(2.17e-05s)
1
(4.87e-07s)
^([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)$ [email protected] 1.22
(1.51e-06s)
1.23
(1.53e-06s)
162
(0.000201s)
1
(1.24e-06s)
^([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)$ [email protected] 1.28
(1.47e-06s)
1.3
(1.49e-06s)
104
(0.00012s)
1
(1.15e-06s)
^([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)$ [email protected] 1.28
(1.47e-06s)
1.3
(1.49e-06s)
113
(0.00013s)
1
(1.15e-06s)
^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$ EH10 2QQ 1.38
(4.68e-07s)
1.41
(4.77e-07s)
13.5
(4.59e-06s)
1
(3.39e-07s)
^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$ G1 1AA 1.28
(4.35e-07s)
1.25
(4.25e-07s)
11.7
(3.97e-06s)
1
(3.39e-07s)
^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$ SW1 1ZZ 1.32
(4.53e-07s)
1.31
(4.49e-07s)
12.2
(4.2e-06s)
1
(3.44e-07s)
^[[:digit:]]{1,2}/[[:digit:]]{1,2}/[[:digit:]]{4}$ 4/1/2001 1.16
(3.82e-07s)
1.2
(3.96e-07s)
13.9
(4.59e-06s)
1
(3.29e-07s)
^[[:digit:]]{1,2}/[[:digit:]]{1,2}/[[:digit:]]{4}$ 12/12/2001 1.38
(4.49e-07s)
1.38
(4.49e-07s)
16
(5.2e-06s)
1
(3.25e-07s)
^[-+]?[[:digit:]]*\.?[[:digit:]]*$ 123 1.19
(7.64e-07s)
1.16
(7.45e-07s)
7.51
(4.81e-06s)
1
(6.4e-07s)
^[-+]?[[:digit:]]*\.?[[:digit:]]*$ +3.14159 1.32
(8.97e-07s)
1.31
(8.88e-07s)
14
(9.48e-06s)
1
(6.78e-07s)
^[-+]?[[:digit:]]*\.?[[:digit:]]*$ -3.14159 1.32
(8.97e-07s)
1.31
(8.88e-07s)
14
(9.48e-06s)
1
(6.78e-07s)



Copyright John Maddock April 2003, all rights reserved.