Catastrophic performances on OCaml files

[Niols]

Describe the bug

On trivial OCaml files, Topiary in its latest version takes forever to run.

To Reproduce

On my machine, this takes about 20s:

$ echo 'let () = ()' > test.ml
$ time topiary -if test.ml

It was confirmed on @aspiwack's machine as well.

Expected behavior

I would expect Topiary to run under one second.

Environment

• OS name + version: NixOS
• Version of the code: v0.2.1, v0.2.2 and master all seem affected.
  edit: v0.2.1 is slow, but not catastrophically slow; cf Topiary is pretty slow on formatting OCaml codebases #525

Additional context

Bisect and flamegraph coming soon.

[Niols]

A quick bisect suggests this might be one of 454fd6f and 6e55140 (from #494) that both have to do with updating our dependency in the OCaml grammar. Topiary is still not the fastest before but at least runs in a few seconds.

[ErinvanderVeen]

Attached is the flamegraph on my machine of Topiary formatting the OCaml snippet above.

[ErinvanderVeen]

Nearly all of the time is spend in initializing the query in the tree-sitter crate. I don't think our OCaml queries are so crazy that they should cause such an issue, but we should investigate anyway. Otherwise this is an upstream issue that we've run into (tree-sitter or tree-sitter-ocaml).

[Niols]

For a tiny bit of context, initially, I was just complaining to @nbacquey that Topiary was taking more than 1s per file for simple files. He then noticed that I was using v0.2.1 and asked me to try the latest version... that happened to be much much much worse. After we fix this, we should still investigate was to make normal runs faster. cf issue by @aspiwack above.

[aspiwack]

Was this closed by mistake? Or is there another tracking issue now that #522 is merged?

[Niols]

I think I can now open the issue I had initially about Topiary being quite slow (with quite slow = one second per file).

edit: done in #525

[aspiwack]

You can (though there is #523 which tracks some of it). But we still need to understand what's going on in the last version Ocaml grammar and query, and address this issue.

[ErinvanderVeen]

This was closed automatically by GitHub.

[Niols]

Quick benchmark of running Topiary (as of 738a178) compiled in release mode on all the *.ml files of Morsmall. This consists in running:

time find -name '*.ml' -print -exec topiary -if {} \;

a few times while bisecting on tree-sitter/tree-sitter-ocaml. I was expecting one commit changing the behaviour violently, but I actually found two so there were two different bisections. Here are the results:

Commit	Query	1	2	Time
tree-sitter/tree-sitter-ocaml@de07323 (v0.20.1)	old	good	good	0:10
tree-sitter/tree-sitter-ocaml@f1106bf	old	good		0:10
tree-sitter/tree-sitter-ocaml@d025214	old	bad		0:30
tree-sitter/tree-sitter-ocaml@cece53c	old	bad		0:30
tree-sitter/tree-sitter-ocaml@a09c63f	old	bad	good	0:30
tree-sitter/tree-sitter-ocaml@4823fe7	old		good	0:30
tree-sitter/tree-sitter-ocaml@f4214a1	new		bad	1:45
tree-sitter/tree-sitter-ocaml@9724dfa (v0.20.2)	new		bad	2:05
tree-sitter/tree-sitter-ocaml@2da4930 (master)	new	bad	bad	1:30

The column “query” tells whether I use Topiary as of 738a178 or if I include the new query as per 738a178. The columns 1 and 2 represent the two bisections and what I told git. The column “time” is to be taken with a grain of salt, especially for the longer times that I repeated less often. There seems to be two different performance drops making Topiary approximately 3x slower (which, as the flamegraph suggests, should be almost linear in the time spent in the query initialisation).

• tree-sitter/tree-sitter-ocaml@d025214
• tree-sitter/tree-sitter-ocaml@f4214a1 (although it is to be noted that our OCaml query has to be updated to follow this change).

[aspiwack]

The first change (tree-sitter/tree-sitter-ocaml@d025214) merely adds the ability to write () as a functor argument (it makes the functor generative). How could such a small change possibly affect our query's build time?

[Niols]

The changes are massive, though, so I guess it all depends on what tools were used to re-generate the parsers from the grammar. Maybe those tools too were updated?

[Niols]

(It is also entirely possible that my measurements are flawed in one way or another.)

[aspiwack]

Ah, yes, the generated C files both advertise 500k line diffs (whereas grammar.js has a 3-line diff!). I'm rather confused why they're so big to begin with. But maybe it goes part of the way to explain where the time is spent.

[ErinvanderVeen]

Between those two commits, where the time blows up, the number of internal tree-sitter state machine states increases from 9769 to 24361. So it is probably worth for the Topiary team to invest some time into optimizing the ocaml grammar.

[314eter]

It looks like I was using tree-sitter-cli 0.20.7 to generate the parser before tree-sitter/tree-sitter-ocaml@d025214, and accidentally switched back to 0.20.6. That can explain the difference, since the actual change in the grammar is very small.

The number of states has indeed increased a lot because of tree-sitter/tree-sitter-ocaml@f4214a1. The actual structure of the grammar didn't change that much, but a lot of anonymous nodes became names nodes. It can be combination of slower parsing (although more states doesn't necessarily mean slower parsing) and the more complicated query. Operators are used a lot, so if the query becomes a bit slower that can have a big impact.

[ErinvanderVeen]

Hej! I've done some experimentation using different tree-sitter versions, I'll post my results in a bit.

[aspiwack]

@314eter for the record, in our current measurements, we basically can't see the time spent parsing. The time is overwhelmingly dominated by compiling the query. Compiling queries maybe scales super-linearly with the number of states of the grammar? This is what our current state of understanding would suggest.

[ErinvanderVeen]

cargo bench with tree-sitter 0.20.8:
    time:   [589.75 ms 592.02 ms 594.39 ms]

cargo bench with tree-sitter 0.20.6:
    time:   [4.6863 s 4.7138 s 4.7421 s]

@314eter Would you be able to re-generate the OCaml parser.c with a newer version of tree-sitter?

[314eter]

I published a new release: https://github.com/tree-sitter/tree-sitter-ocaml/releases/tag/v0.20.3

[Niols]

@ErinvanderVeen Now that #533 is merged, is there still a reason to keep this one open?

[ErinvanderVeen]

@Niols Thank you, closed in favour of #539