GetModIfaceFromDisk has bad first call complexity

[pepeiborra]

The current implementation of GetModIface is O(# of transitive import statements), i.e. it does an amount of work proportional to the number of imports in the project. To see why, notice that to evaluate GetModIface M, that is to load the interface for a module M, we first need to load the interfaces of all its DD direct imports, which involves DD recursive calls to GetModIface. Transitively, this makes one GetModIface M call for every import in the module graph of M. This leads to bad startup performance in projects with a dense module graph since:

O(# of import statements) = O(edges in module graph) ==> O(modules^2).

Once GetModIface M has been called at least once the ongoing cost is O(direct imports), thanks to early cutoff, which is very good.

How can we improve the bad performance of the first call while preserving the good performance of the second call?

[pepeiborra]

An alternative implementation of GetModIface M with better first call complexity would go like this:

1. Find the graph G of all the transitive imports
2. Topologically sort G into a list of MM modules (the transitive imports)
3. Load all the MM interfaces sequentially on a single HscEnv

In step 3 we avoid making any recursive calls to GetModIface and instead load all the interfaces "in place". This leads to O(transitive dependencies) complexity which is optimal and much better than the current O(# of transitive import statements).

The only problem is that, if we wanted to load all the modules in the project, the total cost would be O(modules^2) which is worse than the current one O(imports). Or put another way, the rebuild complexity would go from O(direct imports) to O(transitive imports).

Tradeoffs!

EDIT: The recursive calls to GetModIface would need to be replaced by calls to a hypothetical RefreshInterface build rule that blocks until the interface file on disk is fresh, regenerating it if needed. The tricky part of course is that, in order to check if the interface file is fresh with checkOldIface, we need to first load all the dependencies. So we end up in the same place where we started