Does anybody know the reason why QuotationEvaluator is so slow?

Question

It's common knowledge in the F# community that the PowerPack's quotation compiling facility produces very slow code, so slow in fact that it performs even worse than naive interpretation. I've been looking into the reasons for this, but I haven't been able to find a convincing answer so far. There have been claims that this happens either because of inefficient representation of things like pattern matches in quotations or because of an inherent inefficiency with Expression Trees used by the library. I'd like to illustrate why I think neither is true with a simple example:

#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 going wrong here. The question is, what?

EDIT: the same behaviour also occurs with the FSharpx.Linq compiler

Answer 1

Below is the implementation of the compile:

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)

Notice the use of DynamicInvoke on the delegate, which is much slower than Invoke and the reason for the result you are getting.