Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_33_1/libs/regex/doc/gcc-performance.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 17 years ago
added boost
File size: 20.4 KB

Line
1	<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
2	<html>
3	<head>
4	<title>Regular Expression Performance Comparison (gcc 3.2)</title>
5	<meta name="generator" content="HTML Tidy, see www.w3.org">
6	<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
7	<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
8	<META content="C:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dot" name="Template">
9	<meta name="GENERATOR" content="Microsoft FrontPage Express 2.0">
10	</head>
11	<body bgcolor="#ffffff" link="#0000ff" vlink="#800080">
12	<h2>Regular Expression Performance Comparison</h2>
13	<p>The following tables provide comparisons between the following regular
14	expression libraries:</p>
15	<p><a href="http://www.boost.org/">The Boost regex library</a>.</p>
16	<p><a href="http://www.gnu.org">The GNU regular expression library</a>.</p>
17	<p>Philip Hazel's <a href="http://www.pcre.org">PCRE</a> library.</p>
18	<h3>Details</h3>
19	<p>Machine: Intel Pentium 4 2.8GHz PC.</p>
20	<p>Compiler: GNU C++ version 3.2 20020927 (prerelease).</p>
21	<p>C++ Standard Library: GNU libstdc++ version 20020927.</p>
22	<p>OS: Cygwin.</p>
23	<p>Boost version: 1.31.0.</p>
24	<p>PCRE version: 4.1.</p>
25	<p>As ever care should be taken in interpreting the results, only sensible regular
26	expressions (rather than pathological cases) are given, most are taken from the
27	Boost regex examples, or from the <a href="http://www.regxlib.com/">Library of
28	Regular Expressions</a>. In addition, some variation in the relative
29	performance of these libraries can be expected on other machines - as memory
30	access and processor caching effects can be quite large for most finite state
31	machine algorithms. In each case the first figure given is the relative time
32	taken (so a value of 1.0 is as good as it gets), while the second figure is the
33	actual time taken.</p>
34	<h3>Averages</h3>
35	<p>The following are the average relative scores for all the tests: the perfect
36	regular expression library would score 1, in practice anything less than 2
37	is pretty good.</p>
38	<table border="1" cellspacing="1">
39	<tr>
40	<td><strong>Boost</strong></td>
41	<td><strong>Boost + C++ locale</strong></td>
42	<td><strong>POSIX</strong></td>
43	<td><strong>PCRE</strong></td>
44	</tr>
45	<tr>
46	<td>1.4503</td>
47	<td>1.49124</td>
48	<td>108.372</td>
49	<td>1.56255</td>
50	</tr>
51	</table>
52	<br>
53	<br>
54	<h3>Comparison 1: Long Search</h3>
55	<p>For each of the following regular expressions the time taken to find all
56	occurrences of the expression within a long English language text was measured
57	(<a href="http://www.gutenberg.org/files/3200/old/mtent12.zip">mtent12.txt</a>
58	from <a href="http://promo.net/pg/">Project Gutenberg</a>, 19Mb). </p>
59	<table border="1" cellspacing="1">
60	<tr>
61	<td><strong>Expression</strong></td>
62	<td><strong>Boost</strong></td>
63	<td><strong>Boost + C++ locale</strong></td>
64	<td><strong>POSIX</strong></td>
65	<td><strong>PCRE</strong></td>
66	</tr>
67	<tr>
68	<td><code>Twain</code></td>
69	<td>3.49<br>
70	(0.205s)</td>
71	<td>4.09<br>
72	(0.24s)</td>
73	<td>65.2<br>
74	(3.83s)</td>
75	<td><font color="#008000">1<br>
76	(0.0588s)</font></td>
77	</tr>
78	<tr>
79	<td><code>Huck[[:alpha:]]+</code></td>
80	<td>3.86<br>
81	(0.203s)</td>
82	<td>4.52<br>
83	(0.238s)</td>
84	<td>100<br>
85	(5.26s)</td>
86	<td><font color="#008000">1<br>
87	(0.0526s)</font></td>
88	</tr>
89	<tr>
90	<td><code>[[:alpha:]]+ing</code></td>
91	<td><font color="#008000">1.01<br>
92	(1.23s)</font></td>
93	<td><font color="#008000">1<br>
94	(1.22s)</font></td>
95	<td>4.95<br>
96	(6.04s)</td>
97	<td>4.67<br>
98	(5.71s)</td>
99	</tr>
100	<tr>
101	<td><code>^[^ ]*?Twain</code></td>
102	<td><font color="#008000">1<br>
103	(0.31s)</font></td>
104	<td><font color="#008000">1.05<br>
105	(0.326s)</font></td>
106	<td>NA</td>
107	<td>3.32<br>
108	(1.03s)</td>
109	</tr>
110	<tr>
111	<td><code>Tom\|Sawyer\|Huckleberry\|Finn</code></td>
112	<td><font color="#008000">1.02<br>
113	(0.125s)</font></td>
114	<td><font color="#008000">1<br>
115	(0.123s)</font></td>
116	<td>165<br>
117	(20.3s)</td>
118	<td><font color="#008000">1.08<br>
119	(0.133s)</font></td>
120	</tr>
121	<tr>
122	<td><code> (Tom\|Sawyer\|Huckleberry\|Finn).{0,30}river\|river.{0,30}(Tom\|Sawyer\|Huckleberry\|Finn)</code></td>
123	<td><font color="#008000">1<br>
124	(0.345s)</font></td>
125	<td><font color="#008000">1.03<br>
126	(0.355s)</font></td>
127	<td>NA</td>
128	<td>1.71<br>
129	(0.59s)</td>
130	</tr>
131	</table>
132	<br>
133	<br>
134	<h3>Comparison 2: Medium Sized Search</h3>
135	<p>For each of the following regular expressions the time taken to find all
136	occurrences of the expression within a medium sized English language text was
137	measured (the first 50K from mtent12.txt). </p>
138	<table border="1" cellspacing="1">
139	<tr>
140	<td><strong>Expression</strong></td>
141	<td><strong>Boost</strong></td>
142	<td><strong>Boost + C++ locale</strong></td>
143	<td><strong>POSIX</strong></td>
144	<td><strong>PCRE</strong></td>
145	</tr>
146	<tr>
147	<td><code>Twain</code></td>
148	<td>1.8<br>
149	(0.000519s)</td>
150	<td>2.14<br>
151	(0.000616s)</td>
152	<td>9.08<br>
153	(0.00262s)</td>
154	<td><font color="#008000">1<br>
155	(0.000289s)</font></td>
156	</tr>
157	<tr>
158	<td><code>Huck[[:alpha:]]+</code></td>
159	<td>3.65<br>
160	(0.000499s)</td>
161	<td>4.36<br>
162	(0.000597s)</td>
163	<td><font color="#008000">1<br>
164	(0.000137s)</font></td>
165	<td>1.43<br>
166	(0.000196s)</td>
167	</tr>
168	<tr>
169	<td><code>[[:alpha:]]+ing</code></td>
170	<td><font color="#008000">1<br>
171	(0.00258s)</font></td>
172	<td><font color="#008000">1<br>
173	(0.00258s)</font></td>
174	<td>5.28<br>
175	(0.0136s)</td>
176	<td>5.63<br>
177	(0.0145s)</td>
178	</tr>
179	<tr>
180	<td><code>^[^ ]*?Twain</code></td>
181	<td><font color="#008000">1<br>
182	(0.000929s)</font></td>
183	<td><font color="#008000">1.03<br>
184	(0.000957s)</font></td>
185	<td>NA</td>
186	<td>2.82<br>
187	(0.00262s)</td>
188	</tr>
189	<tr>
190	<td><code>Tom\|Sawyer\|Huckleberry\|Finn</code></td>
191	<td><font color="#008000">1<br>
192	(0.000812s)</font></td>
193	<td><font color="#008000">1<br>
194	(0.000812s)</font></td>
195	<td>60.1<br>
196	(0.0488s)</td>
197	<td>1.28<br>
198	(0.00104s)</td>
199	</tr>
200	<tr>
201	<td><code> (Tom\|Sawyer\|Huckleberry\|Finn).{0,30}river\|river.{0,30}(Tom\|Sawyer\|Huckleberry\|Finn)</code></td>
202	<td><font color="#008000">1.02<br>
203	(0.00178s)</font></td>
204	<td><font color="#008000">1<br>
205	(0.00174s)</font></td>
206	<td>242<br>
207	(0.421s)</td>
208	<td>1.3<br>
209	(0.00227s)</td>
210	</tr>
211	</table>
212	<br>
213	<br>
214	<h3>Comparison 3: C++ Code Search</h3>
215	<p>For each of the following regular expressions the time taken to find all
216	occurrences of the expression within the C++ source file <a href="../../../boost/crc.hpp">
217	boost/crc.hpp</a> was measured. </p>
218	<table border="1" cellspacing="1">
219	<tr>
220	<td><strong>Expression</strong></td>
221	<td><strong>Boost</strong></td>
222	<td><strong>Boost + C++ locale</strong></td>
223	<td><strong>POSIX</strong></td>
224	<td><strong>PCRE</strong></td>
225	</tr>
226	<tr>
227	<td><code> ^(template[[:space:]]<[^;:{]+>[[:space:]])?(class\|struct)[[:space:]]*(\<\w+\>([
228	]\([^)]\))?[[:space:]])(\<\w\>)[[:space:]](<[^;:{]+>[[:space:]])?(\{\|:[^;\{()]\{)</code></td>
229	<td><font color="#008000">1.04<br>
230	(0.000144s)</font></td>
231	<td><font color="#008000">1<br>
232	(0.000139s)</font></td>
233	<td>862<br>
234	(0.12s)</td>
235	<td>4.56<br>
236	(0.000636s)</td>
237	</tr>
238	<tr>
239	<td><code>(^[
240	]#(?:[^\\\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)\></code></td>
241	<td><font color="#008000">1<br>
242	(0.0139s)</font></td>
243	<td><font color="#008000">1.01<br>
244	(0.0141s)</font></td>
245	<td>NA</td>
246	<td>1.55<br>
247	(0.0216s)</td>
248	</tr>
249	<tr>
250	<td><code>^[ ]#[ ]include[ ]+("[^"]+"\|<[^>]+>)</code></td>
251	<td><font color="#008000">1.04<br>
252	(0.000332s)</font></td>
253	<td><font color="#008000">1<br>
254	(0.000318s)</font></td>
255	<td>130<br>
256	(0.0413s)</td>
257	<td>1.72<br>
258	(0.000547s)</td>
259	</tr>
260	<tr>
261	<td><code>^[ ]#[ ]include[ ]+("boost/[^"]+"\|<boost/[^>]+>)</code></td>
262	<td><font color="#008000">1.02<br>
263	(0.000323s)</font></td>
264	<td><font color="#008000">1<br>
265	(0.000318s)</font></td>
266	<td>150<br>
267	(0.0476s)</td>
268	<td>1.72<br>
269	(0.000547s)</td>
270	</tr>
271	</table>
272	<br>
273	<h3></h3>
274	<H3>Comparison 4: HTML Document Search
275	</H3>
276	<p>For each of the following regular expressions the time taken to find all
277	occurrences of the expression within the html file <a href="../../libraries.htm">libs/libraries.htm</a>
278	was measured. </p>
279	<table border="1" cellspacing="1">
280	<tr>
281	<td><strong>Expression</strong></td>
282	<td><strong>Boost</strong></td>
283	<td><strong>Boost + C++ locale</strong></td>
284	<td><strong>POSIX</strong></td>
285	<td><strong>PCRE</strong></td>
286	</tr>
287	<tr>
288	<td><code>beman\|john\|dave</code></td>
289	<td><font color="#008000">1.03<br>
290	(0.000367s)</font></td>
291	<td><font color="#008000">1<br>
292	(0.000357s)</font></td>
293	<td>47.4<br>
294	(0.0169s)</td>
295	<td>1.16<br>
296	(0.000416s)</td>
297	</tr>
298	<tr>
299	<td><code><p>.*?</p></code></td>
300	<td>1.25<br>
301	(0.000459s)</td>
302	<td><font color="#008000">1<br>
303	(0.000367s)</font></td>
304	<td>NA</td>
305	<td><font color="#008000">1.03<br>
306	(0.000376s)</font></td>
307	</tr>
308	<tr>
309	<td><code> <a[^>]+href=("[^"]"\|[^[:space:]]+)[^>]></code></td>
310	<td><font color="#008000">1<br>
311	(0.000509s)</font></td>
312	<td><font color="#008000">1.02<br>
313	(0.000518s)</font></td>
314	<td>305<br>
315	(0.155s)</td>
316	<td><font color="#008000">1.1<br>
317	(0.000558s)</font></td>
318	</tr>
319	<tr>
320	<td><code> <h[12345678][^>]>.?</h[12345678]></code></td>
321	<td><font color="#008000">1.04<br>
322	(0.00025s)</font></td>
323	<td><font color="#008000">1<br>
324	(0.00024s)</font></td>
325	<td>NA</td>
326	<td>1.16<br>
327	(0.000279s)</td>
328	</tr>
329	<tr>
330	<td><code> <img[^>]+src=("[^"]"\|[^[:space:]]+)[^>]></code></td>
331	<td>2.22<br>
332	(0.000489s)</td>
333	<td>1.69<br>
334	(0.000372s)</td>
335	<td>148<br>
336	(0.0326s)</td>
337	<td><font color="#008000">1<br>
338	(0.00022s)</font></td>
339	</tr>
340	<tr>
341	<td><code> <font[^>]+face=("[^"]"\|[^[:space:]]+)[^>]>.*?</font></code></td>
342	<td>1.71<br>
343	(0.000371s)</td>
344	<td>1.75<br>
345	(0.000381s)</td>
346	<td>NA</td>
347	<td><font color="#008000">1<br>
348	(0.000218s)</font></td>
349	</tr>
350	</table>
351	<br>
352	<br>
353	<h3>Comparison 3: Simple Matches</h3>
354	<p>For each of the following regular expressions the time taken to match against
355	the text indicated was measured. </p>
356	<table border="1" cellspacing="1">
357	<tr>
358	<td><strong>Expression</strong></td>
359	<td><strong>Text</strong></td>
360	<td><strong>Boost</strong></td>
361	<td><strong>Boost + C++ locale</strong></td>
362	<td><strong>POSIX</strong></td>
363	<td><strong>PCRE</strong></td>
364	</tr>
365	<tr>
366	<td><code>abc</code></td>
367	<td>abc</td>
368	<td>1.36<br>
369	(2.15e-07s)</td>
370	<td>1.36<br>
371	(2.15e-07s)</td>
372	<td>2.76<br>
373	(4.34e-07s)</td>
374	<td><font color="#008000">1<br>
375	(1.58e-07s)</font></td>
376	</tr>
377	<tr>
378	<td><code>^([0-9]+)(\-\| \|$)(.*)$</code></td>
379	<td>100- this is a line of ftp response which contains a message string</td>
380	<td>1.55<br>
381	(7.26e-07s)</td>
382	<td>1.51<br>
383	(7.07e-07s)</td>
384	<td>319<br>
385	(0.000149s)</td>
386	<td><font color="#008000">1<br>
387	(4.67e-07s)</font></td>
388	</tr>
389	<tr>
390	<td><code>([[:digit:]]{4}[- ]){3}[[:digit:]]{3,4}</code></td>
391	<td>1234-5678-1234-456</td>
392	<td>1.96<br>
393	(9.54e-07s)</td>
394	<td>1.96<br>
395	(9.54e-07s)</td>
396	<td>44.5<br>
397	(2.17e-05s)</td>
398	<td><font color="#008000">1<br>
399	(4.87e-07s)</font></td>
400	</tr>
401	<tr>
402	<td><code> ^([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})(\]?)$</code></td>
403	<td>john@johnmaddock.co.uk</td>
404	<td>1.22<br>
405	(1.51e-06s)</td>
406	<td>1.23<br>
407	(1.53e-06s)</td>
408	<td>162<br>
409	(0.000201s)</td>
410	<td><font color="#008000">1<br>
411	(1.24e-06s)</font></td>
412	</tr>
413	<tr>
414	<td><code> ^([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})(\]?)$</code></td>
415	<td>foo12@foo.edu</td>
416	<td>1.28<br>
417	(1.47e-06s)</td>
418	<td>1.3<br>
419	(1.49e-06s)</td>
420	<td>104<br>
421	(0.00012s)</td>
422	<td><font color="#008000">1<br>
423	(1.15e-06s)</font></td>
424	</tr>
425	<tr>
426	<td><code> ^([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})(\]?)$</code></td>
427	<td>bob.smith@foo.tv</td>
428	<td>1.28<br>
429	(1.47e-06s)</td>
430	<td>1.3<br>
431	(1.49e-06s)</td>
432	<td>113<br>
433	(0.00013s)</td>
434	<td><font color="#008000">1<br>
435	(1.15e-06s)</font></td>
436	</tr>
437	<tr>
438	<td><code>^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$</code></td>
439	<td>EH10 2QQ</td>
440	<td>1.38<br>
441	(4.68e-07s)</td>
442	<td>1.41<br>
443	(4.77e-07s)</td>
444	<td>13.5<br>
445	(4.59e-06s)</td>
446	<td><font color="#008000">1<br>
447	(3.39e-07s)</font></td>
448	</tr>
449	<tr>
450	<td><code>^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$</code></td>
451	<td>G1 1AA</td>
452	<td>1.28<br>
453	(4.35e-07s)</td>
454	<td>1.25<br>
455	(4.25e-07s)</td>
456	<td>11.7<br>
457	(3.97e-06s)</td>
458	<td><font color="#008000">1<br>
459	(3.39e-07s)</font></td>
460	</tr>
461	<tr>
462	<td><code>^[a-zA-Z]{1,2}[0-9][0-9A-Za-z]{0,1} {0,1}[0-9][A-Za-z]{2}$</code></td>
463	<td>SW1 1ZZ</td>
464	<td>1.32<br>
465	(4.53e-07s)</td>
466	<td>1.31<br>
467	(4.49e-07s)</td>
468	<td>12.2<br>
469	(4.2e-06s)</td>
470	<td><font color="#008000">1<br>
471	(3.44e-07s)</font></td>
472	</tr>
473	<tr>
474	<td><code> ^[[:digit:]]{1,2}/[[:digit:]]{1,2}/[[:digit:]]{4}$</code></td>
475	<td>4/1/2001</td>
476	<td>1.16<br>
477	(3.82e-07s)</td>
478	<td>1.2<br>
479	(3.96e-07s)</td>
480	<td>13.9<br>
481	(4.59e-06s)</td>
482	<td><font color="#008000">1<br>
483	(3.29e-07s)</font></td>
484	</tr>
485	<tr>
486	<td><code> ^[[:digit:]]{1,2}/[[:digit:]]{1,2}/[[:digit:]]{4}$</code></td>
487	<td>12/12/2001</td>
488	<td>1.38<br>
489	(4.49e-07s)</td>
490	<td>1.38<br>
491	(4.49e-07s)</td>
492	<td>16<br>
493	(5.2e-06s)</td>
494	<td><font color="#008000">1<br>
495	(3.25e-07s)</font></td>
496	</tr>
497	<tr>
498	<td><code>^[-+]?[[:digit:]]\.?[[:digit:]]$</code></td>
499	<td>123</td>
500	<td>1.19<br>
501	(7.64e-07s)</td>
502	<td>1.16<br>
503	(7.45e-07s)</td>
504	<td>7.51<br>
505	(4.81e-06s)</td>
506	<td><font color="#008000">1<br>
507	(6.4e-07s)</font></td>
508	</tr>
509	<tr>
510	<td><code>^[-+]?[[:digit:]]\.?[[:digit:]]$</code></td>
511	<td>+3.14159</td>
512	<td>1.32<br>
513	(8.97e-07s)</td>
514	<td>1.31<br>
515	(8.88e-07s)</td>
516	<td>14<br>
517	(9.48e-06s)</td>
518	<td><font color="#008000">1<br>
519	(6.78e-07s)</font></td>
520	</tr>
521	<tr>
522	<td><code>^[-+]?[[:digit:]]\.?[[:digit:]]$</code></td>
523	<td>-3.14159</td>
524	<td>1.32<br>
525	(8.97e-07s)</td>
526	<td>1.31<br>
527	(8.88e-07s)</td>
528	<td>14<br>
529	(9.48e-06s)</td>
530	<td><font color="#008000">1<br>
531	(6.78e-07s)</font></td>
532	</tr>
533	</table>
534	<br>
535	<br>
536	<hr>
537	<p>Copyright John Maddock April 2003, all rights reserved.</p>
538	</body>
539	</html>

Note: See TracBrowser for help on using the repository browser.

Download in other formats: