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

Question

I came across this phenomenon when writing my version of FParsec for the poor. 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 check 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 

Results: 59 ms for fromLeft , 658 ms for fromRight and 26 ms for Imperative .

The test is performed 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 coefficient at which the performance of the two compositions is different is 11x or 19x if the execution time of the Imperative is considered the overhead of the add function itself and subtracted from both results.

Does anyone know the reason for this discrepancy?

My time combinator

 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 rude answer would be that the compiler sets the functions in fromLeft , but for some reason does not perform the same optimization for fromRight . You can bring associativity by completely copying the composition as follows:

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

as a result of:

 From left Starting Took 645.648 ms From right Starting Took 625.058 ms Imperative Starting Took 23.0332 ms 

Reverse such a bracket:

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

leads to:

 From left Starting Took 86.3503 ms From right Starting Took 75.6358 ms Imperative Starting Took 33.7193 ms 

So, it just looks like an optimization missing from the compiler.