如何在保持语法的同时使这种功能样式的代码更具性能

Question

我想写这个操作

Matrix.Multiply(source,target)
target.Add(offsets)

在这种数学风格

target = Matrix * source + offsets;

但是,我也很关心性能.(实际上,上面的操作将在紧密循环中运行.)我不想为每个矩阵向量乘法创建一个新向量,而为向量加法创建另一个新向量.

如何在C#或F#(或您知道的任何功能语言)中实现上述操作,以便可以实现样式和性能？

抱歉这个天真的问题.我确信这种愿望是如此根本.

Answer 1

一种众所周知的技术,例如在高性能数值阵列的Repa库的核心,是在基本的"2D整数数组"结构之上定义一个更高级别的数据结构,它延迟了你的操作想要执行,以及最终执行这些操作的解释/规范化功能,应用它认为有利可图的任何优化.

具体来说,在您的示例中,我认为大多数当前的答案都错过了这个,您希望A * B + C不要重写

add(multiply(A,B), C)

或者在OO风格中

A.multiply(B).add(C)

但反而

multiply_and_add(A,B,C)

其中multiply_and_add是specialez,低级操作,它同时执行两个操作并且更加优化.类似地,众所周知,对于任意矩阵A, B, C, D,A * B * C * D可以更有效地计算乘积,A * ((B * C) * D)而不是A * (B * (C * D)))取决于操作数维度.因此,纯粹的本地方法(在整数数组上表示每个操作)不起作用,您需要表达式 - 全局重写以获得最佳效率 - 正如C++中的hackish模板库所做的那样.

解决方案是从int array array精细数据类型转移到,例如:

type matrix =
  | Raw of int array array
  | Add of matrix * matrix
  | Mult of matrix * matrix

然后提供一个eval : matrix -> int array array函数,通过可能应用特定于域的优化来"解释"那些矩阵描述(实质上是矩阵运算的抽象语法树).一个天真的例子:

let rec eval = function
  | Raw m -> m
  | Add(Mult(a,b), c) | Add(c, Mult(a,b)) ->
    multiply_and_add (eval a) (eval b) (eval c)
  | Add (a, b) -> add (eval a) (eval b)
  | Mult (a, b) -> mult (eval a) (eval b)

然后,您可以定义您喜欢的语法糖,以使matrix构造函数更易于阅读.

module Matrix = struct
  let (!) m = Raw m
  let (+) a b = Add (a, b)
  let (*) a b = Mult (a, b)
end

let ... = eval Matrix.(!A * !B + !C)