Introduce multicore parallelism for 40% speed-up on presenting `opam install` plan

[mbacarella]

Hello! This PR is humbly submitted for your consideration.

This is a PR that introduces multicore parallelism to try to reduce opam wall-clock time.

The opam solver and job scheduler have had a lot of heroic work done on them to make them blazingly fast. This is not a PR for that stuff.

Instead, this PR tries to parallelize a lot of the bootstrapping that's done before we get to the solver. On typical workstations, opam install can spend 6-10 seconds loading everything needed to run on the solver and present the final list of packages that it would install.

This patch speeds that interactive step up by about 40% by recruiting more cores.

It does so by embracing OCaml 5.0 and also domainslib.

Anticipated questions

Q: Doesn't requiring OCaml 5.0 reduce the population of people that can build this? Most major users are still on 4.x, right? A: Kind of, but is that a huge issue? Most users of opam install from binary. Distributing an opam binary build against OCaml 5.0 doesn't stop users from using it on their OCaml 4.x projects.

Q: Is this worth it? Surely the important part is making opam install your packages faster, not the 10 seconds of bootstrapping in the beginning? A: Actually installing the packages is important, sure, but the interactive part of opam is waiting to see the list of what can be installed and I think making that faster pays dividends too. Once you decide to install a huge list of packages you can just hit enter and go grab a coffee (er, I mean, task switch to some other productive endeavor). But before that moment, you are busy-waiting on opam to get back to you. This patch hopefully improves quality of life there.

How to run it

0. Install and activate an OCaml 5.0 switch
1. Clone this repo
2. Check out this PR's branch.
3. Do ./configure --with-vendored-deps
4. Run make
5. Run ./opam

Your thoughts are kindly requested. Thanks!

[dra27]

This is very interesting! Just as a brief note for now, if you move dose3.patch to src_ext/patches/dose3.common/dose3.patch, the first configure with --vendored-deps should succeed.

[mbacarella]

Nice. moved to patches!

[kit-ty-kate]

We had a look during the dev meeting and this change looks good and extremely welcome.

We are currently concentrating our efforts on the release of 2.2.0 but we'll give a more serious look after the release.

As a pre-review, we were wondering if the diff could be reduced by moving the thread pool into OpamStateConfig.r and initializing it in the client. Also, this way, uses of the API becomes single-thread by default without any required change.

Out of curiosity, do you have the benchmark result before and after changing dose3 by any chance?

As for making opam OCaml 5.0 only, we could always simply create our own shim that would make pre-5.0 uses sequential or simply use domain_shims, if we prefer keeping support for OCaml 4, so this doesn't seem to be much of an issue.

[mbacarella]

Glad it was well received. Some thoughts.

1. The diff looks larger than it really is because I had to wrap startup blocks in OpamMulticore.run_with_task_pool (fun task_pool ->. Most of that is two spaces of indent, though GItHub's diff tool shows it as massive removals and insertions. If you use patdiff it should be a lot easier to evaluate.

2. That said, I'm not against moving the task pool initialization and acquisition into the global state config, but I was trying to leave it late binding so that the task pool size could be affected by command-line arguments (not yet done). One other thing pushing back against moving it into global state config is Task.async and Task.parallel_for must be run under an enclosing Domainslib.Task.run (fun () ... call. So, maybe re-evaluate the shorter diff in step 1 and let me know if it still seems huge?

3. For benchmarking, I was doing something like time opam install patdiff --debug-level=2 --no and comparing standard opam to multicore. I don't have individual dose3 benchmarks available, it doesn't seem to share opam's logging framework. I was just instrumenting Printf.printf "I am starting here now: %f\n%!" (Unix.gettimeofday ()) at various points to get timings.

[c-cube]

For the diff size, you could replace

OpamMulticore.run_with_task_pool
  (fun task_pool -> …

with

OpamMulticore.run_with_task_pool @@ fun task_pool ->
…

which doesn't affect indentation.

[mbacarella]

good idea, @c-cube! done in last push

dev-team: let me know if the resultant diff is easier on the eyes

[kit-ty-kate]

dev-team: let me know if the resultant diff is easier on the eyes

2. One other thing pushing back against moving it into global state config is Task.async and Task.parallel_for must be run under an enclosing Domainslib.Task.run (fun () ... call. So, maybe re-evaluate the shorter diff in step 1 and let me know if it still seems huge?

My comment was less about the diff in a visual sense and more about whether the API changes or not, as outside users do use the API through the opam-state/opam-client/... packages. But indeed we didn't think Task.async needed to be run inside of the closure of Task.run. In that case it makes sense to have the extra parameter.

For benchmarking, I was doing something like time opam install patdiff --debug-level=2 --no and comparing standard opam to multicore. I don't have individual dose3 benchmarks available, it doesn't seem to share opam's logging framework. I was just instrumenting Printf.printf "I am starting here now: %f\n%!" (Unix.gettimeofday ()) at various points to get timings.

With debug-level 1 and up you can see how long does dose3 alone take overall with these two lines:

00:02.729  CUDF                   Checking request...
00:04.479  CUDF                   Request checked in 1.749s

[mbacarella]

With debug-level 1 and up you can see how long does dose3 alone take overall with these two lines: 00:02.729 CUDF Checking request... 00:04.479 CUDF Request checked in 1.749s

It does. I thought you were asking about micro-benchmarking portions of dose3. (FWIW: Not every portion benefitted from being parallelized so I didn't do them, and some parts could probably benefit from parallelization if the algorithms were re-worked. I may swing into that in the future.)

[kit-ty-kate]

I made an experiment trying to parallelize another part of the code in https://github.com/ocaml/opam/pull/5966. If we want to head to a future where the opam internals are fully parallelisable we probably want to pull both your PR and mine in some capacity (I'm planning to split mine into smaller chunks once 2.2.0 is out).

Btw, I'm not sure if it was available at the time but the TSan option in OCaml 5.2 was extremely useful to detect data races, in case you or someone else wants to try and parallelize another part of opam in the future.