F#: generated IL code for seq{} vs other computational workflows

Question

When I compare IL code that F# generates for seq{} expressions vs that for user-defined computational workflows, it's quite obvious that seq{} is implemented very differently: it generates a state machine similar to the once C# uses for its' iterator methods. User-defined workflows, on the other hand, use the corresponding builder object as you'd expect.

So I am wondering - why the difference?

Is this for historical reasons, e.g. "seq was there before workflows"?
Or, is there significant performance to be gained?
Some other reason?

Answer 1

This is an optimization performed by the F# compiler. As far as I know, it has actually been implemented later - F# compiler first had list comprehensions, then a general-purpose version of computation expressions (also used for seq { ... }) but that was less efficient, so the optimization was added in some later version.

The main reason is that this removes many allocations and indirections. Let's say you have something like:

seq { for i in input do
        yield i
        yield i * 10 }

When using computation expressions, this gets translated to something like:

seq.Delay(fun () -> seq.For(input, fun i -> 
  seq.Combine(seq.Yield(i), seq.Delay(fun () -> seq.Yield(i * 10)))))

There is a couple of function allocations and the For loop always needs to invoke the lambda function. The optimization turns this into a state machine (similar to the C# state machine), so the MoveNext() operation on the generated enumerator just mutates some state of the class and then returns...

You can easily compare the performance by defining a custom computation builder for sequences:

type MSeqBuilder() = 
  member x.For(en, f) = Seq.collect f en
  member x.Yield(v) = Seq.singleton v
  member x.Delay(f) = Seq.delay f
  member x.Combine(a, b) = Seq.concat [a; b]
let mseq = MSeqBuilder()
let input = [| 1 .. 100 |]

Now we can test this (using #time in F# interactive):

for i in 0 .. 10000 do 
  mseq { for x in input do
           yield x
           yield x * 10 }
  |> Seq.length |> ignore

On my computer, this takes 2.644sec when using the custom mseq builder but only 0.065sec when using the built-in optimized seq expression. So the optimization makes sequence expressions significantly more efficient.

Answer 2

Historically, computations expressions ("workflows") were a generalization of sequence expressions: http://blogs.msdn.com/b/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx.

But, the answer is certainly that there is significant performance to be gained. I can't turn up any solid links (though there is a mention of "optimizations related to 'when' filters in sequence expressions" in http://blogs.msdn.com/b/dsyme/archive/2007/11/30/full-release-notes-for-f-1-9-3-7.aspx), but I do recall that this was an optimization that made its way in at some point in time. I'd like to say that the benefit is self-evident: sequence expressions are a "core" language feature and deserving of any optimizations that can be made.

Similarly, you'll see that certain tail-recursive functions will be optimized in to loops, rather than tail calls.