为什么对 f# 线性代数函数的这些微小更改会使它们的性能提高这么多？

Question

我对使用 f# 进行编程还很陌生，虽然我非常喜欢它，但让我困扰的一件事是，在 f# 中以 'proper' 方式编写代码的频率有多高，导致它令人难以置信减缓。我一直在使用 f# 开发神经网络，与其他语言的实现相比，我的代码非常慢。一种具体情况是以下线性代数函数：

// Dot Product

// Slow
let rec dotProduct (vector1 : float []) (vector2 : float []) : float =

    if vector1 |> Array.length = 0 then
        0.0
    else
        vector1.[0] * vector2.[0] + (dotProduct (vector1 |> Array.tail) (vector2 |> Array.tail))

// Fast
let dotProduct (vector1 : float []) (vector2 : float [])  =
    Array.fold2 (fun state x y -> state + x * y) 0.0 vector1 vector2

// Matrix Vector Product

// Slow

let matrixVectorProduct (matrix : float [,]) (vector : float[]) : float [] =
    [|
        for i = 0 to (matrix |> Array2D.length1) - 1 do
            yield dotProduct matrix.[i, 0..] vector
    |]

// Fast
let matrixVectorProduct (matrix : float [,]) (vector : float[]) : float [] =
    
    let mutable product = Array.zeroCreate (matrix |> Array2D.length1)
    
    for i = 0 to (matrix |> Array2D.length1) - 1 do
        product.[i] <- (dotProduct matrix.[i, 0..] vector)
    
    product

我想知道是否有更多 f# 经验的人可以解释为什么第二种情况在每个示例中都更快，就计算机如何解释我的代码而言。使用像 f# 这样的高级语言进行编码的最大痛苦是很难知道您的代码是如何优化的，并且运行与使用低级语言编程相比。

Answer 1

第一个代码示例：

你的慢速 dotProduct 函数正在做两件影响 CPU 性能的事情，按影响顺序排列：

每次递归调用时重新分配一个数组
不使用尾递归

根据我的测量，第二点并不是什么大问题。

第二个样本：

你的慢版本很慢，因为 F# 数组表达式不固定。它需要分配并使用一个枚举器来生成下一个项目，直到完成为止。在您的更多迭代代码中，您已经预先分配了一个固定数组，您只需填充它。这总是明显更快，并且当您关注性能时，变异和循环通常是获胜的好方法。

还有另一种方法可以加快点积代码的速度：只需执行一个简单的循环即可！

let dotProductLoop (vector1 : float []) (vector2 : float []) : float =
    let mutable acc = 0.0

    for idx = 0 to vector1.Length - 1 do
        acc <- acc + (vector1.[idx] * vector2.[idx])
    
    acc

您会注意到 [fold2][1] 或多或少会这样做，但会带来一些边际开销。

我将每种方法都放入 benchmark 中以查看一些比较结果。如您所见，循环方法甚至比 fold2 调用更快，但两者都比您的初始实现快得多，因此选择其中任何一个都是明显的胜利。


BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19042.1288 (20H2/October2020Update)
AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK=6.0.100-rc.2.21505.57
  [Host]     : .NET 6.0.0 (6.0.21.48005), X64 RyuJIT DEBUG
  DefaultJob : .NET 6.0.0 (6.0.21.48005), X64 RyuJIT

Method	Mean	Error	StdDev	Ratio	Gen 0	Gen 1	Allocated
DotProduct	320,534.9 ns	1,738.55 ns	1,626.24 ns	1.000	480.4688	18.0664	8,040,000 B
DotProductLoop	625.4 ns	1.93 ns	1.71 ns	0.002	-	-	-
DotProductFold	1,105.1 ns	10.77 ns	10.07 ns	0.003	-	-	-

如果你致力于编写递归代码，你可以做的另一件事是拥有一个私有辅助函数，它在 Span 或 ReadonlySpan:

上执行尾递归

let rec private dotProductImpl (vector1 : Span<float>) (vector2 : Span<float>) (acc: float) =
        if vector1.Length = 0 then
            acc
        else
            dotProductImpl (vector1.Slice(1)) (vector2.Slice(1)) (acc + vector1.[0] * vector2.[0])

调用此函数的函数将与我建议的循环一样执行。

为什么对 f# 线性代数函数的这些微小更改会使它们的性能提高这么多？

Why do these minor changes to f# linear algebra functions make them so much more performant?

performance

f#