Mantis Bugtracker
  

Viewing Issue Advanced Details Jump to Notes ] View Simple ] Issue History ] Print ]
ID 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   OS
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[^]
Copyright © 2000 - 2005 Mantis Group
32 total queries executed.
28 unique queries executed.
Powered by Mantis Bugtracker