performance - 为什么构建/拼接 F# 引用如此缓慢？

Question

似乎是通过<@ @> 建立报价语法非常低效。例如创建一个整数列表

let q1 = List.foldBack (fun n acc -> <@ n :: %acc @>) [1..100000] <@ [] @>
Real: 00:00:05.714, CPU: 00:00:05.937, GC gen0: 234, gen1: 47, gen2: 1

上面的代码不仅运行很慢而且内存性能也很差
相比之下，以下更快，但在内存方面仍然很差

let q2 = 
    let (NewUnionCase (cons, [_;NewUnionCase (nil, [])])) = <@ [1] @>
    List.foldBack (fun n acc -> Expr.NewUnionCase(cons, [ <@ n @>; acc])) [1..100000] (Expr.NewUnionCase(nil, []))
Real: 00:00:02.352, CPU: 00:00:02.343, GC gen0: 296, gen1: 10, gen2: 0

最后，使用普通的旧 Expr明显更好(但仍然没有我希望的那么快)

let q3 = 
    let (NewUnionCase (cons, [_;NewUnionCase (nil, [])])) = <@ [1] @>
    List.foldBack (fun n acc -> Expr.NewUnionCase(cons, [ Expr.Value(n, typeof<int>); acc])) [1..100000] (Expr.NewUnionCase(nil, []))
Real: 00:00:00.370, CPU: 00:00:00.375, GC gen0: 8, gen1: 3, gen2: 0

Answer 1

为了比较，我尝试定义自己的 Expr - 类似联合类型，看看会有多快:

type MExpr = 
  | MUnionCase of Reflection.UnionCaseInfo * A list
  | MValue of int * System.Type
  | MUnit

现在，我们可以将 DU 对象和列表的创建与实际的表达式构建进行比较。

List.foldBack (fun n acc -> 
  MUnionCase(cons, [MValue(n, typeof<int>); acc])) [1..100000] MUnit
// ~30ms

List.foldBack (fun n acc -> 
  Expr.NewUnionCase(cons, [ Expr.Value(n, typeof<int>); acc])) 
    [1..100000] (Expr.NewUnionCase(nil, []))
// ~200ms

原因 NewUnionCase较慢的是，当您创建引用时，该函数还会对引用进行类型检查以确保结果键入正确。这涉及检查参数的数量及其类型。你可以看到 what's going on from the source code .
您可以使用数组而不是列表吗？下面只需要大约 45 毫秒，因为分配少了很多，类型检查也更容易:

Expr.NewArray(typeof<int>, List.init 100000 (fun i -> 
  Expr.Value(i, typeof<int>)))

如果你想构造一个产生列表的引用，你仍然可以这样做:

let a = Expr.NewArray(typeof<int>, List.init 100000 (fun i -> 
  Expr.Value(i, typeof<int>)))
<@ List.ofArray (%%a) @>