0003195: Anchored regexes take time proportional to subject string size

Viewing Issue Advanced Details [ Jump to Notes ]

[ View Simple ] [ 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

Platform

Status

closed

Projection

none

OS Version

ETA

none

Fixed in Version

4.0.0

Product Version

4.0.0

Product Build

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.

Steps To Reproduce

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.