F# Compiler Guide

Code Optimizations

Code optimizations are in Compiler/Optimize/*.

Some of the optimizations performed in Optimizer.fs are:

In DetupleArgs.fs, tuples at call sites are eliminated if possible. Concretely, functions that accept a tuple at all call sites are replaced by functions that accept each of the tuple's arguments individually. This may require inlining to activate.

Considering the following example:

let max3 t =
    let (x, y, z) = t
    max x (max y z)

max3 (1, 2, 3)

The max3 function gets rewritten to simply accept three arguments, and depending on how it gets called it will either get inlined at the call site or called with 3 arguments instead of a new tuple. In either case, the tuple allocation is eliminated.

However, sometimes this optimization is not applied unless a function is marked inline. Consider a more complicated case:

let rec runWithTuple t offset times =
    let offsetValues x y z offset =
        (x + offset, y + offset, z + offset)
    if times <= 0 then
        let (x, y, z) = t
        let r = offsetValues x y z offset
        runWithTuple r offset (times - 1)

The inner function offsetValues will allocate a new tuple when called. However, if offsetValues is marked as inline then it will no longer allocate a tuple.

Currently, these optimizations are not applied to struct tuples or explicit ValueTuples passed to a function. In most cases, this doesn't matter because the handling of ValueTuple is well-optimized and may be erased at runtime. However, in the previous runWithTuple function, the overhead of allocating a ValueTuple each call ends up being higher than the previous example with inline applied to offsetValues. This may be addressed in the future.

In InnerLambdasToTopLevelFuncs.fs, inner functions and lambdas are analyzed and, if possible, rewritten into separate methods that do not require an FSharpFunc allocation.

Consider the following implementation of sumBy on an F# list:

let sumBy f xs =
    let rec loop xs acc =
        match xs with
        | [] -> acc
        | x :: t -> loop t (f x + acc)
    loop xs 0

The inner loop function is emitted as a separate static method named loop@2 and incurs no overhead involved with allocating an FSharpFunc at runtime.

In LowerCalls.fs:

In LowerSequences.fs:

Potential future optimizations: Better Inlining

Consider the following example:

let inline f k = (fun x -> k (x + 1))
let inline g k = (fun x -> k (x + 2))

let res = (f << g) id 1 // 4

Intermediate values that inherit from FSharpFunc are allocated at the call set of res to support function composition, even if the functions are marked as inline. Currently, if this overhead needs removal, you need to rewrite the code to be more like this:

let f x = x + 1
let g x = x + 2

let res = id 1 |> g |> f // 4

The downside of course being that the id function can't propagate to composed functions, meaning the code is now different despite yielding the same result.

More generally, any time a first-order function is passed as an argument to a second-order function, the first-order function is not inlined even if everything is marked as inline. This results in a performance penalty.

val max3 : 'a * 'a * 'a -> 'a (requires comparison)
val t : 'a * 'a * 'a (requires comparison)
val x : 'a (requires comparison)
val y : 'a (requires comparison)
val z : 'a (requires comparison)
val max : e1:'T -> e2:'T -> 'T (requires comparison)
<summary>Maximum based on generic comparison</summary>
<param name="e1">The first value.</param>
<param name="e2">The second value.</param>
<returns>The maximum value.</returns>
val runWithTuple : int * int * int -> offset:int -> times:int -> int * int * int
val t : int * int * int
val offset : int
val times : int
val offsetValues : (int -> int -> int -> int -> int * int * int)
val x : int
val y : int
val z : int
val r : int * int * int
val sumBy : f:('a -> int) -> xs:'a list -> int
val f : ('a -> int)
val xs : 'a list
val loop : ('a list -> int -> int)
val acc : int
val x : 'a
val t : 'a list
val f : k:(int -> 'a) -> x:int -> 'a
val k : (int -> 'a)
val g : k:(int -> 'a) -> x:int -> 'a
val res : int
val id : x:'T -> 'T
<summary>The identity function</summary>
<param name="x">The input value.</param>
<returns>The same value.</returns>
val f : x:int -> int
val g : x:int -> int