性能 – F#中嵌套序列涉及的开销

我需要对xml结构进行过多的模式匹配,所以我声明了一个表示xml节点的类型. xml是一个多树,我需要以某种方式迭代节点.为了使树可枚举,我使用嵌套序列推导.我的 XML永远不会太大,所以简单性在我的情况下胜过性能,但是下面的代码对于更大的输入有点危险,或者可以保持原样.

type ElementInfo = { Tag : string; Attributes : Map<string, string> }
type Contents = 
    | Nothing
    | String of string
    | Elements of Node list
and Node =
    | Element of ElementInfo * Contents
    | Comment of string
    member node.PreOrder = 
        seq {
            match node with
            | Element (_, Elements children) as parent -> yield parent; yield! children |> Seq.collect (fun child -> child.PreOrder)
            | singleNode -> yield singleNode
        }

我认为对Seq.collect的调用可能会导致它每次调用生成一个IEnumerable,所以我用for循环替换它,它产生相同的输出(通过ILSpy).

这让我很好奇所以我反编译了一个更简单的序列表达式,我希望它能够“扁平化”.

let rec infSeq n =
  seq {
    yield n
    yield! infSeq (n+1)
  }

生成序列中下一个元素的代码反编译为：

public override int GenerateNext(ref IEnumerable<int> next)
{
    switch (this.pc)
    {
    case 1:
        this.pc = 2;
        next = Test.infSeq(this.n + 1);
        return 2;
    case 2:
        this.pc = 3;
        break;
    case 3:
        break;
    default:
        this.pc = 1;
        this.current = this.n;
        return 1;
    }
    this.current = 0;
    return 0;
}

正如您所看到的,它以递归方式调用自身,每次都生成一个新的IEnumerable. FSI的快速测试

infSeq 0 |> Seq.take 10000000 |> Seq.length

你可以看到有很多GC：

> Real: 00:00:01.759, CPU: 00:00:01.762, GC gen0: 108, gen1: 107, gen2: 1

与C#版相比

public static IEnumerable<int> InfSeq(int n) {
    while (true) yield return n++;
}

在FSI：

> Real: 00:00:00.991, CPU: 00:00:00.998, GC gen0: 0, gen1: 0, gen2: 0

它更快并且使用恒定的内存(没有额外的IEnumerables).

我以为F#会为收益产生一个IEnumerable！处于尾部位置,但显然不是.

编辑

spec confirms这个：{|让！ expr |}被详细描述为expr,也就是说,子序列(递归或其他)不会合并到单个IEnumerable中.