Unpickle a quotation literal once, not on every evaluation #20764

Is your feature request related to a problem? Please describe.

Every evaluation of a quotation literal costs tens of microseconds and tens of kilobytes, however often the same literal was evaluated before. A library that takes quotations as its input (a query translator, in my case) cannot avoid that with a cache of its own: it receives the tree only after it is built.

open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running
open FSharp.Quotations

type Person = { Name : string; Age : int; City : string; Nick : string option; Tags : string list }

[<MemoryDiagnoser>]
type QuotationLiteral () =

    let minAge = 18
    let city = "Kyiv"

    // Evaluated once: reading it afterwards costs nothing
    let held : Expr<Person -> bool> = <@ fun p -> p.Age >= 18 @>

    [<Benchmark(Description = "One condition, no captured value, held in a field")>]
    member _.Held () : Expr<Person -> bool> = held

    [<Benchmark(Description = "One condition, no captured value")>]
    member _.Closed () : Expr<Person -> bool> = <@ fun p -> p.Age >= 18 @>

    [<Benchmark(Description = "One condition, one captured value")>]
    member _.OneCondition () : Expr<Person -> bool> = <@ fun p -> p.Age >= minAge @>

    [<Benchmark(Description = "Four conditions, two captured values")>]
    member _.FourConditions () : Expr<Person -> bool> =
        <@ fun p -> p.Age >= minAge && p.City = city && p.Nick.IsSome && List.contains "vip" p.Tags @>

[<EntryPoint>]
let main arguments =
    BenchmarkSwitcher.FromAssembly(typeof<QuotationLiteral>.Assembly).Run arguments |> ignore
    0

BenchmarkDotNet 0.15.8, .NET 10.0.12, FSharp.Core 10.1.401 (SDK 10.0.401), Windows 11 x64, Release. The machine was not idle, so the times are approximate (the last one has a standard deviation of 37 µs); the allocations are exact.

Where it goes, as far as I read the code at a274432:

• IlxGen.GenQuotation pickles the tree at compile time and emits, in place of the literal, a call of Expr.Deserialize40 (type, referencedTypes, spliceTypes, spliceExprs, bytes). The bytes are a new array on every evaluation (newarr and RuntimeHelpers.InitializeArray).
• Deserialize40 runs unpickleExpr over the bytes on every call and then fillHolesInRawExpr with the spliced expressions, which are the captured values.
• Unpickling resolves every type, method and property through reflection again; bindMethodHelper, for one, calls Type.GetMethod (name, flags, null, argTypes, null).
• Nothing is kept between two evaluations. Only the bodies of [<ReflectedDefinition>] members have a table (reflectedDefinitionTable).

Describe the solution you'd like

Unpickle a literal once and keep the tree with its holes. A later evaluation only fills the holes, and a literal without splices can give back the same instance.

The tree with holes depends on the pickled bytes, the referenced type definitions and the type splices, not on the spliced expressions. FSharp.Core has no key to cache by today, because the byte array is a new one each time, so the compiler would have to provide one: for example a static field per literal that holds the unpickled tree, passed to a new entry point next to Deserialize40. A literal with type splices, one inside generic code, needs one tree per instantiation.

I have not prototyped this, so I cannot say how much of the cost it removes. One thing to check is the identity of bound variables: two evaluations of one literal would share their Var objects, as two uses of one quotation value do today.

Describe alternatives you've considered

• Holding the quotation in a value that is evaluated once and passing what changes as arguments of the quoted lambda (the first row of the table). That works where the author of the quotation can restructure the code, not for the caller of a library who writes the quotation at the call.
• A cache inside the library that receives the quotation. It comes too late: the cost is paid before the library is called.

Additional context

Found while measuring the cost model of a quotation-based query translator for Azure Cosmos DB in fsprojects/FSharp.Azure.Cosmos. There a query round trip to the local emulator takes about 2 ms and everything the library does per cached query about 1 µs, so the literal is by far the largest cost on the client.