Why is function composition from left to right 11x to 19x faster than right to left?

f#, performance

Solution

A very rough answer would be that the compiler is in-lining the functions in `fromLeft`, but for some reason isn't doing the same optimization for `fromRight`. It is possible to force the associativity by fully parenthesizing the composition like this:

let fromLeft  = add>>(add>>(add>>(add>>(add>>(add>>(add>>(add>>(add>>add))))))))
let fromRight = ((((((((add<<add)<<add)<<add)<<add)<<add)<<add)<<add)<<add)<<add

resulting in:

From left
Starting
Took 645.648 ms

From right
Starting
Took 625.058 ms

Imperative
Starting
Took 23.0332 ms

Reversing the parenthesization like this:

let fromLeft = ((((((((add>>add)>>add)>>add)>>add)>>add)>>add)>>add)>>add)>>add
let fromRight  = add<<(add<<(add<<(add<<(add<<(add<<(add<<(add<<(add<<add))))))))

results in:

From left
Starting
Took 86.3503 ms

From right
Starting
Took 75.6358 ms

Imperative
Starting
Took 33.7193 ms

So this just looks like an optimization which is missing from the compiler.

Problem

I encountered this phenomenon when writing my poor man's version of FParsec. Consider: ``` let add x = x+1 let fromLeft = add>>add>>add>>add>>add>>add>>add>>add>>add>>add let fromRight = add<<add<<add<<add<<add<<add<<add<<add<<add<<add let imperative x = let mutable result = x for i = 0 to 9 do result <- add result result ``` And test the performance of all three functions: ``` let runs = 10000000 printf "From left\n" time(fun()->fromLeft 0) runs printf "\nFrom right\n" time(fun()->fromRight 0) runs printf "\nImperative\n" time(fun()->imperative 0) runs ``` The results are: 59ms for `fromLeft`, 658 ms for `fromRight` and 26 ms for `Imperative`. The test is done in Release mode and outside of VS. The results are stable and do not depend on the order in which I test the functions. The factor by which the performance of the two compositions differs is 11x or 19x if the `Imperative` run time is taken to be the overhead of the `add` function itself and is subtracted from both results. Does anyone know the reason for such a discrepancy? My `time` combinator is ``` let inline time func n = GC.Collect() GC.WaitForPendingFinalizers() printfn "Starting" let stopwatch = Stopwatch.StartNew() for i = 0 to n-1 do func() |> ignore stopwatch.Stop() printfn "Took %A ms" stopwatch.Elapsed.TotalMilliseconds ```

Original source