Review: Latent Dependencies

[lberki]

Hey there,

This is the review for the proposal "Latent Dependencies: user logic to choose whether a dependency is analyzed". (here)

The short summary is that dependency injection frameworks frequently ignore large parts of the dependency graph, thereby wasting loading and analysis work. This proposal makes it possible for Bazel to ignore such unnecessary dependencies, thereby eliminating the above waste.

[lberki]

cc @Bocete

[lberki]

cc @jgrave3

[lberki]

One limitation was brought to my attention: as it is, the above design makes it possible for a latent dependency to be materialized at any point in its reverse transitive closure, which makes it impossible for Bazel to determine when it will not be used anymore, and thus reclaim its memory use if need be.

Technically, this could be solved by walking the Java object graph of the providers a given configured target produces and noting every LatentDep object accessible from it, but that is expensive and makes the common case (where there are no latent deps) worse to improve the uncommon case (when there are latent deps) so it's not a fantastic alternative.

With this in mind, I propose the following alternative:

1. Latent deps will be represented not by a list of LatentDep objects in ctx.attr.<name> but by a LatentDepInfo there.
2. LatentDepInfo would have a field that in turn contains the list of LatentDep objects
3. Every configured target or aspect that propagates latent deps upwards must have a LatentDepInfo provider that contains all the latent dependencies it propagates (they can still be in any other provider, but they must also be in LatentDepInfo)
4. When latent deps are materialized, Bazel checks whether the invariant in (3) holds

This way, Bazel can tell when a latent dep is guaranteed not to be needed anymore.

@jin @comius WDYT?

[jin]

Would it ever make sense to materialize a latent dependency twice in an upward path?

i.e. once an aspect lower in the graph materializes a dep, could it immediately throw the latent dep object away (or mark it as "materialized"), and pass the materialized information back up the graph?

[jin]

re: point 4, I think a different way to put it is: "Bazel cannot reclaim memory from configured targets that have a LatentDepInfo provider that's yet to be materialized?

[lberki]

More like "Bazel cannot reclaim memory of targets that are referenced by a LatentDepInfo provider"

re: materializing more than once: I don't know if there is a reasonable use case for them, but I don't think we gain anything from it: if we make that a rule, we'd have to enforce it, we'd still need the LatentDepInfo trick in order to find out when a label is never going to be materialized, so I don't think we gain anything by allowing a label to only be materialized once.

[jin]

Surfacing a concern that I have in this comment, I fear that this adds yet another advanced knob to the Starlark APIs that makes Bazel 1) harder to learn and 2) harder to reason about.

1. is also conflated by the coexistence of late bound defaults and computed defaults. For example, if you told me those are the names of this new mechanism (latent deps), I wouldn't be surprised.

This is also conceptually similar to a select statement (as pointed out by @gregestren), which could also confuse people even more. What makes this different to structuring the build graph in a way that instead of wherever you apply the aspect materializer function, you transition a config object down that could be used for a select statement further down the graph to analyze the selected attribute branch there and then?

Can we simplify?

[lberki]

Yes, the increase in API surface are is definitely real, but I don't see any obvious way to make this simpler while keeping all the benefits. In particular, I don't think configuration transitions are an adequate replacement. Here are the reasons, roughly from weakest to strongest, taking the dependency injection use case as an example:

1. Data in configurations is currently not very structured: one can only put simple data types like strings, integers, labels and lists thereof in there and it looks like we'd need something more complicated than that. Granted, this could in theory be fixed without any increase in the theoretical power of any part of Bazel, but it's still additional API surface.
2. It would contribute to lower cache ratios: assuming that A1 and A2 depend on B depends on C and the decision whether the default implementation of C should be included is made by A1 and A2, the data must necessarily be passed through B. If it's done through its configuration, B must necessarily be analyzed twice and its output paths must be different (so that A1 and A2 can be built in the same invocation) so you'd also lose remote execution caching efficiency.
3. It's not always possible to determine in a top-down manner what should be included: assuming that A depends on B1 depends on C1, A depends on B2 and C2, one needs to know whether C1 and C2 implement the same interface in order to determine which one (or both) need to be included. This can't be done in a top-down manner.

I thought a bit about how this could be achieved in way that's less powerful, but I haven't been able to come up with anything other than the "run a periodic cleanup process in the repository" idea which I'm pretty sure would be worse overall.

[jin]

Can we transport such data in "fragments" that B declares to not use (and thus doesn't need to be analyzed with it) and C declares to use (and thus will be analyzed with it, and uses it to decide on the select() branch)? B will serve as a "fragment forwarder" for the different fragments from A1 and A2 to C.

This will tackle 1) and 2), but I guess not 3).

[lberki]

re: "transport", as in, downwards, towards dependencies, from A to C? I'm afraid without solving (3), it doesn't help for the #1 use case (dependency injection).

[lberki]

Update: this is now approved by @meisterT @jin and @haxorz . All that now remains is the minor detail of implementing it!

[lberki]

Update: I implemented this, played with it then found some pretty significant holes.

Namely, in this design, the decision about what to materialize can depend on any configured target, which means that in order to compute the full configured target graph, one may need to do arbitrary analysis. This would in turn mean that one couldn't be sure that a given configured target is not needed anymore, ever which interferes with our future plans to reclaim RAM.

I have some ideas about how to fix this and I have a prototype almost ready. Once it's ready, I'll write it up and send the updated design for discussion and notify this thread.

[lberki]

The new design doc is here .