performance - 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

它更快并使用恒定内存(没有额外的 IEnumerable s)。

我以为 F# 会生成一个 IEnumerable为 yield!在尾部位置，但显然不是。

编辑

spec confirms这个: {| yield! expr |}详述为 expr ，即子序列(递归或其他)不会合并为单个 IEnumerable .