Unexpected iteration performance drop when recursive loops are used.

[pragmatrix]

Description

The problem appears when a recursive asyncSeq loop yields a number of elements and at least one async bind is inside the loop.

Repro steps

The performance drop can reproduced by the following test case:

open System.Diagnostics
open FSharp.Control

let rec generate cnt = asyncSeq {
    if cnt = 0 then () else
    let! v = async.Return 1
    yield v
    yield! generate (cnt-1)
}

[1000;2000;4000]
|> List.iter (fun numbers ->
    let sw = Stopwatch.StartNew()
    generate numbers
    |> AsyncSeq.iter ignore
    |> Async.RunSynchronously
    printfn "%d: %A" numbers sw.Elapsed)

The function generate above yields cnt numberd (all '1's), and it produces the following output on my machine:

1000: 00:00:01.1934439
2000: 00:00:04.7116588
4000: 00:00:18.9604031

Expected behavior

The time it takes to iterate the asynchronous sequence should be proportional to the number of elements it generates.

Actual behavior

The performance seems to be about O(n^2) instead of O(n).

Known workarounds

Try to avoid recursion in all asyncSeq scenarios that may return more than a few hundred values.

Related information

I've tested Release builds of master and @eulerfx's perf branch with no noticable difference. A number of functions in AsyncSeq.fs use a similar looping pattern and might be affected, too.

[eulerfx]

Thanks, I'll take a deeper look. There are some inefficiencies in the way AsyncSeq is generated via computation syntax. Meanwhile, if you express your generator as follows:

let generate = 
  AsyncSeq.unfoldAsync (fun cnt -> async {
    if cnt = 0 then return None
    else
      let! v = async.Return 1
      return Some (v, cnt - 1) })

You should get much better performance.

[pragmatrix]

I've changed bindAsync to use generators in https://github.com/pragmatrix/FSharp.Control.AsyncSeq/commit/8e449786794dd8c5a2fd3097bac72fc4fb707b7f. This keeps the performance linear but may introduce a slight overall slowdown because of the additional allocations.

@eulerfx Does this align with your intentions to optimize AsyncSeq in computation expressions? If yes, I'd like to add a test case and prepare a PR.

[eulerfx]

Hey, that's looking good! One thing to look for is that the input sequence gets disposed as needed - the code above won't, but it should be possible to validate with a unit test.

[pragmatrix]

I'm not sure that it has to. As long bind is waiting for the async to return, there is no sequence to dispose, and immediately after that, the Goto ensures that AsyncEnumeratorGenerator picks up the followup sequence's Dispose().

What can be unit-tested is that finally handlers are called as expected: https://github.com/pragmatrix/FSharp.Control.AsyncSeq/commit/2394a0407c830adca0cac5d57ec38045bc12f585

However, I'm not sure how a reliable unit test for the performance improvement should look like.

[eulerfx]

We don't have anything very structured for tracking performance improvements. I've just been putting some code and notes in tests/FSharp.Control.AsyncSeq.Tests/AsyncSeqPerf.fsx so could be a place to start.

[eulerfx]

@pragmatrix I merged your changes in. Apologies, I wasn't sure how to pull them from your branch, so I copied them. Also started a generator for the collect operation. Didn't expose it yet, because I haven't seen it improve performance, but it should for other operations.

[pragmatrix]

@eulerfx Thanks, no worries, quite the opposite.