antlr4 vs handwritten parser : golang

[ashish...@gmail.com]

Hi
We are planning to use antlr4 in production. It's grammar is simple and precise. Thanks for the great work.
However, initial benchmarks are not encouraging.

Our language spec is a variant of GraphQL.http://graphql.org/

We started benchmarking from the simplest subset grammar.
Benchmarks :
dgraph/antlr4go/graphqlpm$ gotb -test.run=XXX -benchtime=2s -v
BenchmarkQuery/q1-4                 5000       1221967 ns/op
BenchmarkQuery/q2-4                 2000       1710850 ns/op
BenchmarkQuery/q3-4                 3000       1230518 ns/op
BenchmarkQuery/q4-4                 3000       1568564 ns/op
BenchmarkQuery/q5-4                 2000       1803392 ns/op
PASS
ok      github.com/dgraph-io/dgraph/antlr4go/graphqlpm    22.179s

We expected these numbers to be under 0.05 ms. They are currently around 1.5 ms.

Here are comparisons with handwritten parser over practical queries :
Benchmarks :
query$ gotb -test.run=XXX -benchtime=2s -v
BenchmarkQueryParse/spielberg:handwitten:-4               100000         46918 ns/op
BenchmarkQueryParse/spielberg:antlr:-4                          2000       1741364 ns/op
BenchmarkQueryParse/tomhanks:handwitten:-4              100000         25982 ns/op
BenchmarkQueryParse/tomhanks:antlr:-4                          2000       1654579 ns/op
BenchmarkQueryParse/nestedquery:handwritten:-4            30000         73053 ns/op
BenchmarkQueryParse/nestedquery:antlr:-4                       1000       3385005 ns/op
PASS
ok      github.com/dgraph-io/dgraph/query    21.922s

Antlr4 is around 40x slower.
Is this expected ? Or are we doing something wrong ?
How can we debug the performance bottleneck ?

Thanks
-Ashish Negi

[ashish...@gmail.com]

With some help from @KvanTTT on github, lexing is taking most of the time.

with only doing the lexing :
func runAntlrParser(q string, b *testing.B) {
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        input := antlr.NewInputStream(q)
        lexer := parser.NewGraphQLPMLexer(input)
        // for only lexer benchmark
        t := lexer.NextToken()
        for t.GetTokenType() != antlr.TokenEOF {
            t = lexer.NextToken()
        }
    }
}

benchmark with only lexer :
/query$ gotb -test.run=XXX -v  -benchtime=5s
BenchmarkQueryParse/spielberg:handwitten:-4               200000         45724 ns/op
BenchmarkQueryParse/spielberg:antlr:-4                          5000       1468218 ns/op
BenchmarkQueryParse/tomhanks:handwitten:-4              500000         28649 ns/op
BenchmarkQueryParse/tomhanks:antlr:-4                         5000       1538988 ns/op
BenchmarkQueryParse/nestedquery:handwritten:-4         100000         80210 ns/op
BenchmarkQueryParse/nestedquery:antlr:-4                      5000       3029668 ns/op
PASS
ok      github.com/dgraph-io/dgraph/query    63.546s

// lexer + parser for antlr.
ashishnegi@ashish:~/work/golang/src/github.com/dgraph-io/dgraph/query$ gotb -test.run=XXX -v  -benchtime=5s
BenchmarkQueryParse/spielberg:handwitten:-4               300000         47772 ns/op
BenchmarkQueryParse/spielberg:antlr:-4                          3000       1868297 ns/op
BenchmarkQueryParse/tomhanks:handwitten:-4              500000         27980 ns/op
BenchmarkQueryParse/tomhanks:antlr:-4                         5000       1616518 ns/op
BenchmarkQueryParse/nestedquery:handwritten:-4          100000         74961 ns/op
BenchmarkQueryParse/nestedquery:antlr:-4                      2000       3312977 ns/op
PASS
ok      github.com/dgraph-io/dgraph/query    58.056s


I think that this is well known issue that lexing takes most of the time.
Please share any general tips that i can try to bring down the numbers.

[Mike Lischke]

> With some help from @KvanTTT on github, lexing is taking most of the time.
>
> with only doing the lexing :
> func runAntlrParser(q string, b *testing.B) {
> b.ResetTimer()
> for i := 0; i < b.N; i++ {
> input := antlr.NewInputStream(q)
> lexer := parser.NewGraphQLPMLexer(input)
> // for only lexer benchmark
> t := lexer.NextToken()
> for t.GetTokenType() != antlr.TokenEOF {
> t = lexer.NextToken()
> }
> }
> }

ANTLR4 has a significant warmup phase where internal structures are created and cached. So I recommend not to measure the first loop run. The following runs are much faster then usually. However, even after the first run things can go slower if you parse different input, because the mentioned structures are created on demand.

And a side note: you can call BufferedInputStream.fill() to read all tokens instead of a manual loop to read all tokens.

Mike
--
www.soft-gems.net

[ashish...@gmail.com]

To get help from warmup, i am now running :

func runAntlrParser(q string, b *testing.B) {

    // warmup..
    for i := 0; i < 200; i++ {

        input := antlr.NewInputStream(q)
        lexer := parser.NewGraphQLPMLexer(input)

        lexer.GetAllTokens()

    }

    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        // b.N is around 5000

        input := antlr.NewInputStream(q)
        lexer := parser.NewGraphQLPMLexer(input)
        // for only lexer benchmark

        lexer.GetAllTokens()
    }
}

this function is called for 3 queries where b.N is 5000 ;; [ it is actually more involved process of benchmarking provided by golang test library]

func BenchmarkQueryParse(b *testing.B) {
    b.Run("spielberg:antlr:", func(b *testing.B) { runAntlrParser(aq9, b) })
    b.Run("tomhanks:antlr:", func(b *testing.B) { runAntlrParser(aq10, b) })
    b.Run("nestedquery:antlr:", func(b *testing.B) { runAntlrParser(aq11, b) })
}
 

Q. I hope ANTLR4 stores the cache in some global data structure ;  to benchmark i am creating new parser objects ; Do i have to use same Parser object for taking advantage of caching ?
EDIT ** i meant : to benchmark i am creating new lexer objects ; Do i have to use same Lexer object for taking advantage of caching ?

Results have still not changed :

h/query$ gotb -test.run=XXX -v -benchtime=5s
BenchmarkQueryParse/spielberg:antlr:-4                   5000       1553737 ns/op
BenchmarkQueryParse/tomhanks:antlr:-4                  5000       1408192 ns/op
BenchmarkQueryParse/nestedquery:antlr:-4               3000       2972603 ns/op
PASS
ok      github.com/dgraph-io/dgraph/query    27.793s


I also tried setting prediction mode to SLL and that has not helped either.

[Mike Lischke]

> To get help from warmup, i am now running :
>
> func runAntlrParser(q string, b *testing.B) {
> // warmup..
> for i := 0; i < 200; i++ {
> input := antlr.NewInputStream(q)
> lexer := parser.NewGraphQLPMLexer(input)
> lexer.GetAllTokens()
> }

There is no sense in running the same input multiple times for warmup - once is enough. If you input changes it *can* happen (depending on the input and what ran before) that additional structures must be created (also once).

>
> b.ResetTimer()
>
> for i := 0; i < b.N; i++ {
> // b.N is around 5000
> input := antlr.NewInputStream(q)
> lexer := parser.NewGraphQLPMLexer(input)
> // for only lexer benchmark
> lexer.GetAllTokens()
> }
> }
>

> Q. I hope ANTLR4 stores the cache in some global data structure ; to benchmark i am creating new parser objects ; Do i have to use same Parser object for taking advantage of caching ?

Yes, it's the global ATN which is a static structure shared among all parser and lexer instances (there are 2 of them, one for lexers and one for parsers).

>
> Results have still not changed :
>
> h/query$ gotb -test.run=XXX -v -benchtime=5s
> BenchmarkQueryParse/spielberg:antlr:-4 5000 1553737 ns/op
> BenchmarkQueryParse/tomhanks:antlr:-4 5000 1408192 ns/op
> BenchmarkQueryParse/nestedquery:antlr:-4 3000 2972603 ns/op
> PASS
> ok github.com/dgraph-io/dgraph/query 27.793s

Hmm, of course, with more and more iterations the warmup has less and less influence on the outcome. And for simple queries the time consumed during warmup is negligible. Of course there can be target specific things that slow down parsing. In order to see if that is an ANTLR issue per se or just something in the Go target you could try other targets (e.g. C# or C++).

Mike
--
www.soft-gems.net

[ashish...@gmail.com]

Mike, i really appreciate your help here. and thanks for clarifying about global datastructures.

Just to be clear, In benchmarks, numbers are per operation. So,

`BenchmarkQueryParse/spielberg:antlr:-4                   5000       1553737 ns/op `
means that spielberg query took ~1.55 ms on average when caching was enabled.

Our queries are smaller and at least some part of the query would be random always.
So,  with these results that use caching we can infer that this is what golang target version of ANTLR4 can achieve.