Why is Task.WhenAny so slow when called many times against the same TaskCompletionSource?

If a class has a member TaskCompletionSource<TResult> m_tcs with a long lifetime, and if Task.WhenAny is called with m_tcs.Task as one of its arguments, performance seems to degrade exponentially when the number of calls surpasses 50,000 calls or so.

Why is it so slow in this case? Might there be an alternative that operates faster but without using 4x more memory?

My thought is that Task.WhenAny is likely adding and removing so many continuations to and from m_tcs.Task and somewhere in there it results in a complexity of O(N²).

I found a more performant alternative by wrapping the TCS in an async function that awaits m_tcs.Task. It uses about 4x the memory but runs much faster beyond 20,000 iterations.

Sample code below (for accurate results, compile and run the .exe directly without the debugger attached). Note that WhenAnyMemberTcsDirect has the performance issue, WhenAnyMemberTcsIndirect is the faster alternative, and WhenAnyLocalTcs is a baseline for comparison:

using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading.Tasks;

public class WithTcs
{
    // long-lived TaskCompletionSource
    private readonly TaskCompletionSource<bool> m_tcs = new TaskCompletionSource<bool>();

    // this has performance issues for large N - O(N^2)
    public async Task WhenAnyMemberTcsDirectAsync(Task task)
    {
        await await Task.WhenAny(task, m_tcs.Task).ConfigureAwait(false);
    }

    // performs faster - O(N), but uses 4x memory
    public async Task WhenAnyMemberTcsIndirectAsync(Task task)
    {
        await await Task.WhenAny(task, AwaitTcsTaskAsync(m_tcs)).ConfigureAwait(false);
    }

    private async Task<TResult> AwaitTcsTaskAsync<TResult>(TaskCompletionSource<TResult> tcs)
    {
        return await tcs.Task.ConfigureAwait(false);
    }

    // baseline for comparison using short-lived TCS
    public async Task WhenAnyLocalTcsAsync(Task task)
    {
        var tcs = new TaskCompletionSource<bool>();
        await await Task.WhenAny(task, tcs.Task).ConfigureAwait(false);
    }
}

class Program
{
    static void Main(string[] args)
    {
        show_warning_if_debugger_attached();

        MainAsync().GetAwaiter().GetResult();

        show_warning_if_debugger_attached();
        Console.ReadLine();
    }

    static async Task MainAsync()
    {
        const int n = 100000;

        Console.WriteLine("Running Task.WhenAny tests ({0:#,0} iterations)", n);
        Console.WriteLine();

        await WhenAnyLocalTcs(n).ConfigureAwait(false);

        await Task.Delay(1000).ConfigureAwait(false);

        await WhenAnyMemberTcsIndirect(n).ConfigureAwait(false);

        await Task.Delay(1000).ConfigureAwait(false);

        await WhenAnyMemberTcsDirect(n).ConfigureAwait(false);
    }

    static Task WhenAnyLocalTcs(int n)
    {
        Func<WithTcs, Task, Task> function =
            (instance, task) => instance.WhenAnyLocalTcsAsync(task);

        return RunTestAsync(n, function);
    }

    static Task WhenAnyMemberTcsIndirect(int n)
    {
        Func<WithTcs, Task, Task> function =
            (instance, task) => instance.WhenAnyMemberTcsIndirectAsync(task);

        return RunTestAsync(n, function);
    }

    static Task WhenAnyMemberTcsDirect(int n)
    {
        Func<WithTcs, Task, Task> function =
            (instance, task) => instance.WhenAnyMemberTcsDirectAsync(task);

        return RunTestAsync(n, function);
    }

    static async Task RunTestAsync(int n, Func<WithTcs, Task, Task> function, [CallerMemberName] string name = "")
    {
        Console.WriteLine(name);

        var tasks = new Task[n];
        var sw = new Stopwatch();
        var startBytes = GC.GetTotalMemory(true);
        sw.Start();

        var instance = new WithTcs();
        var step = n / 78;
        for (int i = 0; i < n; i++)
        {
            var iTemp = i;
            Task primaryTask = Task.Run(() => { if (iTemp % step == 0) Console.Write("."); });
            tasks[i] = function(instance, primaryTask);
        }

        await Task.WhenAll(tasks).ConfigureAwait(false);
        Console.WriteLine();

        var endBytes = GC.GetTotalMemory(true);
        sw.Stop();
        GC.KeepAlive(instance);
        GC.KeepAlive(tasks);

        Console.WriteLine("  Time: {0,7:#,0} ms, Memory: {1,10:#,0} bytes", sw.ElapsedMilliseconds, endBytes - startBytes);
        Console.WriteLine();
    }

    static void show_warning_if_debugger_attached()
    {
        if (Debugger.IsAttached)
            Console.WriteLine("WARNING: running with the debugger attached may result in inaccurate results\r\n".ToUpper());
    }
}

Sample results:

Iterations | WhenAny* Method   | Time (ms) | Memory (bytes)
---------: | ----------------- | --------: | -------------:
     1,000 | LocalTcs          |        21 |         58,248
     1,000 | MemberTcsIndirect |        54 |        217,268
     1,000 | MemberTcsDirect   |        21 |         52,496
    10,000 | LocalTcs          |        91 |        545,836
    10,000 | MemberTcsIndirect |        98 |      2,141,836
    10,000 | MemberTcsDirect   |       140 |        545,640
   100,000 | LocalTcs          |       210 |      4,898,512
   100,000 | MemberTcsIndirect |       502 |     21,426,316
   100,000 | MemberTcsDirect   |    14,090 |      5,085,396
   200,000 | LocalTcs          |       366 |      9,630,872
   200,000 | MemberTcsIndirect |       659 |     41,450,916
   200,000 | MemberTcsDirect   |    42,599 |     10,069,248
   500,000 | LocalTcs          |       808 |     23,670,492
   500,000 | MemberTcsIndirect |     1,906 |     97,339,192
   500,000 | MemberTcsDirect   |   288,373 |     24,968,436
 1,000,000 | LocalTcs          |     1,642 |     47,272,744
 1,000,000 | MemberTcsIndirect |     3,149 |    200,480,888
 1,000,000 | MemberTcsDirect   | 1,268,030 |     48,064,772

Note: targeting .NET 4.6.2 Release (Any CPU), tested on Windows 7 SP1 64-bit, Intel Core i7-4770.