为什么在Haskell(GHC)中多态性如此昂贵？

Question

我提出这个问题是参考这个SO问题。Don Stewart的答案说："第一行表示"你的代码高度多态性，将所有float变量更改为Double..."，这样可以使代码性能提高4倍。

我有兴趣在Haskell中执行矩阵计算，是否应该养成编写高度单态化代码的习惯？

但是一些语言利用特设多态性生成快速代码，为什么GHC不会或无法实现？（请阅读C ++或D）

为什么我们不能像blitz++或eigen一样拥有Haskell？我不明白GHC中的类型类和（特设）多态性的工作原理。

- fedvasu

---

请看一下SPECIALIZE pragma，它是为这类事情而设计的。 - daniel gratzer

一个非常好的问题。为ghc设置一个标志，将所有东西都特化为单态实例，这是相当合理的。与一些人所认为的相反，这并不会导致普通程序的代码膨胀。 - augustss

我们可以拥有类似于blitz/eigen的东西，而且肯定有一天我们会拥有：http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/haskell-beats-C.pdf - Joker_vD

Answer 1

使用多态代码时，通常存在代码大小和代码速度之间的权衡。一种方法是为它将操作的每种类型都生成单独的代码版本，这会导致更大的代码；另一种方法是生成一个可以在多种类型上运行的单个版本，这将速度变慢。

C++模板的实现选择以增加代码速度为代价来增加代码大小。默认情况下，GHC采取相反的权衡。但是，可以使用SPECIALIZE和INLINABLE编译指示来让GHC为不同的类型生成单独的版本。这将产生速度类似于单态代码的多态代码。

- Dirk Holsopple

---

他还提到了类型类，值得一提的是类型类可能带来的开销和相关记录。 - daniel gratzer

@fedvasu - 请参阅GHC指南："SPECIALIZE的效果是生成（a）函数的专门版本和（b）重写规则[...]，将对未经特殊处理的函数的调用重写为对专门处理的函数的调用。"当然，如果有疑问，请检查生成的Core代码。 - Fixnum

@Fixnum 我明白了，SPECIALIZE 关键字是按函数工作的，并且有一些适用规则，我原以为它可以在模块级别或 .hs 文件级别工作。谢谢。 - fedvasu

Answer 2

我想通过补充Dirk的回答来说明，通常建议使用INLINABLE而不是SPECIALIZE。在函数上使用INLINABLE注释可确保模块导出函数的原始源代码，以便可以在使用点进行特化。这通常消除了为每个用例提供单独的SPECIALIZE指示符的需要。

与INLINE不同，INLINABLE不会改变GHC的优化启发式方法。它只是表示“请导出源代码”。

- Gabriella Gonzalez

Answer 3

我不明白在GHC中类型类是如何工作的。

好的，请考虑这个函数：

linear :: Num x => x -> x -> x -> x
linear a b x = a*x + b

这个函数需要三个数字作为输入，并返回一个数字作为输出。该函数接受任何数值类型；它是多态的。 GHC 是如何实现这个功能的呢？ 好吧，本质上编译器创建了一个“类字典”，其中包含所有类方法（在这种情况下是+、-、*等）。 这个字典成为函数的一个额外隐藏参数。类似于这样：

data NumDict x =
  NumDict
  {
    method_add :: x -> x -> x,
    method_subtract :: x -> x -> x,
    method_multiply :: x -> x -> x,
    ...
  }

linear :: NumDict x -> x -> x -> x -> x
linear dict a b x = a `method_multiply dict` x `method_add dict` b

每次调用函数时，编译器会自动插入正确的字典，除非调用函数也是多态的，这样它本身就已经收到了一个字典，所以只需将其传递即可。

实际上，缺乏多态性的函数通常不太快，不是因为缺少函数查找，而是因为了解类型允许进行其他优化。例如，我们的多态线性函数将在数字、向量、矩阵、比率、复数等方面工作，任何东西都可以。现在，如果编译器知道我们想要在 Double 上使用它，那么所有操作都变成单一的机器代码指令，所有的操作数都可以通过处理器寄存器传递，等等。所有这些都导致极其高效的代码。即使是带有 Double 组件的复数，也可以使其变得美观高效。如果我们不知道将获得什么类型，那么我们就无法进行这些优化...这通常是速度差异的主要原因。

对于像 linear 这样的微小函数，它很可能每次被内联调用，从而没有多态开销和少量的代码重复-有点像 C++ 模板。对于较大、更复杂的多态函数，可能会有一些代价。总的来说，编译器决定这个问题，而不是你-除非你想开始在各个地方撒上编译器指令，或者如果你实际上没有使用任何多态性，可以给出一切单态类型签名...

- MathematicalOrchid

---

对于像 linear 这样的小函数，每次调用时都很可能被内联，从而不会产生多态开销和少量代码重复 - 就像 C++ 模板一样。对于更大、更复杂的多态函数，可能会有一些成本。通常情况下，编译器决定这个问题，而不是你 - 除非你想开始在各个地方撒上 pragma。;-) 或者，如果您实际上没有使用任何多态性，可以只给所有东西提供单态类型签名... - MathematicalOrchid