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

Question

我需要对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
        }

Answer 1

我认为调用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的yield!位置,但显然不是.

编辑

的规格证实这一点:{| yield! expr |}阐述为expr,即,子序列(递归或其他方式)未合并成一个单一的IEnumerable.