Parser very slow

[brtzsnr]

The parser allocates an enormous amount of memory

var tree tokenTree = &tokens32{tree: make([]token32, math.MaxInt16)}

And then uses own vector doubling scheme

func (t *tokens32) Expand(index int) tokenTree {
        tree := t.tree
        if index >= len(tree) {
                expanded := make([]token32, 2*len(tree))
                copy(expanded, tree) 
                t.tree = expanded
        }
        return nil
}

Both of these causes the parser to be very slow because it generates an big amount of garbage. Should probably be optimized.

[egorse]

In my case replacing math.MaxInt16 to 128 did the magic

BenchmarkParse-4   	   20000	     82396 ns/op	  395222 B/op	      28 allocs/op

BenchmarkParse-4   	  200000	      5859 ns/op	    3541 B/op	      28 allocs/op

[pointlander]

Was this done with the benchmark in peg_test.go? I didn't see a speed up using 128. I could make the initial size of 'tree' an option.

[egorse]

That's my own test.
But it measures Init + Parse. The go_test has Init out of benchmark.

Is the 'tree' written in random order or sequencially? Would it better to use golangs Append?

[egorse]

@pointlander btw the benchmark for parse slightly incorrect. The reset() does not brings the var tree back to state of first run. So its warmed up - that's why it looks like it has no probs with memory.

So the benchcmp looks like:

benchmark            old ns/op     new ns/op     delta
BenchmarkParse-4     1651956       1844908       +11.68%

benchmark            old allocs     new allocs     delta
BenchmarkParse-4     0              1              +Inf%

benchmark            old bytes     new bytes     delta
BenchmarkParse-4     786           786432        +99954.96%

[egorse]

Wonder if it be better option to have AST optional? It still would be fine, if #53 is implemented.

benchmark                old ns/op     new ns/op     delta
BenchmarkParse100-4      88669         9559          -89.22%
BenchmarkParse1K-4       135841        45521         -66.49%
BenchmarkParse10K-4      618565        424709        -31.34%
BenchmarkParse20K-4      1374249       844599        -38.54%
BenchmarkParse50K-4      3483712       2102696       -39.64%
BenchmarkParse100K-4     7148746       4185912       -41.45%
BenchmarkParse200K-4     14428879      8532638       -40.86%
BenchmarkParse500K-4     33124910      21241933      -35.87%

benchmark                old allocs     new allocs     delta
BenchmarkParse100-4      28             26             -7.14%
BenchmarkParse1K-4       28             26             -7.14%
BenchmarkParse10K-4      28             26             -7.14%
BenchmarkParse20K-4      29             26             -10.34%
BenchmarkParse50K-4      30             26             -13.33%
BenchmarkParse100K-4     31             26             -16.13%
BenchmarkParse200K-4     32             26             -18.75%
BenchmarkParse500K-4     33             26             -21.21%

benchmark                old bytes     new bytes     delta
BenchmarkParse100-4      395718        2469          -99.38%
BenchmarkParse1K-4       399110        5861          -98.53%
BenchmarkParse10K-4      435973        42725         -90.20%
BenchmarkParse20K-4      1263365       83685         -93.38%
BenchmarkParse50K-4      2959120       206565        -93.02%
BenchmarkParse100K-4     6301456       403173        -93.60%
BenchmarkParse200K-4     12994320      804584        -93.81%
BenchmarkParse500K-4     26781456      2008812       -92.50%

[pointlander]

AST could be useful for Execute:

a <- b { fmt.Println(matches[ruleb]) }
b <- 'b'

matches would be of type 'map[pegRule]string' and contain the string last matched by a rule.

[egorse]

Just FYI. Golang 1.7.3 vs 1.8beta2

benchmark           old ns/op     new ns/op     delta
Benchmark100-4      46171         35606         -22.88%
Benchmark200-4      51137         38867         -23.99%
Benchmark500-4      62289         47871         -23.15%
Benchmark1k-4       80334         65205         -18.83%
Benchmark10k-4      369003        306170        -17.03%
Benchmark20k-4      368056        302885        -17.71%
Benchmark50k-4      1769308       1466341       -17.12%
Benchmark100k-4     3533624       2913083       -17.56%
Benchmark200k-4     7872356       6253801       -20.56%
Benchmark500k-4     20558354      18085645      -12.03%
Benchmark1M-4       41403256      35189057      -15.01%
Benchmark2M-4       78344012      67451728      -13.90%
Benchmark4M-4       151345529     130580661     -13.72%

[bdamm]

I have one large C file of about 33,000 lines which saw a big speedup with 128. This is not particularly large but for some reason this change sped up the parse on this file quite a lot. Sorry I don't have better data at the moment.