用户编写的算法是否有可能胜过库的内置优化功能?

计算科学 表现 图书馆
2021-12-18 20:50:31

我一直有这个问题(即使听起来很模糊),但在我的数值分析课程中,我们总是学习如何分析和优化代码。然而,由于大多数线性代数库(即 LAPACK、BLAS 等)自 1980 年代以来一直由专业开发人员不断优化,我质疑让我们写下算法并运行它们的目的是什么。例如,当已经有内置函数 ( eig) 时,我们不得不在 MATLAB 中编写 QR 迭代算法。是否存在特殊情况,这些内置函数会因数值不稳定性而导致自定义算法的性能优于它们?

更新:我要感谢大家有趣的答案和评论,我已经阅读了所有内容。

我还意识到这个非常狭窄的数学领域的美妙之处,它在我们的工作中有着深远的应用。这些数学家和计算机科学家为使这些代码更强大而付出的努力使我们(那些正在学习他们的理论的人)变得美丽,这样我们就可以在学习的同时欣赏它们,并知道何时使用这些优化的构建-in 函数。当我们写下 15 行代码来计算某个矩阵的 Householder QR 分解时,我只能想知道内置函数有多少行代码(可能是 100 行),这样它才能在我们的计算中为我们提供最好的服务在现实生活中的应用。Aqr()

4个回答

尽管 LAPACK 有一些非常优化的代码,但在少数情况下编写自己的版本仍然是值得的。

  1. 最重要的原因(以及他们让您在课程中这样做的原因)。这是一次很棒的学习经历。除非您花一些时间来实现它,否则您永远不会完全理解 QR 算法之类的东西(实际上要获得正确的细节非常复杂)。当您编写其他数字代码时,您学到的许多技能都会被翻译。

  2. 许多代码是由开发算法的研究人员贡献的,这需要付出很多努力。通常评估研究人员发表的论文数量,而不是他们为图书馆编写的代码,因此研究人员可能缺乏贡献这些代码的动力。例如,仅在去年才贡献了 QZ 算法的优化版本,尽管在 2006 年发表了一篇关于它的论文。

  3. LAPACK 代码需要健壮且通用。这对于小规模的例程最为重要。我将以 DLARTG 为例进行讨论。该例程计算吉文斯旋转。它有很多缩放、安全检查和异常,以确保它对于你可能给它的所有输入总是准确的。如果您知道对于您的应用程序,这些安全检查将不是必需的,或者您不需要强大的准确性保证,您可以获得更快的结果。

@ThiysSteel 涵盖了很多内容,这是我认为重要的另一个观点:

即使您有可能需要的任何算法的优秀实现,您仍然需要了解一些内部结构才能充分利用您的库。一些例子:

  • 任何线性代数库都可以在数学允许的范围内真正快速且准确地计算逆矩阵。但是您必须了解一点理论才能知道您仍然应该尽可能避免使用它。(一般来说,不显式计算逆矩阵的矩阵分解和求解更好)。
  • 您的库可能可以计算任意矩阵的特征值,因此可能很想只使用通用函数并完成它。但是通过一些背景知识,您可以了解对称/厄米特矩阵的专用算法工作得有多好(!)。因此,付出相当大的努力将您的问题转化为这种情况是合理的。
  • 为了获得最佳性能,您必须考虑数据布局。行专业?列专业?AoS 或 SoA(如果是复数)?一个好的库将能够使用其中任何一个,但是您需要了解一些内部工作原理才能做出明智的选择(尽管在实践中:尝试一下衡量性能。)

这种情况有点类似于编写汇编代码。你几乎不应该用手这样做。但是了解(一些)汇编将使您成为任何高级语言的更好程序员。

澄清@ThiysSteel 的好答案:

关键是不要试图超越经验丰富的人编写的代码的优化,他们已经为此争论了几十年。

关键是要熟悉该代码解决的问题,欣赏“美好”,并且不要对未来的相关问题天真。

(向其他人学习是明智/公平的。您不必自己重新发明坏轮子。“他们卖掉它们!”坏轮子和好轮子...... :)

我曾经尝试通过使用汇编语言(而不是 C)来优化代码。我取得了一些明显的成功,实时麦克风阵列使用汇编语言工作,但它在 C 语言中根本不起作用。

然而,从那时起,已经过去了20多年。现在要达到这样的改善是非常困难的。编译器变得更好,图书馆也是如此。人们仍然使用基于LINPACK的包(例如,用于特征值/特征向量例程的线性代数),其核心是在 1960 年代用 Fortran 编写的!C# 等有新的包装器。

任何时候使用低级语言编写,都会增加错误和不可读代码的风险,当然对于除了原作者之外必须维护代码的任何人来说都是一个问题。

此外,要解决的编程问题中可能存在特殊情况、边缘情况等。但是,这些可能最好在“调用程序”中处理(即:

if (such and such) 
     call the library 
  else 
     implement special rule for edge case 

... 等等.....

例如,如果浮点数的绝对值小于某个阈值,则可以避免除以零,然后调用涉及除法的计算。