Another poor performance about expression parsing

[qwerppoo]

I'm using ANTLR-4.4 with a grammar file modified from sqlite.g4,and find some complex expressions cost too much time to parse.And then I found issue#192 .

That grammar file works fast with the antlr version I'm using now.But when I add some rules I used in my grammar file,it get slow down.

To make the issue simple,the grammar I use is just like this:

grammar expr;

expr: ID
    | 'not' expr
    | expr 'and' expr
    | expr 'or' expr
    | expr 'between' expr 'and' expr
    ;

ID: [a-zA-Z_][a-zA-Z_0-9]*;
WS: [ \t\n\r\f]+ -> skip;
ERROR: .;

and the sample file is just same like

not X1 and not X2 and not X3 and not X4 and not X5 and not X6 and not X7 and not X8 and not X9 and not X10 and not X11 and not X12 or
    X1 and not X2 and not X3 and not X4 and not X5 and not X6 and not X7 and not X8 and not X9 and not X10 and not X11 and not X12 or
not X1 and     X2 and not X3 and not X4 and not X5 and not X6 and not X7 and not X8 and not X9 and not X10 and not X11 and not X12

I tried this with the antlr plugin in IDEA,just 3 lines of the expressions will make the parsing time unacceptable.

[KvanTTT]

Your should use two-stage strategy as decribed in pointed issue: #192 (comment)
It is solve your problem with slow parsing.

[sharwell]

Two stage parsing does resolve the issue when the input is correct, but error recovery results in a fallback to the second stage where it goes slow again.

The solution to this is making every precedence rule transition in the prediction algorithm follow a precedence-dependent edge, as opposed to the current behavior where precedence is only considered for the DFA start state. It would be a very complicated change to the way the DFA cache works, but obviously be a big win in some real scenarios.

[KvanTTT]

Anyway, for this grammar performance is good with two-stage parsing even for input file with errors (Maybe EOF or some input market missing in this grammar).

[WolfgangFahl]

A JUnit test with a similar grammar shows the following behavior for adding "AND" clauses in a loop and parsing ever growing AND expressions:

@Test
  public void testNestedAndCode() throws Exception {
    // RuleLanguageParser.ONE_STAGE=false;
    String andClause="VALUE=0";
    for (int i=1;i<=12;i++) {
      long start = System.currentTimeMillis();
      andClause+="\n AND VALUE"+i+"=0\n";
      doTestRule("if\n" + andClause+
       "\nendif");     
      long stop = System.currentTimeMillis();
       System.out.println(String.format("%3d %4d msecs",i,stop - start));
    }
  }

With One Stage Parsing:

  1   418 msecs
  2    33 msecs
  3    39 msecs
  4    75 msecs
  5   189 msecs
  6   424 msecs
  7   943 msecs
  8   869 msecs
  9  2714 msecs
 10  6346 msecs
 11 14929 msecs
 12 39246 msecs

With Two Stage Parsing:

  1   362 msecs
  2    16 msecs
  3    37 msecs
  4    63 msecs
  5   151 msecs
  6   396 msecs
  7   623 msecs
  8  1039 msecs
  9  3154 msecs
 10  6924 msecs
 11 18117 msecs
 12 47501 msecs

In both cases the parsing time roughly doubles with every additional "AND". Since this is obviously inacceptable it would be good to have a solution or workaround.

I have now added a JUnit test to my environment that fails if the average performance ratio for adding an additional "AND" is higher than 1.2. I'd rather see a linear behavior, though.

@Test
  public void testNestedAndCode() throws Exception {
    // RuleLanguageParser.ONE_STAGE=false;
    String andClause="VALUE=0";
    long prevduration=0;
    double ratiosum=0;
    int ratiocount=0;
    for (int i=1;i<=6;i++) {
      long start = System.currentTimeMillis();
      andClause+="\n AND VALUE"+i+"=0\n";
      doTestRule("if\n" + andClause+
       "\nendif");     
      long stop = System.currentTimeMillis();
      long duration=stop-start;
      System.out.println(String.format("%3d %5d msecs",i,duration));
      if (i>2) {
        double ratio=duration/prevduration;
        ratiosum+=ratio;
        ratiocount++;
      }
      prevduration=duration;
    }
    double averageRatio=ratiosum/ratiocount;
    System.out.println(String.format("ratio: %3.2f",averageRatio));
    assertTrue(averageRatio<1.2);
  }

[WolfgangFahl]

Here is a Junit Test for the grammar originally specified for this issue:

import static org.junit.Assert.*;

import java.io.IOException;

import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.junit.Test;

/**
 * Test the Issue 994 performance 
 * @author wf
 *
 */
public class TestIssue994 {
  boolean debug=false;


  /**
   * see https://github.com/antlr/antlr4/issues/994
   * @throws Exception
   */
    @Test
    public void testIssue994() throws Exception {
    String andClause="not X0";
    long prevduration=0;
    double ratiosum=0;
    int ratiocount=0;
    for (int i=1;i<=20;i++) {
      long start = System.currentTimeMillis();
      if (i%4==1) {
        andClause+=" or X"+i;
      } else {
        andClause+=" and not X"+i;
      }
      doTestExpr(andClause);     
      long stop = System.currentTimeMillis();
      long duration=stop-start;
      if (i>=2) {
        double ratio=duration*1.0/(prevduration*1.0);
        System.out.println(String.format("%3d %5d msecs %5.1f",i,duration,ratio));
        if (duration>25) {
          ratiosum+=ratio;
          ratiocount++;
        }
      }
      prevduration=duration;
    }
    double averageRatio=ratiosum/ratiocount;
    System.out.println(String.format("ratio: %3.2f",averageRatio));
    assertTrue("Performance issue https://github.com/antlr/antlr4/issues/994",averageRatio<1.2);

    }

    /**
     * do parse the given expression
     * @param andClause
     * @throws IOException
     */
  private void doTestExpr(String andClause) throws IOException {
    if (debug)
      System.out.println(andClause);
    ANTLRInputStream in = RuleLanguageParser.streamForText(andClause);
    exprLexer lexer = new exprLexer(in);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    exprParser parser = new exprParser(tokens);
    parser.expr();
  }

}

it has the following time behaviour:

len   time           ratio
  2    12 msecs   0,1
  3     4 msecs   0,3
  4     8 msecs   2,0
  5     8 msecs   1,0
  6     9 msecs   1,1
  7    11 msecs   1,2
  8    20 msecs   1,8
  9    31 msecs   1,6
 10    47 msecs   1,5
 11    73 msecs   1,6
 12   135 msecs   1,8
 13   230 msecs   1,7
 14   189 msecs   0,8
 15   203 msecs   1,1
 16   246 msecs   1,2
 17   452 msecs   1,8
 18   934 msecs   2,1
 19  1723 msecs   1,8
 20  2702 msecs   1,6
ratio: 1,55

[jimidle]

Performance tests that measure just a single iteration of anything are
usually not a good idea, especially in Java. You should re-jig this to
create the parser, then run say 2000 iterations and divide to get an
average. Really you should also measure the loop time itself and take that
off, but an empty loop may optimize out.

I don't dispute your thoughts but you may find that the performance
difference is not as much as you think.

Jim

On Mon, Apr 4, 2016 at 5:03 PM, Wolfgang Fahl notifications@github.com
wrote:

Here is a Junit Test for the grammar originally specified for this issue:

import static org.junit.Assert.;
import java.io.IOException;
import org.antlr.v4.runtime.ANTLRInputStream;import org.antlr.v4.runtime.CommonTokenStream;import org.junit.Test;
/* * Test the Issue 994 performance * @author wf * */public class TestIssue994 {
boolean debug=false;

/* * see #994 * @throws Exception _/
@test
public void testIssue994() throws Exception {
String andClause="not X0";
long prevduration=0;
double ratiosum=0;
int ratiocount=0;
for (int i=1;i<=20;i++) {
long start = System.currentTimeMillis();
if (i%4==1) {
andClause+=" or X"+i;
} else {
andClause+=" and not X"+i;
}
doTestExpr(andClause);
long stop = System.currentTimeMillis();
long duration=stop-start;
if (i>=2) {
double ratio=duration_1.0/(prevduration1.0);
System.out.println(String.format("%3d %5d msecs %5.1f",i,duration,ratio));
if (duration>25) {
ratiosum+=ratio;
ratiocount++;
}
}
prevduration=duration;
}
double averageRatio=ratiosum/ratiocount;
System.out.println(String.format("ratio: %3.2f",averageRatio));
assertTrue("Performance issue https://github.com/antlr/antlr4/issues/994",averageRatio<1.2);

}

/**     * do parse the given expression     * @param andClause     * @throws IOException     */

private void doTestExpr(String andClause) throws IOException {
if (debug)
System.out.println(andClause);
ANTLRInputStream in = RuleLanguageParser.streamForText(andClause);
exprLexer lexer = new exprLexer(in);
CommonTokenStream tokens = new CommonTokenStream(lexer);
exprParser parser = new exprParser(tokens);
parser.expr();
}

}

it has the following time behaviour:

2 12 msecs 0,1
3 4 msecs 0,3
4 8 msecs 2,0
5 8 msecs 1,0
6 9 msecs 1,1
7 11 msecs 1,2
8 20 msecs 1,8
9 31 msecs 1,6
10 47 msecs 1,5
11 73 msecs 1,6
12 135 msecs 1,8
13 230 msecs 1,7
14 189 msecs 0,8
15 203 msecs 1,1
16 246 msecs 1,2
17 452 msecs 1,8
18 934 msecs 2,1
19 1723 msecs 1,8
20 2702 msecs 1,6
ratio: 1,55

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#994 (comment)

[WolfgangFahl]

@jimidle - thank you for your comment. Please note that I stopped the loop at 20 on purpose. If you keep almost doubling the timing from there you will end up with 20 minutes parsing time after some 10 more loops and some 300 hours parsing time after additional 20 loops. Keep adding and you'll basically wait for ever. This is called exponential growth and should not happen.

Running this a few thousand iterations is prohibitive since I do not need a more precise result I need a different time behaviour see https://en.wikipedia.org/wiki/Big_O_notation

In the ANTLR techreport http://www.antlr.org/papers/allstar-techreport.pdf
you'll find the statement

ALL() is O(n_*4) in theory but consistently per- forms linearly on grammars used in practice, outperforming general strategies such as GLL and GLR by orders of magnitude._

The basis of this statement seems to be that the the two stage parsing approach as outlined in paragraph 3.2 Two-stage ALL(*) parsing is used.

This means the SLL and LL strategies have to be used one after another. It also means that you might have to adapt your grammar. The grammar of this Issue e.g. is fit for the two stage strategy. Unfortunately a bigger grammar I am currently analyzing is not and I still have to find out how to make it SLL - this is the reason why I posted my results here in the first place. One way to get my grammar more SLL like was to change the order of grammar rules putting possibly "longer" matches before shorter matches. E.g.

in_clause:
    field (IN field) * |
    field
   ;

is better than

in_clause:
    field |
    field (IN field) * 
   ;

[jimidle]

Youre rule can be just: