While loop pattern in Async builder allocates a lot

[Liminiens]

Repro steps

The problem is in this code pattern:

async {
  let mutable i = 0
  while i < "some length" do
    i <- i + 1
  return i
 }

Benchmark code:

[<SimpleJob(runtimeMoniker = RuntimeMoniker.NetCoreApp31, launchCount = 3, warmupCount = 3, targetCount = 5)>]
[<GcServer(true)>]
[<MemoryDiagnoser>]
[<MarkdownExporterAttribute.GitHub>]
type Benchs() =

  [<Params(100, 200, 300, 400, 500, 1000, 2000, 3000, 10000)>]
  member val Length = 0 with get, set

  [<Benchmark>]
  member x.Run() =
    async {
      let mutable i = 0
      while i < x.Length do
        i <- i + 1
      return i
    } |> Async.StartAsTask

Result:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-3770K CPU 3.50GHz (Ivy Bridge), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT DEBUG
  Job-VRTOUB : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT

Runtime=.NET Core 3.1  Server=True  IterationCount=5  
LaunchCount=3  WarmupCount=3  

Method	Length	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
Run	100	8.443 us	1.0161 us	0.9504 us	0.2136	-	-	7.59 KB
Run	200	19.149 us	1.5007 us	1.4037 us	0.3662	-	-	13.94 KB
Run	300	21.909 us	3.3153 us	3.1011 us	0.5493	-	-	20.25 KB
Run	400	29.473 us	0.5453 us	0.5101 us	0.7324	-	-	26.55 KB
Run	500	34.433 us	1.2715 us	1.1893 us	0.9155	-	-	32.86 KB
Run	1000	59.594 us	2.5140 us	2.3516 us	1.7090	-	-	64.38 KB
Run	2000	104.767 us	4.0733 us	3.8102 us	3.5400	-	-	127.43 KB
Run	3000	154.497 us	2.4013 us	2.2462 us	5.1270	-	-	190.48 KB
Run	10000	484.288 us	19.7594 us	18.4830 us	17.0898	-	-	631.8 KB

Essentially the problem is that the loop internally turns into this:

Expected behavior

Allocations shouldn't depend(?) on the number of loops.

Actual behavior

Allocations depend on the number of loops.

Known workarounds

Using recursion:

async {
  let mutable i = 0
  let rec while' () =
     if i = "some length"
     then i
     else
       i <- i + 1
       while' ()
  return while' ()
}

Related information

Using TaskBuilder.fs helps, but not that much:

https://gist.github.com/grishace/83f540cb299867e94145551931fcbcb1

.NET Core 3.1

[cartermp]

The comment in the code appears to be lying 🙂 https://github.com/dotnet/fsharp/blob/master/src/fsharp/FSharp.Core/async.fs#L588

cc @dsyme

[dsyme]

Note that synchronous loops can be made efficient like this:

async {
  let mutable i = 0
  do 
     while i < "some length" do
         i <- i + 1
  return i
 }

[dsyme]

I took a stab at eliminating the allocations in async while/for loops. The technique works, but performance is slower, I need to work out why:

BEFORE:

AFTER:

[TheAngryByrd]

This is also an issue in Resumable CEs such as IcedTasks. CancellableTask loop allocate horribly without the do block trick. . Adding an async bind with Task.Yield() is really bad for CancellableTask about 67000x more allocations compared to the Task Baseline

    [<Benchmark>]
    member x.CancellableTask() =
        let cTask = cancellableTask {
            let mutable i = 0

            while i < x.Length do
                i <- i + 1

            return i
        }

        cTask CancellationToken.None


    [<Benchmark>]
    member x.CancellableTask_syncDoBlockTrick() =
        let cTask = cancellableTask {
            let mutable i = 0

            do
                while i < x.Length do
                    i <- i + 1

            return i
        }

        cTask CancellationToken.None


    [<Benchmark>]
    member x.CancellableTask_async() =
        let cTask = cancellableTask {
            let mutable i = 0

            while i < x.Length do
                do! Task.Yield()
                i <- i + 1

            return i
        }

        cTask CancellationToken.None

[TheAngryByrd]

So I think I'm actually running into #12839 (comment) however I'm not seeing the FS3511 This state machine is not statically compilable message. It's just creating the dynamic version sometimes and very temperamental. To verify this further I made sure the RunDynamic portion just threw an exception and I verified it in dotPeek.

    [Benchmark(147, "C:\\Users\\jimmy\\Repositories\\public\\TheAngryByrd\\IcedTasks\\benchmarks\\FSharpBenchmarks\\LoopBenchmarks.fs")]
    public Task<int> CancellableTask()
    {
      \u0024LoopBenchmarks.cTask\u0040149 cTask149 = new \u0024LoopBenchmarks.cTask\u0040149();
      ref \u0024LoopBenchmarks.cTask\u0040149 local1 = ref cTask149;
      local1.x = this;
      \u0024LoopBenchmarks.cTask\u0040149 sm = local1;
      FSharpFunc<CancellationToken, Task<int>> fsharpFunc = (FSharpFunc<CancellationToken, Task<int>>) new \u0024LoopBenchmarks.cTask\u0040149\u002D1(sm);
      CancellationToken none = CancellationToken.None;
      ref CancellationToken local2 = ref none;
      return fsharpFunc.Invoke(local2);
    }

    [Benchmark(163, "C:\\Users\\jimmy\\Repositories\\public\\TheAngryByrd\\IcedTasks\\benchmarks\\FSharpBenchmarks\\LoopBenchmarks.fs")]
    public Task<int> CancellableTask2()
    {
      ResumableCode<CancellableTasks.CancellableTaskStateMachineData<int>, int> resumableCode = new ResumableCode<CancellableTasks.CancellableTaskStateMachineData<int>, int>((object) new \u0024LoopBenchmarks.CancellableTask2\u0040165(this), __methodptr(Invoke));
      if (false)
        return ((FSharpFunc<CancellationToken, Task<int>>) null).Invoke(CancellationToken.None);
      throw new Exception("sorry lol");
    }