The parser does not like long boolean expressions #3634

MDoerner · 2017-12-21T22:28:15Z

The problem is that the parser slows down to a crawl in the presence of long boolean expressions. The runtime seems to be roughly exponential in the number of concatenated expressions.

Examples:

From #3556

If preserveUserColor = True _
   And rCell.row > 6 _
   And Not cColor = matColor("blue", 50) _
   And Not cColor = matColor("blue", 100) _
   And Not cColor = matColor("blue", 200) _
   And Not cColor = matColor("blue", 300) _
   And Not cColor = matColor("blue", 400) _
   And Not cColor = matColor("blue", 500) _
   And Not cColor = matColor("blue", 600) _
   And Not cColor = matColor("blue", 700) _
   And Not cColor = matColor("blue", 800) _
   And Not cColor = matColor("blue", 900) _
   And Not cColor = matColor("amber", 100) _
   And Not cColor = matColor("amber", 200) _
   And Not cColor = matColor("lime", 100) _
   And Not cColor = matColor("lime", 200) _
   And Not cColor = matColor("bluegrey", 100) _
   And Not cColor = matColor("bluegrey", 200) _
   And Not cColor = matColor("deeppurple", 100) _
   And Not cColor = matColor("deeppurple", 200) _
   And Not cColor = matColor("yellow", 200) _
   And Not cColor = matColor("teal", 200) _
Then GoTo skiprCellFor

From chat:

Dim Ignore As Boolean
Ignore = TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
TypeOf Me Is Class1

My guess is that the parser is constantly guessing the wrong way to proceed. Reordering the subrules of expression might help. Upgrading Antlr might help as well, since the left-recursion resollution changed. (This would make changes to the ordering necesary anyway in order to get the SLL parser to work again.)

ref #2498

parrt · 2017-12-22T00:02:19Z

What is the target language? C#? Note that technically ALL(*) is not linear and large expressions can hit a landmine, often with big diffs between target runtime speed.

Hosch250 · 2017-12-22T00:03:55Z

Yes, we are a C# project. We are parsing VBA code.

retailcoder · 2017-12-22T00:06:42Z

@parrt correct. Are we doomed? Our grammar is here if you want to have a look - it's based on the VBA language specifications: https://github.com/rubberduck-vba/Rubberduck/blob/next/Rubberduck.Parsing/Grammar/VBAParser.g4

Hosch250 · 2017-12-22T00:07:08Z

Also, feel free to visit our warroom here: https://chat.stackexchange.com/rooms/14929/vba-rubberducking

parrt · 2017-12-22T00:10:46Z

Not doomed but might have to convert https://github.com/rubberduck-vba/Rubberduck/blob/next/Rubberduck.Parsing/Grammar/VBAParser.g4#L588 to avoid left-recursion. Are you using latest antlr 4.7.1?

retailcoder · 2017-12-22T00:32:53Z

@parrt still on v4.3... seems there have been a number of breaking changes we're struggling with. Conversion is in progress though. Not sure avoiding recursion is possible with that one (not to mention all the implications in our resolver code).. hopefully 4.7 works better with it?

parrt · 2017-12-22T00:46:13Z

There have been important optimizations in later version so definitely upgrade

…

Sent from my iPhone

On Dec 21, 2017, at 4:32 PM, Mathieu Guindon ***@***.***> wrote: @parrt still on v4.3... seems there have been a number of breaking changes we're struggling with. Conversion is in progress though. Not sure avoiding recursion is possible with that one (not to mention all the implications in our resolver code).. hopefully 4.7 works better with it? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

ThunderFrame · 2017-12-22T01:57:13Z

Some testing...

I'm getting odd behavior with refresh times - it's almost like ANTLR is caching a parsing strategy... The first parse takes some time, but with small edits, the subsequent parse is very fast.
I'm not sure that it's the multiple boolean conditions per se, but rather the complexity of the expressions

This parses/resolves in 4 seconds:

Sub test()
  Debug.Print False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False And _
              False
End Sub

Whereas, this resolves in 12 seconds:

Sub test()
  Debug.Print Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False And _
              Not False
End Sub

But, if I edit that code to substitute False for True, and reparse, and then revert True to False and reparse, it resolves in 4 seconds. It's like ANTLR has cached the parsing strategy for this statement. If I add an extra condition and reparse, the parse time shoots up again, and then if I remove the extra condition and reparse, the parse time is low again, which suggests that the cached optimizations are independent of individual reparses?

And this is still resolving after 10 minutes...

Sub test()
  Debug.Print Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42 And _
              Not 42 = 42
End Sub

parrt · 2017-12-22T02:15:31Z

Definitely caches partial parsing results so that similar parses will get the benefit of reusing the analysis. It warms up just like a jit.

…

Sent from my iPhone

On Dec 21, 2017, at 5:57 PM, ThunderFrame ***@***.***> wrote: Some testing... I'm getting odd behavior with refresh times - it's almost like ANTLR is caching a parsing strategy... The first parse takes some time, but with small edits, the subsequent parse is very fast. I'm not sure that it's the multiple boolean conditions per se, but rather the complexity of the expressions This parses/resolves in 4 seconds: Sub test() Debug.Print False And _ False And _ False And _ False And _ False And _ False And _ False And _ False And _ False And _ False And _ False And _ False And _ False End Sub Whereas, this resolves in 12 seconds: Sub test() Debug.Print Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False And _ Not False End Sub But, if I edit that code to substitute False for True, and reparse, and then revert True to False and reparse, it resolves in 4 seconds. It's like ANTLR has cached the parsing strategy for this statement. If I add an extra condition and reparse, the parse time shoots up again, and then if I remove the extra condition and reparse, the parse time is low again, which suggests that the cached optimizations are independent of individual reparses? And this is still resolving after 10 minutes... Sub test() Debug.Print Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 And _ Not 42 = 42 End Sub — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

parrt · 2017-12-22T16:09:16Z

Are you using two-stage parsing? SLL then full ALL only if SLL fails?

retailcoder · 2017-12-22T16:11:35Z

@parrt Yup. We attempt a quick parse first, and fallback to the slower prediction mode if the initial pass throws a parse exception.

parrt · 2017-12-22T16:12:15Z

okidoki. we had a big optimization for left-recursive expressions in a recent release, so definitely upgrade.

Vogel612 · 2017-12-22T16:13:55Z

yes. We first attempt to parse with SLL to get the performance boost. In something like <= 5% of cases (from logfiles posted in issues) SLL will fail, and we retry parsing the whole module with LL prediction. See VBAModuleParser for code

Vogel612 · 2017-12-22T16:16:29Z

note that we're running multiple parse passes that way, because Attributes are only available when exporting a module. We need the line numbers to match with the displayed code though, so there's two runs for each module.

Additionally we handle compilation directives before each of these runs.

MDoerner · 2017-12-22T23:02:09Z

As @Vogel612 already showed above, the complexity of the boolean expression seems to be an important factor. I think the basic problem here is that the parser has a hard time sorting out where the operands of And and Or begin and end. In the presence of parentheses, the parse is much faster.

Parses in about 1s:

Public Sub Test()
    Dim Ignore As Boolean
    Ignore = TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1) And _
    (TypeOf Me Is Class1) And (TypeOf Me Is Class1)
End Sub

Parses in about 380s:

Public Sub Test()
    Dim Ignore As Boolean
    Ignore = TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    TypeOf Me Is Class1 And TypeOf Me Is Class1 And _
    TypeOf Me Is Class1 And TypeOf Me Is Class1
End Sub

MDoerner · 2018-01-29T23:22:31Z

I can confirm that this has been fixed by the move to Antlr 4.6.4 (PR #3715).

Now the parse for the examples above is basically instant.

Vogel612 added critical Marks a bug as a must-fix, showstopper issue enhancement Feature requests, or enhancements to existing features. Ideas. Anything within the project's scope. performance labels Dec 21, 2017

MDoerner closed this as completed Jan 29, 2018

MDoerner mentioned this issue Jan 29, 2018

Parser errors aren't consistently reported as such #3556

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

The parser does not like long boolean expressions #3634

The parser does not like long boolean expressions #3634

MDoerner commented Dec 21, 2017

parrt commented Dec 22, 2017 •

edited

Hosch250 commented Dec 22, 2017

retailcoder commented Dec 22, 2017

Hosch250 commented Dec 22, 2017

parrt commented Dec 22, 2017

retailcoder commented Dec 22, 2017

parrt commented Dec 22, 2017 via email

ThunderFrame commented Dec 22, 2017

parrt commented Dec 22, 2017 via email

parrt commented Dec 22, 2017

retailcoder commented Dec 22, 2017

parrt commented Dec 22, 2017

Vogel612 commented Dec 22, 2017

Vogel612 commented Dec 22, 2017

MDoerner commented Dec 22, 2017

MDoerner commented Jan 29, 2018

The parser does not like long boolean expressions #3634

The parser does not like long boolean expressions #3634

Comments

MDoerner commented Dec 21, 2017

parrt commented Dec 22, 2017 • edited

Hosch250 commented Dec 22, 2017

retailcoder commented Dec 22, 2017

Hosch250 commented Dec 22, 2017

parrt commented Dec 22, 2017

retailcoder commented Dec 22, 2017

parrt commented Dec 22, 2017 via email

ThunderFrame commented Dec 22, 2017

parrt commented Dec 22, 2017 via email

parrt commented Dec 22, 2017

retailcoder commented Dec 22, 2017

parrt commented Dec 22, 2017

Vogel612 commented Dec 22, 2017

Vogel612 commented Dec 22, 2017

MDoerner commented Dec 22, 2017

MDoerner commented Jan 29, 2018

parrt commented Dec 22, 2017 •

edited