Improve performance of TransitiveTargets/CoarsenedTargets

[stuhood]

When #10409 introduced cycle tolerance, it also removed structure sharing of TransitiveTarget instances. This meant that if you made 100 TransitiveTargets requests, much less of their work could be reused, and in particular, cycle detection could not be reused. Cycle detection is cheap enough to do for one concurrent instance, but not to do hundreds of times redundantly.

[stuhood]

Unfortunately, this is blocked by some rule graph craziness that I'd like to lean in to fix via #11269. In the meantime, I'm going to revert the original fix for #11201, and raise the recursion limit.

[stuhood]

I believe that rather than necessarily internally structure-sharing for multiple distinct TransitiveTargets requests, there might be another solution based on adjusting TransitiveTargets to be more like CoarsenedTargets... possibly by becoming a wrapper around CoarsenedTargets, but also possibly by just becoming a fully expanded map of targets similar to _DependencyMapping.

Rather than making a TransitiveTargets request per root target, you would make a request for all root targets, and then use methods of the return type to partition and recurse on any number of roots.

[Eric-Arellano]

How hard would that be to do? I suspect it will make a tangible impact on Pylint and MyPy -- the dedicated rule for partitioning seems to take at ~1 second on my very fast M1 in a not very huge repository..

[stuhood]

How hard would that be to do?

Not too hard? I suspect that the biggest challenge will be updating all of the relevant callsites to avoid making lots of requests in parallel. But that could be incremental, since TT could continue to expose its existing methods.

[stuhood]

Going to revisit this one.

#15141 fully fixed mypy since it is always monolithic, and not broken up into batches. But when pylint is broken up into batches (due to the default --lint-batch-size=128 option), it ends up making one request for CoarsenedTargets per batch (which is effectively equivalent to having made one TransitiveTargets request per batch: hence the title change for this issue).

I'm going to spend a little bit of time thinking through whether there is a holistic solution to avoid needing to change APIs. But in the absence of that, adjusting both the lint and test APIs to take CoarsenedTargets for their roots would mean that we did a single @rule-graph level graph walk for the entire goal, rather than doing one per lint-batch or test.

[stuhood]

I gave this one some thought last week, and came to the conclusion that while structure sharing is still helpful, recursive memoization is just not feasible in the presence of graph cycles. Which is part of why when we added support for cycles, we did so by moving TT/CT calculations from recursion to iteration.

But iteration is also memoizable: usually via a map/dict on the stack of your iteration function. Unlike recursion though, it isn't referentially transparent, and so requires (visible) mutability.

So: I think that by adding a new feature to the Engine/Graph to mark a @rule output as mutable (either by adding a new field to EngineAwareReturnType, or by marking the @rule itself somehow), we can memoize the iteration of transitive dependency computation, by consuming a mutable map of structure-shared TransitiveTarget instances.

Supporting mutable state in the Graph seemingly amounts to adding all of the dependencies of any Graph Node which depends on the mutable state to the mutable state (or, equivalently: putting the consumer Node into a cycle with the mutable state it is consuming, such that either Node being invalidated would invalidate the other). This accounts for the fact that a @rule might put any of its inputs into the mutable state.