Why is building/splicing F# quotations so slow?

Question

It seems that building quotations via <@ @> syntax is painfully inefficient. For example creating a list of integers

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

Not only does the above code run very slowly but memory performance is also bad

In contrast the following is faster but still poor memory-wise

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

Finally, using plain old Expr is significantly better (still not as fast as I would have hoped though)

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

For comparison, I tried to define my own Expr-like union type and see how fast that would be:

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

Now, we can compare just the creation of the DU objects and lists, with the actual expression building.

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

The reason why NewUnionCase is slower is that, when you're creating a quotation, the function also type-checks the quotation to make sure that the result is well typed. This involves checking the number of arguments and their types. You can see what's going on from the source code.

Could you use an array instead of list? The following takes only about ~45ms, because there is a lot less allocation and the type checking is also easier:

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

If you want to construct a quotation that produces a list, you can still do that:

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