incr.comp.: Maybe optimize case of dependency-less anonymous queries.

[michaelwoerister]

Some kinds of queries can end up with no dependencies. That is a valid case if their computation solely depends on their query key and not on anything in the environment. erase_regions_ty is such a case.

We could optimize this case by not allocating a DepNode for such query invocations, which in turn would also save registering reads of that DepNode.

@nikomatsakis, should we do this? If so, I could write some mentoring instructions.

[michaelwoerister]

The current plan is to implement this optimization via not instantiating anonymous nodes at all. Instead their edges should be duplicated to readers.

[nikomatsakis]

I'm a fan of not instantiating anonymous nodes at all. I think that simplifies the overall model and may be a perf win to boot. Seems good.

[cjgillot]

Is this still relevant? If yes, could you explain what you mean by "not instantiating anonymous nodes"?

[nikomatsakis]

I think it's still relevant, but I'd have to dig more into the code to be sure. An "anonymous node" is a node in the dependency graph that doesn't correspond to a query. They primarily occur in trait selection, if I recall.

[wesleywiser]

The query system has changed quite a bit since the last time I looked but I will try to leave some notes in case this is helpful:

• The query system is defined in compiler/rustc_query_system

• A query is anonymous if this is true

  rust/compiler/rustc_query_system/src/query/config.rs

  Line 74 in 90b1f5a

  const ANON: bool;

• I think a query depends solely on key and not the environment if no_tcx = true

  rust/compiler/rustc_query_system/src/dep_graph/graph.rs

  Line 225 in 90b1f5a

  no_tcx: bool,

• I believe recording the edge recording happens here

  rust/compiler/rustc_query_system/src/dep_graph/graph.rs

  Line 1004 in 90b1f5a

  fn intern_node(

[tgnottingham]

I'm far from an expert in this area, but I wanted to note some potential wrinkles.

As I understand it, anonymous nodes provide two things, which we probably want to preserve:

1. They enable, or at least interact with (sorry, hazy on the details) caching the querys' results in a single compilation session. If we make multiple calls to the same anonymous query in a single session, we don't have to recompute the result.

   I'm not sure what has to change to preserve this behavior if we remove the anonymous nodes. The caching system does have some dependency on DepNodeIndex, which wouldn't exist for an anonymous query if it wasn't allocated.

2. They track dependencies. Suppose query A depends on anonymous query B, which depends on queries C and D. If we remove anonymous nodes, we need to make A depend on C and D directly, or we lose that dependency info.

   I'm not sure if this is trivial to handle. As we execute A, we build up its dependency list. We do that by adding the dependency's DepNodeIndex to A's dependency list. But if B isn't ever allocated, it doesn't have an index, so we're already in trouble. We really want to depend on C and D, anyway, so maybe we can get around it. But where are we getting that list of C and D from if it isn't stored somewhere? And if we're storing it somewhere, how much are we gaining by not just storing it in a node for the anonymous query B? There may be a good answer, it's just not clear to me.

Finally, I want to note that this may not actually be an optimization. If we copy B's dependencies into things that depend on B, this could actually result in more storage being used, depending on the queries involved. Multiple queries can depend on B. If B depends on 10 queries, now we've replaced each dependency on B with 10 dependencies. In a way, anonymous nodes are an optimization for this case. They deduplicate a set of common edges.

[michaelwoerister]

@tgnottingham's analysis is pretty spot on, afaict. To give some context (which is unfortunately lacking in the issue description):

Anonymous dep-nodes were conceived in order to represent things in the dep-graph for which we don't have a query key. In particular we used them for things cached internally in the trait selection system. Their main purpose is to enable dependency tracking for things that don't fit in the query system -- and I think we always considered them as a kind of crutch that we wanted to get rid of as soon as possible.

Some time later we discovered that we could use them as a performance optimization for queries that don't get cached on disk, like erase_regions_ty. They are more performant because they don't need to compute the DepNode fingerprint from the query key.

This issue talks about handling dependency tracking differently: Instead of introducing an anonymous node and pointing the dep-edge to it, we just duplicate the anonymous node's outgoing edges. E.g.

A <-------+  +------ C
          |  |
          |  v
         (anon) 
          |  ^
          |  |
B <-------+  +------ D    

becomes

A <---------------- C
^                   |
|                   |
+-----------+       |
            |       |
+---------- | ------+
|           |
v           |
B <---------D 

That way, we would still keep all dependencies intact. However, as @tgnottingham points out, this might not actually be an optimization. The number of edges becomes n * m instead of n + m. In the case of erase_regions_ty where n == 0, this would be beneficial, but for other cases it might make things a lot worse.

I'm wondering if we could omit allocating anon dep-nodes IFF they have zero outgoing edges? I'm not sure if that could lead to complications. Probably yes.

[cjgillot]

Marking as fixed by #85337.