Does anyone know the reason why QuotationEvaluator is so slow?

Question

It is well known in the F # community that the PowerPack quote compiler produces very slow code, so slow in fact that it performs even worse than a naive interpretation. I studied the reasons for this, but so far I have not been able to find a convincing answer. It has been argued that this is either due to an ineffective representation of such things as matching patterns in quotes, or due to the inherent inefficiency of the expression trees used by the library. I would like to illustrate why, in my opinion, not one of them is true:

#r "FSharp.Powerpack.Linq.dll" open System open System.Linq.Expressions open Microsoft.FSharp.Quotations.Patterns let powerpack = Microsoft.FSharp.Linq.QuotationEvaluator.Compile <@ 1 + 1 @> // explicitly rewrite above quotation with expression trees let expressionTree = let (Call(_,addM,_)) = <@ 1 + 1 @> let constExpr (x : 'T) = Expression.Constant(box x, typeof<'T>) let eval = Expression.Call(addM, constExpr 1, constExpr 1) let lambda = Expression.Lambda<Func<int>>(eval) lambda.Compile() // reflection - based evaluation let reflection = let (Call(_,addM,_)) = <@ 1 + 1 @> fun () -> addM.Invoke(null, [| 1 :> obj ; 1 :> obj |]) :?> int #time // QuotationEvaluator ~ 2.5 secs for i in 1 .. 1000000 do powerpack () |> ignore // native evaluation ~ 1 msec for i in 1 .. 1000000 do (fun () -> 1 + 1) () |> ignore // reflection evaluation ~ 700 msec for i in 1 .. 1000000 do reflection () |> ignore // naive expression tree ~ 19 msec for i in 1 .. 1000000 do expressionTree.Invoke () |> ignore 

Something is clearly wrong here. The question is what?

EDIT: The same behavior is observed with the FSharpx.Linq compiler

Answer 1

The following is a compilation implementation:

 let CompileImpl (e: #Expr, eraseEquality) = let ty = e.Type let e = Expr.NewDelegate(GetFuncType([|typeof<unit>; ty |]), [new Var("unit",typeof<unit>)],e) let linqExpr = Conv (e,eraseEquality) let linqExpr = (linqExpr :?> LambdaExpression) let d = linqExpr.Compile() (fun () -> try d.DynamicInvoke [| box () |] with :? System.Reflection.TargetInvocationException as exn -> raise exn.InnerException) 

Note the use of DynamicInvoke in the delegate, which is much slower than Invoke , and the reason for getting the result.