[5.2] Build occurrences index for Merlin

[voodoos]

This PR adds new rules that drive the ocaml-index tool to aggregate a workspace index. The rules are a bit simpler as the ones in https://github.com/ocaml/dune/pull/6762 since now part of the indexation will is done by the compiler in 5.2.

Building the index involves three steps:

• Use the -bin-annot-occurrences flag to have the compiler store partial indexes in the cmt files.
• Run the ocaml-index tool to make an index for each stanza (actually each compilation-context).
• Run the ocaml-index tool to aggregate every stanza's index into a global project index.

I ran simple benchmarks on Dune itself. These are cold builds ran after ./dune.exe clean:

Command	Mean [s]	Min [s]	Max [s]	Relative
./dune.exe build @check (without -bin-annot-occurrences)	8.632 ± 0.167	8.454	8.950	1.00
./dune.exe build @check	8.637 ± 0.108	8.433	8.796	1.00
./dune.exe build @check @ocaml-index	13.597 ± 0.173	13.384	13.904	1.00

• There are no perceptible performance cost of using the -bin-annon-occurrences flag when writing cmt files, so the best option is probably to always use that flag to simplify the rules.
• Actually building and gathering the index is costly (especially from a cold build), so it should be opt-in. (We have several optimizations in mind that should improve that situation in the future.)

There are several moving parts that I would like to discuss in the next dune-dev meeting:

1. The indexing rules have specific dependencies that I am unsure how best to check/enforce:
   • The external ocaml-index tool must be installed
   • The -bin-annot-occurrences flag requires OCaml 5.2
2. I am unsure of the best way to make indexation opt-in (it can be expensive on massive projects)
   • I initially added a dune-workspace-level option that I remove in cd34ae18a860a3e7aec6b6fe0f798d891cb22617 following a discussion with @emillon
   • I currently think we could simply keep the @ocaml-index alias but remove it from @default so that users have to explicitly use it.

Other issues to consider:

• The Melange compiler is not yet accepting the -bin-annot-occurrences flag

[emillon]

For a first release, I would consider the following strategy to select whether this feature is enabled:

• attach these rules to @ocaml-index
• if ocaml-index is available, and OCaml >= 5.2 (which I suppose is an opam constraint already), attach @ocaml-index to @check

(This is similar to how we set up sherlodoc, though the situation is a bit different)

That way:

• you can test this in dune's test suite, by providing a fake ocaml-index binary (check how sherlodoc is tested)
• people can use it in an opt-in way in their workspaces
• we can find later a way to configure this in a more precise way.

[voodoos]

For a first release, I would consider the following strategy to select whether this feature is enabled:

* attach these rules to `@ocaml-index`

* if `ocaml-index` is available, and OCaml >= 5.2 (which I suppose is an opam constraint already), attach `@ocaml-index` to `@check`

(This is similar to how we set up sherlodoc, though the situation is a bit different)

That way:

* you can test this in dune's test suite, by providing a fake `ocaml-index` binary (check how sherlodoc is tested)

* people can use it in an opt-in way in their workspaces

* we can find later a way to configure this in a more precise way.

I wonder whether we should attach @ocaml-index to @check to make it really "opt-in" ?

[voodoos]

@rgrinberg removing the aggregation step does have an impact on cold build time, which is probably more noticeable on rebuilds. @check @ocaml-index is still 46% slower than @check, but it was 57% before.

Command	Mean [s]	Min [s]	Max [s]	Relative
./dune.exe build @check	9.090 ± 0.089	8.959	9.222	1.00
./dune.exe build @check @ocaml-index	13.302 ± 0.174	12.964	13.449	1.00

But now I realize that my measurement are wrong: the @ocaml-index appears to build much more targets (and not only indexes) than @check so it is not a good comparison. (and maybe I do something wrong in my rules ?)

If I compare with @check @install the results are much "better", only a 16% increase in built time:

Command	Mean [s]	Min [s]	Max [s]	Relative
./dune.exe build @check @install	18.552 ± 0.441	18.206	19.745	1.00
./dune.exe build @check @install @ocaml-index	21.517 ± 0.219	21.224	21.976	1.00

But even then, there is some additional building happening (in vendored dirs notably). I find this a bit surprising since the dependencies of @ocaml-index are "every cmt of every stanza of the project" which I would expect to be the result of building @check ?

Additionally, is there some way to list the targets built for some given aliases ? And to have Dune output time spent running commands (ideally total time per tool) ?

In any case, the more I think about it the more I am convinced that the "don't merge" strategy is the best. I will update the merlin config and see how it goes.

[rgrinberg]

As discussed, the performance penalty currently is too large to build this by default. A separate alias sounds like a good start to me. When this feature becomes fast enough for general use, do you think we will still need the ocaml-index alias?

Also, could you comment on the stability of this feature for the users? When this feature is shipped, is it recommended that everyone start using it right away? Or is it more for wider experimentation?

[voodoos]

Thanks for your review @rgrinberg. I was focused on experimenting with performance improvement but I will answer your comments soon.

We spent some time with @emillon to make the indexer faster and we did found some important optimizations.

However indexing only the libraries/executables which are part of @check still takes increases cold-build time by 18% . Moreover most of the additional time is spent at the end of the build when indexing the dune_rules library which features a large number of modules. I notably tried things such as indexing each cmt independently to get finer grained dependencies. This improves partial re-build time a lot but also increase significantly cold-build time because it doesn't allow the indexer to cache results that are the same for every cmt.

In short, I don't think we can afford to enable the feature by default right now. I propose to add two additional targets:

• @check-index which only indexes cmt generated by the @check target
• @index-all which perform full indexation of the project, which might trigger the build of additionnal targets like unused vendored dependencies.

Eventually, our best option is probably to have LSP ask dune via RPC to update the index when needed.

Command	Mean [s]	Min [s]	Max [s]	Relative
./dune.exe build @check	8.789 ± 0.094	8.673	8.920	1.00
./dune.exe build @check-index	10.422 ± 0.174	10.227	10.838	1.00
./dune.exe build @index-all	11.520 ± 0.239	11.177	11.877	1.00

Results are actually better on a codebase such as Irmin where there is no single very large library such as dune_rules: the time increase between @check ad @check-indexis 9.5%.

Command	Mean [s]	Min [s]	Max [s]	Relative
dune build @check	15.718 ± 0.091	15.618	15.928	1.00
dune build @check-index	17.220 ± 0.129	17.000	17.420	1.00
dune build @ocaml-index	17.437 ± 0.120	17.228	17.601	1.00

There is a tension between: more granularity for smaller incremental rebuild VS less granularity that allow for greater use of cache which speeds up cold builds but slow down incremental rebuilds. We could probably adapt the indexer to cache on the disk results for each cmt so that we could get the best of both worlds, but I don't think the benefit would be big enough to make it a priority.

[rgrinberg]

Additionally, is there some way to list the targets built for some given aliases ? And to have Dune output time spent running commands (ideally total time per tool) ?

Yes, there's the --trace-file flag

[rgrinberg]

Could you stick to check-index or index-all for now? The only reason vendored sources aren't included in @check is because of a bug.

[voodoos]

I rebased the PR and made a few more changes like adding documentation and removing @check-index.

I think the PR is now ready for another round of review.

@rgrinberg I still wonder about the hidden transitive deps issue. I think now that the compiler supports the -H flag and Merlin has corresponding configuration directives we should pass it the hidden deps using these directives Right now to get the set of hidden deps I use requires_link \ requires_compile and it appears to work, but is that correct ? Is there a better way to get these ?

[rgrinberg]

Right now to get the set of hidden deps I use requires_link \ requires_compile and it appears to work, but is that correct ? Is there a better way to get these ?

I think it's correct though not ideal. I can't think of a better way

[voodoos]

Right now to get the set of hidden deps I use requires_link \ requires_compile and it appears to work, but is that correct ? Is there a better way to get these ?

I think it's correct though not ideal. I can't think of a better way

Right, I reworked the update of Merlin's configuration to use this set and also rely on the new BH and SH directives that take advantage of the new "hidden deps" mechanism of the compiler.

I moved these changes to a separated PR since they are a bit orthogonal: https://github.com/ocaml/dune/pull/10535

[voodoos]

@rgrinberg you contributed multiple refactorings to the PR, should I include you into the list of contributors in the changelog entry ?

[rgrinberg]

There's no need