|
Read the original (no copy/paste) post
by dark100 at http://sljit.sourceforge.net/regex_perf.html
Performance comparison of regular expression engines
Introduction
Processing text or raw byte-sequence are among the common tasks performed by most software tools.
These tasks usually involve pattern matching algorithms, and the most popular tool for such purpose
is regular expressions. Regular expressions has been evolved a lot since Kleene defined the regular
sets in the 1950's. Today we have several widely used regular expression engines which have
different features
which makes any performance comparison a difficult task, since a faster engine is not necessary
better. Depending on the use case it might be enough to know whether a POSIX compatible regular
expression matches to a line, even the position of the match is unneeded (grep utility). On the
contrary other use cases require the position of capturing brackets, unicode support, conditional and
atomic block (handling a byte sequence as a single character, like 'sch' in German language) support
just to name a few. The former case needs a less sophisticated algorithm, which is likely be much
faster than the latter, but again, that does not mean the former is better. More about these
engine types can be found here.
Participants
The following popular engines were choosen:
and
Before anyone jump to any conclusions, I should note the followings:
- The engines were not fine tuned (because of my lack of knowledge about their internal workings).
I just compiled them with the default options. I know enabling or disabling some features can
heavily affect the results. If you feel that you have a better configuration just drop me an
e-mail and I will update the results (hzmester(at)freemail(dot)hu).
- The regular expression engines are compiled with -O3 to allow the best performance.
- This comparison page was inspired by the work of John Maddock (See his own regex comparison
here).
The input is also the same he used before:
mtent12.zip.
It is a text file (e-book) which size is about 20 Mbytes.
- Only common patterns are selected, they are not pathological cases nor have any PERL
specific features. The comparison was caseful.
Results
x86-64 bit Intel Cerelon 847 1.1GHz (GCC 6.2.1, GNU/Linux)
| Regular expression | PCRE | PCRE
-DFA | TRE | Onig-
uruma | RE2 | PCRE
-JIT | regexp3 | regexp4 |
|---|
| 4416 ms (20045118) | 4982 ms (20045118) | 6639 ms (20045118) | 2156 ms (20045118) | 7306 ms (20045118) | 1075 ms (20045118) | 1803 ms (20045118) | 753 ms (20045118) |
| 2881 ms (14751878) | 2991 ms (14751878) | 4693 ms (14751878) | 2316 ms (14751878) | 5517 ms (14751878) | 945 ms (14751878) | 1885 ms (14750958) | 915 ms (14750958) |
| 67 ms (27084) | 67 ms (27084) | 1034 ms (27084) | 134 ms (27084) | 233 ms (27084) | 57 ms (27084) | 1769 ms (27084) | 585 ms (27084) |
| 3002 ms (15451664) | 3083 ms (15451664) | 4633 ms (15451664) | 1763 ms (15451664) | 5806 ms (15451664) | 887 ms (15451664) | 1908 ms (15451664) | 927 ms (15451664) |
| 931 ms (3430783) | 1060 ms (3430783) | 1882 ms (991813) | 773 ms (3430783) | 1773 ms (3430783) | 380 ms (3430783) | 4051 ms (3430783) | 1377 ms (3430783) |
| 187 ms (438367) | 232 ms (438367) | 1407 ms (438367) | 226 ms (438367) | 409 ms (438367) | 45 ms (438367) | 3726 ms (438367) | 1035 ms (438367) |
| 360 ms (1781425) | 426 ms (1781425) | 496 ms (1781425) | 437 ms (1781425) | 722 ms (1781425) | 134 ms (1781425) | 1795 ms (1781425) | 650 ms (1781425) |
| 1226 ms (1781425) | 1098 ms (1781425) | 490 ms (1781425) | 844 ms (1781425) | 723 ms (1781425) | 202 ms (1781425) | 26092 ms (1781425) | 3548 ms (1781425) |
| ((((((((((e)))))))))) | | <<<<<<<<<<e>>>>>>>>>> |
| 1907 ms (1781425) | 1741 ms (1781425) | 489 ms (1781425) | 1095 ms (1781425) | 726 ms (1781425) | 312 ms (1781425) | 82855 ms (1781425) | 5421 ms (1781425) |
| 10 ms (2388) | 47 ms (2388) | 987 ms (2388) | 52 ms (2388) | 8 ms (2388) | 50 ms (2388) | 2550 ms (2388) | 554 ms (2388) |
| 14 ms (2388) | 48 ms (2388) | 988 ms (2388) | 52 ms (2388) | 8 ms (2388) | 50 ms (2388) | 7145 ms (2388) | 940 ms (2388) |
| 198 ms (2657) | 285 ms (2657) | 1253 ms (2657) | 412 ms (2657) | 255 ms (2657) | 52 ms (2657) | 2638 ms (2657) | 697 ms (2657) |
| ((T|t)(w|W)(a|A)i([a-z]|1)) | | <<T|t><w|W><a|A>i<[a-z]|1>> |
| 673 ms (2427) | 531 ms (2427) | 1928 ms (2427) | 358 ms (2427) | 254 ms (2427) | 68 ms (2427) | 24419 ms (2427) | 2393 ms (2427) |
| 1482 ms (1877) | 2309 ms (1877) | 1518 ms (1877) | 49 ms (1877) | 349 ms (1877) | 48 ms (1877) | 5341 ms (1877) | 1426 ms (1877) |
| Huck[a-zA-Z]+|Saw[a-zA-Z]+ | | Huck[a-zA-Z]+|Saw[a-zA-Z]+ |
| 72 ms (396) | 77 ms (396) | 1540 ms (396) | 138 ms (396) | 224 ms (396) | 9 ms (396) | 6161 ms (396) | 1416 ms (396) |
| [a-q][^u-z]{13}x | | [a-q][^u-z]{13}x |
| 1768 ms (4929) | 6307 ms (4929) | 4309 ms (4929) | 171 ms (4929) | 10119 ms (4929) | 5 ms (4929) | 11825 ms (4929) | 4299 ms (4929) |
| Tom|Sawyer|Huckleberry|Finn | | Tom|Sawyer|Huckleberry|Finn |
| 97 ms (3015) | 103 ms (3015) | 2764 ms (3015) | 157 ms (3015) | 226 ms (3015) | 84 ms (3015) | 11291 ms (3015) | 2545 ms (3015) |
| (Tom|Sawyer|Huckleberry|Finn) | | <Tom|Sawyer|Huckleberry|Finn> |
| 102 ms (3015) | 106 ms (3015) | 2754 ms (3015) | 158 ms (3015) | 227 ms (3015) | 82 ms (3015) | 26147 ms (3015) | 2928 ms (3015) |
| [hHeELlLlOo][hHeELlLlOo][hHeELlLlOo][hHeELlLlOo][hHeELlLlOo] | | [hHeELlLlOo][hHeELlLlOo][hHeELlLlOo][hHeELlLlOo][hHeELlLlOo] |
| 619 ms (534) | 887 ms (534) | 3201 ms (534) | 676 ms (534) | 320 ms (534) | 240 ms (534) | 10955 ms (534) | 1662 ms (534) |
| Tom.{10,25}river|river.{10,25}Tom | | Tom([^(river|\n)]){10,25}river|river([^(Tom|\n)]){10,25}Tom | | Tom(river|\n){10,25}#!river|river(Tom|\n){10,25}#!Tom |
| 205 ms (2) | 257 ms (2) | 1749 ms (2) | 264 ms (2) | 244 ms (2) | 45 ms (2) | 13026 ms (2) | 1455 ms (2) |
| 136 ms (85956) | 234 ms (85956) | 1110 ms (85956) | 91 ms (85956) | 100 ms (85956) | 54 ms (85956) | 2846 ms (85956) | 600 ms (85956) |
| [a-zA-Z]ing[^a-zA-Z] | | [a-zA-Z]ing[^a-zA-Z] |
| 1550 ms (85823) | 2371 ms (85823) | 1781 ms (85823) | 93 ms (85823) | 378 ms (85823) | 57 ms (85823) | 6105 ms (85823) | 1534 ms (85823) |
| ([a-zA-Z]+ing) | | <([^(ing|:A)])+ing(([^(ing|:A)])*ing)*> | | <(ing|:A)+#!ing(((ing|:A)*#!ing)*> |
| 4105 ms (95863) | 5539 ms (95863) | 2044 ms (95863) | 2395 ms (95863) | 390 ms (95863) | 229 ms (95863) | 53525 ms (95863) | 6746 ms (95863) |
| ([A-Za-z]awyer|[A-Za-z]inn)\s | | <[A-Za-z]awyer|[A-Za-z]inn>:s |
| 3128 ms (313) | 3635 ms (313) | 2715 ms (313) | 550 ms (313) | 341 ms (313) | 105 ms (313) | 22344 ms (313) | 4088 ms (313) |
Just Donwload, type make. and run runtest.
|