performance - 为什么这段代码不快？

Question

我已经制作了一段大约运行的 Java 代码的“副本”。 400 毫秒 ( https://gist.github.com/threecee/cb1c55ad1ce9ac4b1903 )。我的 F# 版本使用 Parallel.ForEach我也试过 PSeq但没有一个版本的速度超过 7 秒。

并不是说我的一段代码必须比我复制的代码快，但我真的很想知道在 F# 中这样的示例计算中可以做些什么来提高性能。

open System.Threading.Tasks
#time 
let calculateProducts n =
    let bits = [| for i in 1 .. ((n+1)*(n+1)) -> 0 |]
    let inner i =
        [|i..n|] |> Array.map (fun j -> bits.[j*i] <- 1) |> ignore
    Parallel.ForEach([|1 .. n|], (fun i -> inner i)) |> ignore
    bits |> Array.sum
printfn "%i" (calculateProducts 8000)

代码的作用是计算所有独特的产品 x*y where x: 1->8000 and y: 1-8000 .

更新:
使用后更新的代码Array.init正如 jpe 在答案中所建议的那样:

open System.Threading.Tasks
#time 
let calculateProducts n =
    let bits = Array.init ((n+1)*(n+1)) (fun _ -> 0)        
    let inner i =
        let arr = Array.init (n-i+1) (fun x -> x+i)
        Parallel.ForEach(arr, (fun j -> bits.[j*i] <- 1)) |> ignore
    let arr = Array.init n (fun x -> (x+1))
    Parallel.ForEach(arr, (fun i -> inner i)) |> ignore
    bits |> Array.sum
printfn "%i" (calculateProducts 8000)

Answer 1

您需要使用内置的数组初始化代码，因为您当前的数组初始化在示例中需要很长时间。因此更换线

let bits = [| for i in 1 .. ((n+1)*(n+1)) -> 0 |]

带线

let bits = Array.init ((n+1)*(n+1)) (fun _ -> 0)

并且您应该获得与 Java 代码相当的性能。

更新:正如 John Palmer 所建议的，Array.zeroCreate将使数组初始化为零更快。因此，如果您只需要将数组初始化为零而不计算任何初始值，则使用

let bits = Array.zeroCreate ((n+1)*(n+1))

更新:为什么这么快的原因之前已经解释过here .简短摘要:它使用适当的 IL 字节码命令 newarr用于初始化，反过来在 .Net 的运行时中被优化为非常快。 Array.init比直接的“手动”初始化更快，因为它调用 zeroCreateUnchecked初始化数组，然后在已经初始化的数组上运行初始化函数。

如果你想知道代码在哪里，那么这里是链接:implementation of Microsoft.FSharp.Collections.Array依次调用 internal implementation in Microsoft.FSharp.Primitives.Basics.Array .