Major slow down (4500X) around particular RegExp
Reported by
bed...@technicalpursuit.com,
Sep 18 2017
|
||||||||
Issue descriptionUserAgent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8 Steps to reproduce the problem: 1. Use the supplied RegExp on a piece of text containing markup 2. 3. What is the expected behavior? Performance would be what it was in prior version of Chrome What went wrong? Performance is 4500X slower. Did this work before? Yes Chrome 60? (not completely sure) Chrome version: 61.0.3163.91 (Official Build) (64-bit) Channel: stable OS Version: OS X 10.12.6 Flash Version: The regex in question attempts to match 'element' markup in a String. It is: /<([A-Za-z_:]|[^\x00-\x7F])([^<>"']+)*$/ Note that removing the '*' quantifier from the last grouping causes this RegExp to return to normal performance: /<([A-Za-z_:]|[^\x00-\x7F])([^<>"']+)$/ Note that I'm not a RegExp guru and this may be a wildly poor performing RegExp that wasn't actually working before but because of recent changes to Chrome is actually working now. In other words, I'm not sure whether Chrome 'fixed' something or 'broke' it ;-).
,
Sep 18 2017
Thank you for providing more feedback. Adding requester "pbommana@chromium.org" to the cc list and removing "Needs-Feedback" label. For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot
,
Sep 18 2017
The first RegExp takes 5 seconds to run in all Chrome versions I tested in Windows (23, 37, 42, 54, 57, 60, 62). Python didn't complete at all (my patience ran out first).
,
Sep 19 2017
Tested the issue on the reported version 61.0.3163.91 and on latest canary 63.0.3219.0 with the mentioned steps below on Ubuntu 14.04, Windows, Mac 10.12.6. 1. Downloaded the attached html file and clicked on Perform Slow RegExp. 2. It's taking 5500+ ms. Same is observed on M50-50.0.2624.0 as well and 3.Checked in Task manager When clicked on Perform Slow RegExp, CPU is showing 100% usage for that instance. Since, this is a Non-Regression issue seen from M50-50.0.2624.0, marking it as untriaged.
,
Sep 19 2017
FYI, here's more data from other browser platforms: Firefox Nightly (57.0a1 (2017-09-19) (64-bit)): Slow RegExp: 30844ms Fast RegExp: 0ms Firefox stopped twice with their version of the 'script running too long' message. I proceeded both times, but that might affect the time above by 1000-2000ms. Safari (Version 10.1.2 (12603.3.8)): Slow RegExp: 39ms Fast RegExp: 0ms
,
Sep 20 2017
Routing to V8 team.
,
Sep 28 2017
,
Sep 28 2017
Looks like catastrophic backtracking to me. Jakob, please confirm.
,
Oct 9 2017
,
Nov 9 2017
Sorry for the delay, this somehow got lost. It's indeed exponential backtracking due to repetition within and without the final group: ([^<>"']+)* |
||||||||
►
Sign in to add a comment |
||||||||
Comment 1 by pbomm...@chromium.org
, Sep 18 2017Components: -Blink Blink>JavaScript
Labels: Needs-Triage-M61 Needs-Feedback