Comparing Continuations in C# and F# Part 2

In my last post I went over the differences between using a continuation in F# and C#.  As it turns out I was right about the limits and symptoms but wrong about the reason. 

The F# code does indeed generate tail calls for part of the continuation.  However this is only a very small portion of the actual code and is in fact only generated for the call in the empty case.  I misread this function to be the call for the overall continuation.  Instead it is the function for the entire “inner” lambda.

So why does F# perform differently than C# in this scenario?

Andrew Kennedy pointed out that F# will actually transform the “inner” function into a loop.  In affect the code generated looks like the following.

     TypeFunc func = this._self3;
    while (true)
    {
        if (!this.e.MoveNext())
        {
            break;
        }
        A cur = this.e.Current;
        cont = new Program.clo@9<U V, A ,>(this.combine, cont, cur);
    }
    return cont.Invoke(this.acc);

The actual transformation into a loop is what is preventing F# from overflowing the stack here.  Iteration incurs no stack overhead in this case. 

Even more interesting is that the tail opcode is quite simply ignored when dealing with un-trusted code.  It therefore cannot be relied on to generate performant code in all scenarios.

Comments

• Anonymous
  November 11, 2008
  PingBack from http://mstechnews.info/2008/11/comparing-continuations-in-c-and-f-part-2/

• Anonymous
  November 11, 2008
  The stack is fine, but I pondered a bit about what the consequences are for the heap. The conclusion is that all values from the sequence are placed onto the heap and not in the most economic way. So I rewrote the FoldRight function as: open System.Collections.Generic let FoldRight combine (sequence:seq<'a>) acc =  let list = new List<_>(sequence)  let rec reduce i a =    if i=0 then a else    combine list.[i-1] a    |> reduce (i-1)  reduce list.Count acc Tests confirm that this is not only more memory-efficient but also faster.

• Anonymous
  November 12, 2008
  @brilsmurf Would you mind posting your tests?  The speed of your test can alter drastically based on the type of the sequence and hence the argument you passed into List<T>. There are really two main scenarios for List<T>.ctor().  In the case the parameter implements ICollection<T> the code is fairly efficeient. It will pre-allocated an array of the appropriate size and then do a quick ICollection<T>.CopyTo method. In the case the parameter does not implement ICollection<T>, the code is a lot less efficient.  It will simply call List<T>.Add() in a loop and resize the array dynamically.  This will start with a length of 4 and double every time there is not enough memory.  It will also have to copy the contents of the old array at every allocation. In the case of a 1,000,000 element array this results in roughly 18 allocations and copies (each one twice as big as the last).  I don't think this will be more memory efficient for large sequence based collections. Especially in languages like F# where enumerable based sequences are common, it would be a mistake to assume they are backed by an actual ICollection<T>.   Another general issue is the List<T> solution requires contiguous memory because the underlying backing is an array.  The contituation sample does not because it essentially building up a linked list which can be represented in discrete elements.The total amount of contigous memory is count*size of type.  In a production app you are much less likely to have huge chunks of contiguous memory than non-contiguous memory.