0003195: Anchored regexes take time proportional to subject string size

Viewing Issue Simple Details [ Jump to Notes ]

[ View Advanced ] [ Issue History ] [ Print ]

Category

Severity

Reproducibility

Date Submitted

Last Update

0003195

[Quercus]

major

always

12-24-08 21:52

12-27-08 15:40

Reporter

koreth

View Status

public

Assigned To

ferg

Priority

normal

Resolution

fixed

Status

closed

Product Version

4.0.0

Summary

0003195: Anchored regexes take time proportional to subject string size

Description

<?php
$sizes = array(1000, 10000, 100000, 1000000, 10000000);
foreach ($sizes as $size) {
  $str = str_repeat('abcde', $size);
  $start_time = microtime(true);
  $match = preg_match('/x/A', $str);
  $end_time = microtime(true);
  printf("size %d took %0.6fsec
\n", $size, $end_time - $start_time);
}

In regular PHP, each run takes more or less the same amount of time. In Quercus, each run takes longer than the last by a factor of 10.

The behavior is also there if you use /^x/ instead of /x/A to anchor the regex.

This is making some of our on-the-fly JavaScript rewriting run so slowly the scripts time out.

Additional Information

Attached Files

Relationships

Notes
(0003674) koreth 12-24-08 22:04	One other note is that this only seems to be the case for failed matches. If a match succeeds it does so right away.

(0003676) ferg 12-27-08 15:40	php/4e82

Issue History
Date Modified	Username	Field	Change
12-24-08 21:52	koreth	New Issue
12-24-08 22:04	koreth	Note Added: 0003674
12-26-08 09:26	nam	Status	new => assigned
12-26-08 09:26	nam	Assigned To	=> nam
12-27-08 15:40	ferg	Note Added: 0003676
12-27-08 15:40	ferg	Assigned To	nam => ferg
12-27-08 15:40	ferg	Status	assigned => closed
12-27-08 15:40	ferg	Resolution	open => fixed
12-27-08 15:40	ferg	Fixed in Version	=> 4.0.0

Mantis 1.0.0rc3[^]

32 total queries executed.
28 unique queries executed.