ILC: Virtual method resolution likely uses exponential algorithm

[filipnavara]

When compile a large application that uses WinForms there are many classes that derive from System.Windows.Forms.Control/Form and have class hierarchy depth around 12-13 levels deep.

This hits a code path in ILC type system that doesn't scale well:

Bulk of the time in the marking phase (several minutes) is spent in Internal.TypeSystem.MetadataVirtualMethodAlgorithm.ResolveInterfaceMethodToVirtualMethodOnType(MethodDesc, MetadataType). It recursively calls into itself through ResolveInterfaceMethodToVirtualMethodOnTypeRecursive. ResolveInterfaceMethodToVirtualMethodOnTypeRecursive also walks the class hierarchy upwards. This results in an algorithm that doesn't scale well with the class hierarchy depth.

Perhaps there's a way to short-circuit it to prevent double recursion? Or maybe the algorithm can be rewritten in more efficient manner? Dynamic programming? I am open to ideas.

Fixing this is likely to cut the compilation time by several minutes for this particular application. I expect it to affect every WinForms application (once the scenario is supported) in one way or another.

[dotnet-policy-service[bot]]

Tagging subscribers to this area: @agocke, @MichalStrehovsky, @jkotas See info in area-owners.md if you want to be subscribed.

[filipnavara]

One thing I forgot to note is that this is happening in the non-parallelized mark part of the scanning. There's likely a brute force option to precompute some of this information in parallel, but I would consider it a last resort.

[MichalStrehovsky]

What we generally do is "do the best to avoid calling into this multiple times". I made multiple fixes in the past to reduce number of times we need to resolve virtual/interface methods. There's probably still opportunities left.

I tried to introduce a straight cache in front of this in the past, it just made things worse. I can see how a cache could make the WinForms case better, but it will probably regress any other normal app where this is not the hottest thing.

[filipnavara]

This accounts for somewhere between 30%-50% of the compilation time for our app (likely > 3 minutes) so it's quite a huge problematic spot. The compiler basically spends > 0.01 seconds for each type derived from Control/Form in MightHaveInterfaceDispatchMap in our case, which quickly adds up, especially since this phase is not running in parallel.

I understand that straightforward cache may make things worse but the algorithm itself seems to be doing some extremely bad tree traversal (with some pruning).

[filipnavara]

Throwing out a wild idea:

--- a/src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/DependencyAnalysis/InterfaceDispatchMapNode.cs
+++ b/src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/DependencyAnalysis/InterfaceDispatchMapNode.cs
@@ -89,7 +89,7 @@ public static bool MightHaveInterfaceDispatchMap(TypeDesc type, NodeFactory fact

             DefType declType = type.GetClosestDefType();

-            for (int interfaceIndex = 0; interfaceIndex < declType.RuntimeInterfaces.Length; interfaceIndex++)
+            for (int interfaceIndex = declType.RuntimeInterfaces.Length - 1; interfaceIndex >= 0; interfaceIndex--)
             {
                 DefType interfaceType = declType.RuntimeInterfaces[interfaceIndex];
                 InstantiatedType interfaceOnDefinitionType = interfaceType.IsTypeDefinition ?

This seems to save around 1-2 minutes on the compilation time with some benchmarked invocations of MightHaveInterfaceDispatchMap showing 9x improvements. Presumably the last interfaces on the list are more likely to be coming from the less nested classes and allow short circuiting earlier in most cases?

[filipnavara]

Second naive idea:

--- a/src/coreclr/tools/Common/TypeSystem/Common/MetadataVirtualMethodAlgorithm.cs
+++ b/src/coreclr/tools/Common/TypeSystem/Common/MetadataVirtualMethodAlgorithm.cs
@@ -610,7 +610,7 @@ public override MethodDesc ResolveVariantInterfaceMethodToStaticVirtualMethodOnT
         //    function returns null if the interface method implementation is not defined by the current type in
         //    the hierarchy.For variance to work correctly, this requires that interfaces be queried in correct order.
         //    See current interface call resolution for details on how that happens.
-        private static MethodDesc ResolveInterfaceMethodToVirtualMethodOnType(MethodDesc interfaceMethod, MetadataType currentType)
+        private static MethodDesc ResolveInterfaceMethodToVirtualMethodOnType(MethodDesc interfaceMethod, MetadataType currentType, bool returnRecursive = false)
         {
             Debug.Assert(!interfaceMethod.Signature.IsStatic);

@@ -665,7 +665,7 @@ private static MethodDesc ResolveInterfaceMethodToVirtualMethodOnType(MethodDesc
                 MethodDesc baseClassImplementationOfInterfaceMethod = ResolveInterfaceMethodToVirtualMethodOnTypeRecursive(interfaceMethod, baseType);
                 if (baseClassImplementationOfInterfaceMethod != null)
                 {
-                    return null;
+                    return returnRecursive ? baseClassImplementationOfInterfaceMethod : null;
                 }
                 else
                 {
@@ -729,7 +729,7 @@ private static MethodDesc ResolveInterfaceMethodToVirtualMethodOnTypeRecursive(M
                     return null;
                 }

-                MethodDesc currentTypeInterfaceResolution = ResolveInterfaceMethodToVirtualMethodOnType(interfaceMethod, currentType);
+                MethodDesc currentTypeInterfaceResolution = ResolveInterfaceMethodToVirtualMethodOnType(interfaceMethod, currentType, returnRecursive: true);
                 if (currentTypeInterfaceResolution != null)
                     return currentTypeInterfaceResolution;

[MichalStrehovsky]

The first one looks reasonable to me. The second one is a change to the virtual method resolution algorithm so I can't really comment on that.

[filipnavara]

The idea behind the second one is that you are already in an outer loop which goes up in the class hierarchy so the result should essentially not change and you don't have to recompute it time and again. I'm not sure how sound the idea is and who would be the right person to review it. As a smoke test I can run the compilation with both code paths and check that the returned values match.

(UPD: Smoke test passed.)