Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider avoiding irreducible loops in async codegen #67774

Closed
jcouv opened this issue Apr 12, 2023 · 2 comments
Closed

Consider avoiding irreducible loops in async codegen #67774

jcouv opened this issue Apr 12, 2023 · 2 comments
Assignees
Labels
Area-Compilers Code Gen Quality Room for improvement in the quality of the compiler's generated code Resolution-Duplicate The described behavior is tracked in another issue

Comments

@jcouv
Copy link
Member

jcouv commented Apr 12, 2023

Whenever there is an await inside of a loop (see example below), the resulting IL will have a loop with two ways to enter the loop: 1. from the start, 2. after resumption of the await. This causes problems for the JIT.

Normally, the JIT can pull some common logic out of loops ("loop invariant code motion") and perform some optimizations with variables that it can prove progress a certain way ("induction variable analysis"). But with irreducible loops (loops with multiple entry points) it cannot perform those optimizations.

From discussion with @AndyAyersMS (as part of his investigation work), a few options came up:

  1. the traditional solution to irreducible loops in the literature is some code duplication. Aside from inflating the IL, this seems unbounded (need to duplicate arbitrary code) and I worry about some kind of quadratic explosion (loop with multiple awaits)
  2. runtime/JIT deals with irreducible loop somehow
  3. runtime adds primitives for async/await (relates to previous discussion on optimizing async methods)
  4. compiler codegen forces resumption path to go through start of the loop (similar to "try" lowering)

I want to document proposal 4 in more details. We would want to validate the expected benefits (benchmarks of run time) and measure the downside (slightly inflated IL). Some kind of prototype could be useful to explore this further.

Proposed codegen change

TL;DR: when resuming after an await, you'd jump to the start of the loop logic, enter normally, and then have another switch just inside the loop that jumps to the right resumption point.

Background

When the compiler lowers an await, the await itself results in a little block like:

{
  // start async computation
  // save state
  return;
  resumptionLabel:
  // restore state and get result
}

Then at the top of the method we'll also add a switch dispatch:

switch (state)
{
  case await1:
    goto resumptionLabel;
  ...
}

But when the await is inside of a try this switch dispatch isn't allowed (can't jump into the middle of a try).
To deal with this, the compiler will produce two switch dispatches: one at the top of the method and another one at the top of the try block.

switch (state)
{
  case await1:
    goto tryLabel;
  ...
}
...
tryLabel:
try
{
  switch (state)
  {
    case await1:
      goto resumptionLabel;
    ...
  }

  ... lowered code for await, including resumptionLabel
}

This ensures that we only enter try blocks from the start.
You can find more background details including examples here.

Proposal for loops

We could use a similar lowering strategy for loops, where we'd intentionally avoid jumping into the middle of a loop with our switch dispatches.
This means that loops would only be entered through the start.

Example

using System.Diagnostics;

class Program
{
    static readonly CancellationTokenSource s_cts = new CancellationTokenSource();

    static readonly HttpClient s_client = new HttpClient
    {
        MaxResponseContentBufferSize = 1_000_000
    };

    static readonly IEnumerable<string> s_urlList = new string[]
    {
            "https://docs.microsoft.com",
            "https://docs.microsoft.com/aspnet/core",
            "https://docs.microsoft.com/azure",
            "https://docs.microsoft.com/azure/devops",
            "https://docs.microsoft.com/dotnet",
            "https://docs.microsoft.com/dynamics365",
            "https://docs.microsoft.com/education",
            "https://docs.microsoft.com/enterprise-mobility-security",
            "https://docs.microsoft.com/gaming",
            "https://docs.microsoft.com/graph",
            "https://docs.microsoft.com/microsoft-365",
            "https://docs.microsoft.com/office",
            "https://docs.microsoft.com/powershell",
            "https://docs.microsoft.com/sql",
            "https://docs.microsoft.com/surface",
            "https://docs.microsoft.com/system-center",
            "https://docs.microsoft.com/visualstudio",
            "https://docs.microsoft.com/windows",
            "https://docs.microsoft.com/xamarin"
    };

    static async Task Main()
    {
        Console.WriteLine("Application started.");

        try
        {
            s_cts.CancelAfter(3500);

            await SumPageSizesAsync();
        }
        catch (OperationCanceledException)
        {
            Console.WriteLine("\nTasks cancelled: timed out.\n");
        }
        finally
        {
            s_cts.Dispose();
        }

        Console.WriteLine("Application ending.");
    }

    static async Task SumPageSizesAsync()
    {
        var stopwatch = Stopwatch.StartNew();

        int total = 0;
        foreach (string url in s_urlList)
        {
            int contentLength = await ProcessUrlAsync(url, s_client, s_cts.Token); // <-- await inside loop
            total += contentLength;
        }

        stopwatch. Stop();

        Console.WriteLine($"\nTotal bytes returned:  {total:#,#}");
        Console.WriteLine($"Elapsed time:          {stopwatch.Elapsed}\n");
    }

    static async Task<int> ProcessUrlAsync(string url, HttpClient client, CancellationToken token)
    {
        HttpResponseMessage response = await client.GetAsync(url, token);
        byte[] content = await response.Content.ReadAsByteArrayAsync(token);
        Console.WriteLine($"{url,-60} {content.Length,10:#,#}");

        return content. Length;
    }
}
			try
			{
				if (num != 0)
				{
                    // resume after await
					goto IL_00b8;
				}
                // first time through
				TaskAwaiter<int> awaiter = <>u__1;
				<>u__1 = default(TaskAwaiter<int>);
				num = (<>1__state = -1);
				goto IL_00a2;
				IL_00b8:

				if (<>7__wrap3.MoveNext())
				{
					awaiter = ProcessUrlAsync(<>7__wrap3.Current, s_client, s_cts.Token).GetAwaiter();
					if (!awaiter.IsCompleted)
					{
						num = (<>1__state = 0);
						<>u__1 = awaiter;
						<>t__builder.AwaitUnsafeOnCompleted(ref awaiter, ref this);
						return;
					}
					goto IL_00a2;
				}
				goto end_IL_002d;
				IL_00a2:
				int contentLength = awaiter.GetResult();
				<total>5__3 += contentLength;
				goto IL_00b8;
				end_IL_002d:;
			}
@jcouv jcouv self-assigned this Apr 12, 2023
@dotnet-issue-labeler dotnet-issue-labeler bot added Area-Compilers untriaged Issues and PRs which have not yet been triaged by a lead labels Apr 12, 2023
@jcouv jcouv added Code Gen Quality Room for improvement in the quality of the compiler's generated code and removed untriaged Issues and PRs which have not yet been triaged by a lead labels Apr 12, 2023
@AndyAyersMS
Copy link
Member

Realized @benaadams also noted this a while back: #39814

@jcouv
Copy link
Member Author

jcouv commented Apr 27, 2023

Thanks. Closing in favor of #39814
I'll add some information there

@jcouv jcouv closed this as not planned Won't fix, can't repro, duplicate, stale Apr 27, 2023
@jcouv jcouv added the Resolution-Duplicate The described behavior is tracked in another issue label Apr 27, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Area-Compilers Code Gen Quality Room for improvement in the quality of the compiler's generated code Resolution-Duplicate The described behavior is tracked in another issue
Projects
None yet
Development

No branches or pull requests

2 participants