[antlr-interest] ANTLR 3.1 - Serious performance downgrade

[Dr. Michael Gerz]

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);
        }
    }