Use disjoint-set-union for `ClassLayout::AreCompatible`.

In this function: https://github.com/dotnet/runtime/blob/e2e43f44f1032780fa7c2bb965153c9da615c3d0/src/coreclr/src/jit/layout.cpp#L429

we are iteration over all slots if two layouts have same size and both have GC pointers, it could work slowly (number of fields * number of calls to this function) on some exotic tests, the task is to construct such a test and use DSU to fix the time complexity of the algorithm.

Steps:

• Create a test where there are 2 structs with the same size, both with GC pointers, with huge number of fields (N = 1000+) and use many operations of copies between them (M = 1000+);

public struct Str1
{
    public int i1;
    public Object o; // at least one gc field.
    // add many more bytes of fields here.
}

public struct Str2
{
    public int j1;
    public Object o; // at least one gc field.
    // add the same number of bytes here.
}

public static int Test1()
{
    i = 0;

    Str1 str1 = new Str1();
    // add many copies from one struct to another, check that 
    // C# compiler to IL (Roslyn) does not delete them.
    Str2 str2 = Unsafe.As<Str1, Str2>(ref str1); 
    
}

• measure jit compilation time (the time will include N*M operations in AreCompatible), confirm that it has quadratic time complexity;

• Add ClassLayout* m_dsuParent to ClassLayout and implement DSU, when you create a new layout using the existing naive algorithm of comparing slots to find if the new layout should be united with any preexisting layout (note: do not compare with a layout a if its m_dsuParent is not equal to a);

• Change AreCompatible to return layout1->m_dsuParent == layout2->m_dsuParent;

• Make an optimization to create DSU only when we have calls to AreCompatible (extract InitDSU, add static bool s_DSUinitialized, check it in AreCompatible).

• Measure JitCompilationTime on System.Private.CoreLib and other tests to understand if the optimization should be merged and used by default

Feel free to ask questions if something is not clear.

Right now we don't have examples where this issue affects JitCompilationTime but I am planning to add more usages of AreCompatible in the future.

category:implementation theme:throughput skill-level:beginner cost:medium impact:small