Hello. Why is my InstaParser so slow? 850ms vs 8ms hand-written Clojure: https://github.com/borkdude/aoc2017/blob/master/src/day16.clj#L119

Maybe it’s my grammar, but I don’t see it.

How big is the input?

The input is this: https://github.com/borkdude/aoc2017/blob/master/resources/day16.txt

Here’s the grammar: https://github.com/borkdude/aoc2017/blob/master/src/day16.clj#L17

I mean, you're basically generating one string per character in a 40kb file. I'm not surprised it's slow.

And wrapping with vectors, etc

That’s fair, but even without wrapping the arguments I get a similar time

I had that before, but I wanted to transform the arguments to ints, that’s why I wrapped them later

Hmm yeah

I mean, it’s not really a problem, but just curious why or if I made a mistake in my grammar

I don't think you made a mistake like an ambiguity issue or anything

It's just really exercising the parser's dataflow overhead

I saw similar issues when trying to perf-tune @dave's Alda parser a while ago

Because his rules were like "if you see this single character, parse this other single character"

Instaparse does a lot of bookkeeping during a parse to make sure it magically works with weirdly recursive grammars, so for super low level parsers like this it doesn't exactly shine

(def parse2
  (insta/parser
   "<INPUT>       = (INSTRUCTION <','>)+ INSTRUCTION 
    <INSTRUCTION> = SPIN | EXCHANGE | PARTNER
    SPIN          = <'s'> POSITION
    EXCHANGE      = <'x'> POSITION <'/'> POSITION
    PARTNER       = <'p'> PROGRAM  <'/'> PROGRAM
    <POSITION>    = #'\\d\\d?'
    <PROGRAM>     = #'[a-p]'"))

ok

Just curious, does anything improve if you change the first rule to INSTRUCTION (<','> INSTRUCTION)*?

I wondered about that rule as well. Quickbenching…

Yup, 582ms!

Does the order of rules matter for performance?

I mean, when it’s more likely to encounter EXCHANGE, does it help putting that first?