[antlr-interest] ANTLR 3.1 - Serious performance downgrade

[Benjamin Niemann]

Hi Michael,

there has been a major change to the implementation of the
TokenRewriteStream. I quick look at the code suggests, that
TokenRewriteStream.reduceToSingleOperationPerIndex() is O(n^2), where
n is the number of rewrites - and it is called for each toString call.
Did you do some profiling to find the method that takes most of the
time?

-Ben


On Sun, Aug 17, 2008 at 9:52 PM, Dr. Michael Gerz
<michael.gerz at teststep.org> wrote:
> Dear ANTLR developers, hi Terence,
>
> when upgrading to the latest and greatest ANTLR 3.1, we noticed a
> significant performance downgrade that makes it almost unuseable for our
> purposes.
>
> In our system, we use a grammar that is a modified version of the 'Java'
> grammar given on the ANTLR web page, with some minor test-specific
> extensions and a few simplifications. By means of a ANTLR tree grammar
> (using StringTemplate), we transform these extensions to plain Java.
>
> In the past, the transformation times were neglectable (within the range of
> a few seconds). However, with ANTLR 3.1 final, converting a 679KB input file
> into a 735KB Java file takes about 10 minutes!
>
> I tried to identify the problem and came up with the following conclusions:
>
> * The performance slowdown happens in our tree grammar. The ANTLR
>  parser and lexer are pretty fast.
> * The showstopper was introduced sometime between intermediate release
>  antlr-2008-05-25.11.tar.gz (fast) and antlr-2008-08-03.16.tar.gz (slow).
> * The performance seems to decrease exponentially with the input size.
>
> Below please find the header of our tree grammar and the method that invokes
> it.
>
> Does anybody have any idea why ANTLR has become so extremely slow just
> before its final release? I am sure that this must be a general problem that
> also affects other people. Is there anything else that you need to analyse
> the problem?
>
> Thanks in advance!
>
> Michael
>
>
>
> ++++++ Snippet from JavaCodeGenerator.g ++++++
>
> tree grammar JavaCodeGenerator;
>
> options {
>       k = 1;
>       ASTLabelType = CommonTree;
>       tokenVocab = TestLang;
>       output = template;
>       rewrite = true;
>   }
>
> ... some scope definitions ...
>
> @members {
>
>   ... some member definitions ...
> }
>
> @header {
>   package de.fgan.fkie.sylt.testsystem.testlang;
>
>   ... some import declarations ...
> }
>
> ... the start rule ... where needed, string templates are used ...
>
> compilationUnit
>   :    idecls+=importDeclaration*
>       (    tsd=testsuiteDeclaration
>           -> template(ids={$idecls}, tsd={$tsd.text})
> <<
> package de.fgan.fkie.sylt.test;
>
> import de.fgan.fkie.sylt.testsystem.server.testrunner.TestRunner;
>
> <ids>
> <tsd>
>>>
>       |    tgd=testgroupDeclaration
>           -> template(ids={$idecls}, imp={getImportStatements()},
> tgd={$tgd.text})
> <<
> package de.fgan.fkie.sylt.test;
>
> <imp>
>
> <ids>
> <tgd>
>>>
>       )
>   ;
>
> ... and so on ...
>
>
> ++++++ Invocation of JavaCodeGenerator ++++++
>
>
>   private static void saveAsJava(String testGroupName, String script) {
>       ANTLRInputStream input;
>       try {
>           input = new ANTLRInputStream(new
> ByteArrayInputStream(script.getBytes()));
>           TestLangLexer lexer = new TestLangLexer(input);
>           TokenRewriteStream tokens = new TokenRewriteStream(lexer);
>           TestLangParser parser = new TestLangParser(tokens);
>           TestLangParser.compilationUnit_return r;
>           try {
>               r = parser.compilationUnit();
>           } catch (RecognitionException e) {
>               throw new RuntimeException("Error while parsing " +
> testGroupName + ":"
>                       + parser.getErrorMessage(e,
> TestLangParser.tokenNames));
>           }
>           CommonTree t = (CommonTree) r.getTree();
>           CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
>           nodes.setTokenStream(tokens);
>           JavaCodeGenerator codeGen = new JavaCodeGenerator(nodes);
>
>           JavaCodeGenerator.compilationUnit_return r2;
>           try {
>               r2 = codeGen.compilationUnit();  /// SLOOOOOW, SOOO SLOOOOOW
>           } catch (RecognitionException e) {
>               throw new RuntimeException("Error while parsing " +
> testGroupName + ":"
>                       + codeGen.getErrorMessage(e,
> JavaCodeGenerator.tokenNames));
>           }
>
>           File f = new File(ServerProperties.SERVER_TEST_CLASS_DIRECTORY +
> File.separator
>                   + testGroupName + ".java");
>           FileWriter out = new FileWriter(f);
>           out.write(r2.st.toString());
>           out.close();
>
>       } catch (IOException e) {
>           throw new RuntimeException("Error while reading/writing " +
> testGroupName + ":"
>                   + e.getMessage(), e);
>       }
>   }
>
>
>
>