haskell - 计算向量表达式的范数 ||aW+bX+cY||

Question

我是一名博士生。
在我的论文的介绍中，我对线性代数工具的表现力和性能之间的折衷很感兴趣。

作为一个简单的例子，我使用了向量表达式范数的计算。
我的示例的 C 代码是:

float normExpression3(float a, float *W, float b, float *X, float c, float*Y){
double norm = 0;
for (int i=0; i<n; ++i) // n in [3e6; 2e8]
{
    float tmp = a*W[i]+b*X[i]+c*Y[i];
    norm+=tmp*tmp;
}
return sqrtf(norm);

}

我比较了使用不同技术实现的性能。
由于向量很大(几百万个元素)，性能受到内存带宽的限制。
但是，不同的方法之间存在巨大差异。

我编写的优化 C 版本没有表现力(必须将新函数编写为第 4 个向量)并且非常丑陋(线程化和向量化)，但达到了 6.4 GFlops。
另一方面，MATLAB 代码非常好:

result = norm(a*W+b*X+c*Y)

但仅达到 0.28 GFlops。

C++ 模板表达式 à la Blitz++ 为用户提供表现力和性能(6.5 GFlops)。

作为我分析的一部分，我想知道函数式语言如何与这些方法进行比较。
我想在 Haskell 或 OCaml 中展示一个例子(AFAIK，两者都被认为非常适合这种操作)。

我不知道这些语言。我可以向他们学习以提供我的示例，但这不会是一个公平的比较:我不确定能够提供一个允许表现力和性能的实现。

所以我的两个问题是:
1)哪种语言最适合？
2) 如何在不影响实现的通用性的情况下有效地计算向量表达式的范数？

提前，谢谢!

威尔弗里德 K。

编辑:更正了 norm 的类型蓄电池 float至 double

Answer 1

值得一提的是，以下是您函数的 OCaml 版本:

let normExpression3 a w b x c y =
    let n = Array.length w in
    if not (n = Array.length x && n = Array.length y)
        then invalid_arg "normExpression3";
    let (@) = (Array.unsafe_get : float array -> int -> float) in
    let rec accum a w b x c y n i norm =
        if i = n then sqrt norm else
        let t = a *. (w @ i) +. b *. (x @ i) +. c *. (y @ i) in
        accum a w b x c y n (i + 1) (norm +. t)
    in accum a w b x c y n 0 0.

它对性能进行了一些考虑，即:

未经检查的数组访问(或者更确切地说，数组边界检查手动提升到循环之外)

单态数组访问

递归内循环，避免对浮点累加器进行装箱和拆箱

内循环的 Lambda 提升以避免引用封闭值

最后一个优化应该针对封闭的内部循环进行检查，因为有这么多参数，寄存器溢出可能会超过引用封闭参数的成本。

请注意，除非要在基准测试中竞争，否则通常不会为这种优化而烦恼 ;-)另请注意，您需要使用 64 位 OCaml 对此进行测试，因为否则数组仅限于 4 兆元素。