为什么功能组成从左到右比右到左快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

结果是:59 fromLeft毫秒,658毫秒fromRight 和26毫秒Imperative.

测试在发布模式和VS外部完成.结果是稳定的,不依赖于我测试函数的顺序.如果Imperative运行时间被认为是add函数本身的开销并且从两个结果中减去,则两个组合物的性能不同的因素是11x或19x .

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

我的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

所以这看起来像是编译器缺少的优化。