为什么 f# 线性代数函数的这些微小变化会让它们的性能变得如此之好？

Question

我对 f# 编程相当陌生，虽然我非常喜欢它，但困扰我的一件事是，在 f# 中以感觉“正确”的方式编写代码经常会导致速度极其缓慢。我一直在使用 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 性能的事情（按影响顺序排列）：

1. 每次递归调用重新分配数组
2. 不使用尾递归

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

对于第二个样本：

您的慢版本之所以慢，是因为 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]或多或少可以做到这一点，但它会带来一些边际开销。

我将每种方法放入基准测试中以查看一些比较结果。正如您所看到的，循环方法甚至比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

方法	意思是	错误	标准差	比率	第0代	第一代	已分配
点积	320,534.9 纳秒	1,738.55 纳秒	1,626.24 纳秒	1.000	480.4688	18.0664	8,040,000 B
点积循环	625.4纳秒	1.93纳秒	1.71纳秒	0.002	-	-	-
点积折叠	1,105.1 纳秒	10.77纳秒	10.07纳秒	0.003	-	-	-

如果您致力于编写递归代码，您可以做的另一件事是拥有一个私有辅助函数来对Spanor进行尾递归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])

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