Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(529)

Issue 92290043: code review 92290043: regexp/syntax: don't waste time checking for one pass a... (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
9 years, 10 months ago by r
Modified:
9 years, 10 months ago
Reviewers:
gobot, rsc, dfc, josharian
CC:
rsc, golang-codereviews
Visibility:
Public.

Description

regexp/syntax: don't waste time checking for one pass algorithm The code recurs very deeply in cases like (?:x{1,1000}){1,1000} Since if much time is spent checking whether one pass is possible, it's not worth doing at all, a simple fix is proposed: Stop if the check takes too long. To do this, we simply avoid machines with >1000 instructions. Benchmarks show a percent or less change either way, effectively zero. Fixes issue 7608.

Patch Set 1 #

Total comments: 1

Patch Set 2 : diff -r b9c40afbd66c https://code.google.com/p/go #

Patch Set 3 : diff -r b9c40afbd66c https://code.google.com/p/go #

Unified diffs Side-by-side diffs Delta from patch set Stats (+15 lines, -0 lines) Patch
M src/pkg/regexp/all_test.go View 6 chunks +10 lines, -0 lines 0 comments Download
M src/pkg/regexp/syntax/prog.go View 1 1 chunk +5 lines, -0 lines 0 comments Download

Messages

Total messages: 9
r
Hello rsc (cc: golang-codereviews@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go
9 years, 10 months ago (2014-05-12 22:00:49 UTC) #1
rsc
https://codereview.appspot.com/92290043/diff/1/src/pkg/regexp/syntax/prog.go File src/pkg/regexp/syntax/prog.go (right): https://codereview.appspot.com/92290043/diff/1/src/pkg/regexp/syntax/prog.go#newcode626 src/pkg/regexp/syntax/prog.go:626: checkDepth := 0 // Recursion depth in calls to ...
9 years, 10 months ago (2014-05-12 23:27:10 UTC) #2
r
Hello rsc@golang.org (cc: golang-codereviews@googlegroups.com), Please take another look.
9 years, 10 months ago (2014-05-13 19:14:21 UTC) #3
rsc
LGTM
9 years, 10 months ago (2014-05-13 19:17:19 UTC) #4
r
*** Submitted as https://code.google.com/p/go/source/detail?r=6e10ddc0bbc2 *** regexp/syntax: don't waste time checking for one pass algorithm The ...
9 years, 10 months ago (2014-05-13 19:17:52 UTC) #5
gobot
This CL appears to have broken the freebsd-arm-cheney builder. See http://build.golang.org/log/d5c9f3f9d7bdbc6d4c4fccd901ca5dff86570101
9 years, 10 months ago (2014-05-13 20:50:57 UTC) #6
r
I think the machine is just too slow. The stuff I added should have sped ...
9 years, 10 months ago (2014-05-13 21:01:53 UTC) #7
josharian
> I think the machine is just too slow. The stuff I added should have ...
9 years, 10 months ago (2014-05-13 21:04:32 UTC) #8
dfc
9 years, 10 months ago (2014-05-14 01:02:03 UTC) #9
I'm really sorry about the freebsd/arm builder. It is the fastest I
have available as hardware support for freebsd/arm is very spotty.

On Wed, May 14, 2014 at 7:04 AM, Josh Bleecher Snyder
<josharian@gmail.com> wrote:
>> I think the machine is just too slow. The stuff I added should have
>> sped it up as much as it down, by deleting the expensive evaluation of
>> an optimization.
>
> Yep. The same machine timed out not long ago around the same spot:
> http://build.golang.org/log/4387dd65514722a46b2811e1e4d566b810f6db01.
>
> --
> You received this message because you are subscribed to the Google Groups
"golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b