Superlinear behavior with polymorphic recursion in runtime async

[jakobbotsch]

When trying to benchmark some generic instantiations for #126091 (comment) my usual method of polymorphic recursion using two generic type parameters hit some non-linear behavior. We should investigate why that happens.

[jakobbotsch]

using System;
using System.Diagnostics;
using System.Threading.Tasks;

namespace AsyncMicro;

public class Program
{
    static void Main()
    {
        for (int n = 0; n < 32; n++)
        {
            Stopwatch timer = Stopwatch.StartNew();
            new Program().Recurse<int, int>(n).GetAwaiter().GetResult();
            Console.WriteLine("n={0:00} Took {1} ms", n, timer.ElapsedMilliseconds);
        }
    }

    private async Task<V<T1, T2>> Recurse<T1, T2>(int n)
    {
        await Task.Yield();

        if (n != 0)
        {
            Task t;
            if (n % 2 == 0)
            {
                t = Recurse<V<T1, T2>, T2>(n - 1);
            }
            else
            {
                t = Recurse<T1, V<T1, T2>>(n - 1);
            }

            await t;
        }

        return default;
    }

    private struct V<T1, T2>
    {
        public int X;
    }
}

n=00 Took 6 ms
n=01 Took 2 ms
n=02 Took 4 ms
n=03 Took 4 ms
n=04 Took 4 ms
n=05 Took 4 ms
n=06 Took 4 ms
n=07 Took 5 ms
n=08 Took 5 ms
n=09 Took 4 ms
n=10 Took 5 ms
n=11 Took 6 ms
n=12 Took 6 ms
n=13 Took 7 ms
n=14 Took 9 ms
n=15 Took 11 ms
n=16 Took 16 ms
n=17 Took 23 ms
n=18 Took 35 ms
n=19 Took 53 ms
n=20 Took 93 ms
n=21 Took 132 ms
n=22 Took 212 ms
n=23 Took 338 ms
n=24 Took 555 ms
n=25 Took 868 ms
n=26 Took 1432 ms
n=27 Took 2295 ms
n=28 Took 3716 ms
n=29 Took 6199 ms
n=30 Took 10164 ms
n=31 Took 15622 ms

[dotnet-policy-service]

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

[jakobbotsch]

When breaking in I stop here:

runtime/src/coreclr/vm/readytoruninfo.cpp

Lines 1270 to 1277 in e1d19fe

	// Async variants are stored in the instance methods table
	if (pMD->HasClassOrMethodInstantiation()
	|| pMD->IsAsyncVariantMethod())
	{
	if (m_instMethodEntryPoints.IsNull())
	goto done;
	NativeHashtable::Enumerator lookup = m_instMethodEntryPoints.Lookup(GetVersionResilientMethodHashCode(pMD));

I think computing this hash code is exponential in the depth of the generic instantiation. Perhaps it is a non-issue.

[jakobbotsch]

@davidwrighton What do you think about the above? One possibility would be memoizing the intermediate type hash codes once we hit some budget.

[davidwrighton]

Yes I think caching these hash codes isn't a bad idea. I think we may have the space available on the auxiliary structure. I'll take a look on Monday.