Skip to content

ILC: Virtual method resolution likely uses exponential algorithm #103034

@filipnavara

Description

@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:
image

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    area-NativeAOT-coreclrin-prThere is an active PR which will close this issue when it is merged

    Type

    No type

    Projects

    Status

    No status

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions