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

[sandreenko]

In this function:

runtime/src/coreclr/src/jit/layout.cpp

Line 429 in e2e43f4

bool ClassLayout::AreCompatible(const ClassLayout* layout1, const ClassLayout* layout2)

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+);

Test template

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

[TaurahSP]

Hi, can i take this up as a first time contribution

[sandreenko]

@TaurahSP sure, you are welcome! Feel free to ask if something is not clear about this issue or about runtime workflow.

[surya99]

Hi @sandreenko sandreenko,
As I understand from the above issue that you are telling when we have two structure but having large size then at the time of compilation it's taking time to complete.
Is my understanding correct ?

Thanks
Sk

[sandreenko]

Is my understanding correct?

Kind of, you need to meet several rare conditions in one method to see significant compilation time spent in ClassLayout::AreCompatible, look at the test template that I wrote for references. However, if you create an artificial test that meets all these conditions you can see the issue with the current algorithm.

[TaurahSP]

@sandreenko The test has been created but can you point me out the right directory for it.

I have currently created it in "dotnetruntime\runtime\src\tests\JIT\Performance\CodeQuality\Layout\AreCompatible.cs"

[sandreenko]

@sandreenko The test has been created but can you point me out the right directory for it.

I would put it under https://github.com/dotnet/runtime/tree/master/src/tests/JIT/opt/Structs . I do not think it should be under CodeQuality because it does not affect the generated asm CQ.

Do you see quadratic compilation time for your test?