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

Question

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

Answer 1

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.