Performance on large Monorepos

[dziemba]

We're currently using target-determinator for our monorepo and are quite happy with it.
As we are moving more components into the monorepo, we are notificing that the performance of target-determinator is becoming problematic. Since we run it on each PR CI build, we would like the runtime to be as low as possible.

Here's some data for our monorepo with ~2000 components.

00:00:00 Processing revision 'before' (sha: [redacted])
00:00:08 Running cquery on deps(//...)
00:01:41 Running cquery on //...
00:02:10 Finding compatible targets under //...
00:02:35 Matching labels to configurations
00:02:40 Hashing targets
00:02:59 Processing revision 'after' (current working directory state)
00:03:03 Running cquery on deps(//...)
00:04:18 Running cquery on //...
00:04:48 Finding compatible targets under //...
00:05:12 Matching labels to configurations
00:05:17 Hashing targets
00:05:38 Finished after 5m37.207708484s

Profile for bazel cquery deps(//...) --output_file=/dev/null --transitions=lite --output=streamed_proto

It seems like we're spending most of the time in the cquery calls, and they're bottlenecked by a single-threaded action for most of their runtime. Additionally it might be possible to do some concurrent work in target-determinator itself.

In our primary use-case of running the diff on PR builds against the latest master branch, we're also doing a lot of duplicate work. Instead of checking out and doing all the queries/computations on the before/master branch, we could just fetch some pre-computed data from a previous build.

I would love to hear everyone's thoughts on this, in particular where the best opportunities for optimizations are and which of them would be possible to add to this project. I'm happy to contribute with implementations. If you would like any extra benchmarking data, I can provide that as well of course.

[sitaktif]

Thanks @dziemba, we are very open to discussions about how to optimize TD!

Do you have suggestions as to the changes that can be made to improve the cquery part?

Persisting the computed hashes to bypass the "before" phase is likely to have a significant positive impact on performance (probably not quite 3 minutes in your example because that phase probably contributes to work in the "after" step, but still). I can imagine a generic persistent storage layer, starting with an on-disk implementation (basically a local cache). As a second step, an object store implementation can be implemented for cross-host caching.

Some steps can happening concurrently. For example, the hashing of targets can happen while cquery streams results (thanks @fmeum!).

More controversially, multiple bazel invocations could happen in parallel on different output bases (but that would cause lots of duplicated work, so I am unclear whether that'd be worth it).

I also wonder if there are possible improvements on the Bazel side for cquery.

Any other ideas?

[honnix]

Persisting the computed hashes to bypass the "before" phase

This is pretty much #3, right?

[honnix]

I played a bit with the idea of parallelising some operations in main...honnix:target-determinator:honnix/performance. Basically for two things: ParseCqueryResult while doing the second cquery and PrefillCache while computing for after.

While it does improve the overall time, it seems to be racy somewhere. Maybe @sitaktif you could help take a look where things are not supposed to run in parallel? Thank you.