antlr4 icon indicating copy to clipboard operation
antlr4 copied to clipboard

Published 20 hours ago • verified publisher icon antlr

Constant folding for Python and other runtimes

Open KvanTTT opened this issue 2 years ago • 7 comments

@SimonStPeter I've created a benchmark with respective grammar and have got the following result:

no_const_folding: 2010734 ns
const_folding: 907140 ns
ratio: 0.4511

I haven't tested on real grammars, but It's already signficant improvement, more 2x faster and it should be considered. Also, resulting file > 20 % less than the file with not folded constants.

There is no improvement in speed for JavaScript.

fixes #3698, fixes #3699

@parrt I suggest using constant folding for all runtimes because:

  • It reduces the size of generated parsers (more than 20% as I've checked for Python and JavaScript)
  • It eliminates very long lines that are hard to read by human and text editors. Just compare (there are a lot of similar lines for SQL parsers):
    • Current: if not(((((_la - 1)) & ~0x3f) == 0 and ((1 << (_la - 1)) & ((1 << (PParser.T0 - 1)) | (1 << (PParser.T1 - 1)) | (1 << (PParser.T2 - 1)) | (1 << (PParser.T3 - 1)) | (1 << (PParser.T4 - 1)) | (1 << (PParser.T5 - 1)) | (1 << (PParser.T6 - 1)) | (1 << (PParser.T7 - 1)) | (1 << (PParser.T8 - 1)) | (1 << (PParser.T9 - 1)) | (1 << (PParser.T10 - 1)) | (1 << (PParser.T11 - 1)) | (1 << (PParser.T12 - 1)) | (1 << (PParser.T13 - 1)) | (1 << (PParser.T14 - 1)) | (1 << (PParser.T15 - 1)) | (1 << (PParser.T16 - 1)) | (1 << (PParser.T17 - 1)) | (1 << (PParser.T18 - 1)) | (1 << (PParser.T19 - 1)) | (1 << (PParser.T20 - 1)) | (1 << (PParser.T21 - 1)) | (1 << (PParser.T22 - 1)) | (1 << (PParser.T23 - 1)) | (1 << (PParser.T24 - 1)) | (1 << (PParser.T25 - 1)) | (1 << (PParser.T26 - 1)) | (1 << (PParser.T27 - 1)) | (1 << (PParser.T28 - 1)) | (1 << (PParser.T29 - 1)) | (1 << (PParser.T30 - 1)) | (1 << (PParser.T31 - 1)) | (1 << (PParser.T32 - 1)) | (1 << (PParser.T33 - 1)) | (1 << (PParser.T34 - 1)) | (1 << (PParser.T35 - 1)) | (1 << (PParser.T36 - 1)) | (1 << (PParser.T37 - 1)) | (1 << (PParser.T38 - 1)) | (1 << (PParser.T39 - 1)) | (1 << (PParser.T40 - 1)) | (1 << (PParser.T41 - 1)) | (1 << (PParser.T42 - 1)) | (1 << (PParser.T43 - 1)) | (1 << (PParser.T44 - 1)) | (1 << (PParser.T45 - 1)) | (1 << (PParser.T46 - 1)) | (1 << (PParser.T47 - 1)) | (1 << (PParser.T48 - 1)) | (1 << (PParser.T49 - 1)) | (1 << (PParser.T50 - 1)) | (1 << (PParser.T51 - 1)) | (1 << (PParser.T52 - 1)) | (1 << (PParser.T53 - 1)) | (1 << (PParser.T54 - 1)) | (1 << (PParser.T55 - 1)) | (1 << (PParser.T56 - 1)) | (1 << (PParser.T57 - 1)) | (1 << (PParser.T58 - 1)) | (1 << (PParser.T59 - 1)) | (1 << (PParser.T60 - 1)) | (1 << (PParser.T61 - 1)) | (1 << (PParser.T62 - 1)) | (1 << (PParser.T63 - 1)))) != 0)):
    • Folded: if not((((_la - 1) & ~0x3f) == 0 and (1 << (_la - 1)) & -1) != 0):
  • Actually such expressions almost don't clarity how parser works in debug mode (if it's important).
  • It improves compilation speed (for compilable languages) or interpretation performance (for dynamic languages such as Python or JavaScript)

KvanTTT avatar May 07 '22 20:05 KvanTTT

CI improvement for Python: 12s vs >13s vs (>10%)

KvanTTT avatar May 07 '22 20:05 KvanTTT

Looks cool. I'll check as soon as I can.

parrt avatar May 07 '22 20:05 parrt

Good stuff. I'd be really interested to see how it works on a large grammar. If you've fixed the python perf problem that would be Most Excellent Indeed. Fingers crossed.

cheers

jan

On 07/05/2022 21:02, Ivan Kochurkin wrote:

@SimonStPeter https://github.com/SimonStPeter I've created a bechmark https://github.com/KvanTTT/AntlrBenchmarks/blob/master/ConstantFoldingBenchmark/checkParsers.py with respective grammar and have got the following result:

|no_const_folding: 2010734 ns const_folding: 907140 ns ratio: 0.4511 |

I haven't tested on real grammars but It's already signficant improvement, more 2x faster and it should be considered. Also, resulting file > 20 % less than the file with not folded constants.

There is no improvement in speed for JavaScript.

fixes #3698 https://github.com/antlr/antlr4/issues/3698, fixes #3699 https://github.com/antlr/antlr4/issues/3699

@parrt https://github.com/parrt I suggest use constant folding for all runtimes because:

  • It reduces the size of generated parsers (more than 20% as I've checked for Python and JavaScript)
  • It eliminates very long lines that are hard to read by human and text editors. Just compare: o Current: |if not(((((_la - 1)) & ~0x3f) == 0 and ((1 << (_la - 1)) & ((1 << (PParser.T0 - 1)) | (1 << (PParser.T1 - 1)) | (1 << (PParser.T2 - 1)) | (1 << (PParser.T3 - 1)) | (1 << (PParser.T4 - 1)) | (1 << (PParser.T5 - 1)) | (1 << (PParser.T6 - 1)) | (1 << (PParser.T7 - 1)) | (1 << (PParser.T8 - 1)) | (1 << (PParser.T9 - 1)) | (1 << (PParser.T10 - 1)) | (1 << (PParser.T11 - 1)) | (1 << (PParser.T12 - 1)) | (1 << (PParser.T13 - 1)) | (1 << (PParser.T14 - 1)) | (1 << (PParser.T15 - 1)) | (1 << (PParser.T16 - 1)) | (1 << (PParser.T17 - 1)) | (1 << (PParser.T18 - 1)) | (1 << (PParser.T19 - 1)) | (1 << (PParser.T20 - 1)) | (1 << (PParser.T21 - 1)) | (1 << (PParser.T22 - 1)) | (1 << (PParser.T23 - 1)) | (1 << (PParser.T24 - 1)) | (1 << (PParser.T25 - 1)) | (1 << (PParser.T26 - 1)) | (1 << (PParser.T27 - 1)) | (1 << (PParser.T28 - 1)) | (1 << (PParser.T29 - 1)) | (1 << (PParser.T30 - 1)) | (1 << (PParser.T31 - 1)) | (1 << (PParser.T32 - 1)) | (1 << (PParser.T33 - 1)) | (1 << (PParser.T34 - 1)) | (1 << (PParser.T35 - 1)) | (1 << (PParser.T36 - 1)) | (1 << (PParser.T37 - 1)) | (1 << (PParser.T38 - 1)) | (1 << (PParser.T39 - 1)) | (1 << (PParser.T40 - 1)) | (1 << (PParser.T41 - 1)) | (1 << (PParser.T42 - 1)) | (1 << (PParser.T43 - 1)) | (1 << (PParser.T44 - 1)) | (1 << (PParser.T45 - 1)) | (1 << (PParser.T46 - 1)) | (1 << (PParser.T47 - 1)) | (1 << (PParser.T48 - 1)) | (1 << (PParser.T49 - 1)) | (1 << (PParser.T50 - 1)) | (1 << (PParser.T51 - 1)) | (1 << (PParser.T52 - 1)) | (1 << (PParser.T53 - 1)) | (1 << (PParser.T54 - 1)) | (1 << (PParser.T55 - 1)) | (1 << (PParser.T56 - 1)) | (1 << (PParser.T57 - 1)) | (1 << (PParser.T58 - 1)) | (1 << (PParser.T59 - 1)) | (1 << (PParser.T60 - 1)) | (1 << (PParser.T61 - 1)) | (1 << (PParser.T62 - 1)) | (1 << (PParser.T63 - 1)))) != 0)):| o Folded: |if not((((_la - 1) & ~0x3f) == 0 and (1 << (_la - 1)) & -1) != 0):|
  • Actually such expressions don't clarity how parser works in debug mode.
  • It improves compilation speed (for compilable languages) or interpretation performance (for Python)
    You can view, comment on, or merge this pull request online at:

https://github.com/antlr/antlr4/pull/3701 https://github.com/antlr/antlr4/pull/3701

    Commit Summary

(5 files https://github.com/antlr/antlr4/pull/3701/files)

— Reply to this email directly, view it on GitHub https://github.com/antlr/antlr4/pull/3701, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNF57LFP2NPDHRHRTYMKZTVI3D4VANCNFSM5VK3FXWQ. You are receiving this because you were mentioned.Message ID: @.***>

SimonStPeter avatar May 07 '22 21:05 SimonStPeter

Also I've completed the following:

  • Go: getInlineTestSetWordSize 32 -> 64 (go actually supports long integers)
  • Dart: get rid of BigInt
  • Swift: optimize TestSetInline (also should improve performance)

KvanTTT avatar May 08 '22 15:05 KvanTTT

Should we look at this again after completing your other testing upgrades? @KvanTTT

parrt avatar Jun 25 '22 17:06 parrt

Yes, I think it makes sense to get rid of very long lines in generated sources.

KvanTTT avatar Jun 25 '22 17:06 KvanTTT

Eventually, it's ready for review.

KvanTTT avatar Jul 03 '22 18:07 KvanTTT

@parrt any chance it will be merged?

KvanTTT avatar Aug 23 '22 18:08 KvanTTT

Happy to merge once you add the parentheses and change the name of the method! thanks!

parrt avatar Aug 27 '22 20:08 parrt

Eventually done. Some fails on C# tests, but are unrelated.

KvanTTT avatar Aug 31 '22 00:08 KvanTTT

Eventually done. Some fails on C# tests, but are unrelated.

rerunning C# now...

parrt avatar Aug 31 '22 20:08 parrt

Nice work! I'll merge it in and then verify the Java gen'd code still looks OK haha

parrt avatar Aug 31 '22 21:08 parrt

It's arguably being 'evaluated' so perhaps 'folding' -> 'evaluation'.

Also these are constants, but more precisely I'd say they are literal constants, or literals for short. So maybe 'constant' -> 'literal'

jan

On 28/08/2022 12:23, Ivan Kochurkin wrote:

@.**** commented on this pull request.

In tool/src/org/antlr/v4/codegen/model/Choice.java https://github.com/antlr/antlr4/pull/3701#discussion_r956711633:

 	for (IntervalSet s : altLookSets) {

  • 	altLook.add(factory.getGenerator().getTarget().getTokenTypesAsTargetLabels(factory.getGrammar(), s.toArray()));

  • 	if (target.supportsConstants()) {

Not sure it's correct naming. Python supports constant folding, i.e. the following expression

|(1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6) | \ (1 << 7) | (1 << 8) | (1 << 9) | (1 << 10) | (1 << 11) | (1 << 12) | \ (1 << 13) | (1 << 14) | (1 << 15) | (1 << 16) |

is being folded to constant |0xFFFF|. But Python doesn't support constant propagation since Python is unable to determine whether a variable is constant or not.

— Reply to this email directly, view it on GitHub https://github.com/antlr/antlr4/pull/3701#discussion_r956711633, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNF57NDAG5JGNVYEKXFX53V3ND4BANCNFSM5VK3FXWQ. You are receiving this because you were mentioned.Message ID: @.***>

SimonStPeter avatar Oct 11 '22 07:10 SimonStPeter

@KvanTTT I have a warning from C++ where stuff like:

((_la & ~ 0x3fULL) == 0) &&
      ((1ULL << _la) & -41056) != 0 || (((_la - 64) & ~ 0x3fULL) == 0) &&
      ((1ULL << (_la - 64)) & 32767) != 0

gets warnings

$ clang++ -Werror,-Wlogical-op-parentheses t.cc
warning: unknown -Werror warning specifier: '-Werror,-Wlogical-op-parentheses' [-Wunknown-warning-option]
1 warning generated.
parrt-macbookpro2:tmp parrt$ clang++ -Werror -Wlogical-op-parentheses t.cc
t.cc:3:34: error: '&&' within '||' [-Werror,-Wlogical-op-parentheses]
    if (((_la & ~ 0x3fULL) == 0) &&
        ~~~~~~~~~~~~~~~~~~~~~~~~~^~
t.cc:3:34: note: place parentheses around the '&&' expression to silence this warning
    if (((_la & ~ 0x3fULL) == 0) &&
                                 ^

The -41056 makes me nervous. Are you sure that word size is portably correct, given the ULL usage?

parrt avatar Oct 22 '22 01:10 parrt

Seems like C++ would change this template to wrap in parens:

bitsetBitfieldComparison(s, bits) ::= <<
<testShiftInRange({<offsetShift(s.varName, bits.shift)>})> &&
  ((1ULL \<\< <offsetShift(s.varName, bits.shift)>) & <bits.calculated>) != 0
>>

Some companies flip this warning to an error.

parrt avatar Oct 22 '22 01:10 parrt