为什么从左到右的函数组合比从右到左的速度快11倍到19倍？

Question

在写我可怜人的FParsec版本时，我遇到了这种现象。考虑：

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

并测试所有三个功能的性能：

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

结果表明：fromLeft为59 ms，fromRight为65 8ms，Imperative为26 ms。

该测试是在版本模式和VS之外进行的。结果是稳定的，不取决于我测试函数的顺序。如果将Imperative运行时视为add函数本身的开销，并从这两个结果中减去，则两个组合性能不同的因素是11倍或19倍。

有谁知道出现这种差异的原因吗？

我的time组合器是

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

一个非常粗略的答案是，编译器在fromLeft中嵌入了函数，但出于某种原因，它没有对fromRight进行相同的优化。完全用圆括号表示这样的构图是可以强制结合的：

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

其结果是：

From left
Starting
Took 645.648 ms

From right
Starting
Took 625.058 ms

Imperative
Starting
Took 23.0332 ms

将圆括号颠倒如下：

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

在以下方面的成果：

From left
Starting
Took 86.3503 ms

From right
Starting
Took 75.6358 ms

Imperative
Starting
Took 33.7193 ms

这看起来就像是编译器中缺少的一个优化。