Why can't the F# compiler fully inline function arguments of a higher order function?

Question

One of the things I love about F# is a real inline keyword. However, while it allows to write first order functions that perform the same as pasted code blocks, things aren't so rosy for higher order functions. Consider

let inline add i = i+1
let inline check i = if (add i) = 0 then printfn ""    
let inline iter runs f = for i = 0 to runs-1 do f i
let runs = 100000000
time(fun()->iter runs check) 1
time(fun()->for i = 0 to runs-1 do check i) 1

The results are 244 ms for iter and 61 ms for manual checks. Let's delve into ILSpy. The relevant function called for the direct call is:

internal static void func@22-12(Microsoft.FSharp.Core.Unit unitVar0)
{
    for (int i = 0; i < 100000000; i++)
    {
        if (i + 1 == 0)
        {
            Microsoft.FSharp.Core.PrintfFormat<Microsoft.FSharp.Core.Unit, System.IO.TextWriter, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit> format = new Microsoft.FSharp.Core.PrintfFormat<Microsoft.FSharp.Core.Unit, System.IO.TextWriter, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit>("");
            Microsoft.FSharp.Core.PrintfModule.PrintFormatLineToTextWriter<Microsoft.FSharp.Core.Unit>(System.Console.Out, format);
        }
    }
}

With add inlined. The relevant function for iter is

internal static void func@22-11(Microsoft.FSharp.Core.Unit unitVar0)
{
    for (int i = 0; i < 100000000; i++)
    {
        Tests.FunctionInlining.f@315-5(i);
    }
}
internal static void f@315-5(int i)
{
    if (i + 1 == 0)
    {
        Microsoft.FSharp.Core.PrintfFormat<Microsoft.FSharp.Core.Unit, System.IO.TextWriter, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit> format = new Microsoft.FSharp.Core.PrintfFormat<Microsoft.FSharp.Core.Unit, System.IO.TextWriter, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit, Microsoft.FSharp.Core.Unit>("");
        Microsoft.FSharp.Core.PrintfModule.PrintFormatLineToTextWriter<Microsoft.FSharp.Core.Unit>(System.Console.Out, format);
        return;
    }
}

And we can see the performance penalty comes from one extra level of indirection. As the performance test shows, this indirection is also not removed by the JIT compiler. Is there a reason for why the higher order functions cannot be fully inlined? This is a pain when writing a computational kernel.

My time combinator (though not really relevant here) is

let inline time func n =
    func() |> ignore
    GC.Collect()
    GC.WaitForPendingFinalizers()
    let stopwatch = Stopwatch.StartNew()
    for i = 0 to n-1 do func() |> ignore
    stopwatch.Stop()
    printfn "Took %A ms" stopwatch.Elapsed.TotalMilliseconds

Answer 1

Just to be clear, the F# compiler is inlining every definition that you've marked as inline. It's just that the current behavior of inlining isn't very useful when using an inlined function as a higher-order argument. check can only be inlined when given an argument, and so iter runs check is treated as iter runs (fun i -> check i). Then check gets inlined, resulting in the equivalent of

iter runs (fun i -> if (add i) = 0 then printfn "")

(as you can see in the IL, there is no call to check in the generated IL, but there is a call to the synthetic f@315-5 body for this lambda, which is equivalent). iter gets inlined, too.

Having said that, I agree that the current behavior isn't as useful as it could be - the compiler could also inline the body of the lambda into the call site, which would be safe and improve performance.