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

Question

我问与refernce这个问题该 SO问题.Don Stewart接受的答案:第一行说"您的代码是高度多态的,将所有浮动变量改为Double ...",它提供了4倍的性能提升.

我有兴趣在Haskell中进行矩阵计算,我应该养成编写高度单态代码的习惯吗？

但是有些语言很好地利用了ad-hoc多态来生成快速代码,为什么GHC不会或不能呢？(阅读C++或D)

为什么我们不能为Haskell提供类似blitz ++或eigen的东西？我不明白GHC中的类型和(ad-hoc)多态性是如何工作的.

Answer 1

对于多态代码,通常需要在代码大小和代码速度之间进行权衡.要么为它将要操作的每种类型生成相同代码的单独版本,这会导致更大的代码,或者您生成可以在多种类型上运行的单个版本,这将更慢.

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

Answer 2

我想通过说INLINABLE通常建议结束来补充Dirk的答案SPECIALIZE.INLINABLE函数的注释保证模块导出函数的原始源代码,以便它可以在使用时专门化.这通常不需要SPECIALIZE为每个用例提供单独的编译指示.

不同INLINE,INLINABLE不会改变GHC的优化启发式.它只是说"请导出源代码".

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

无论何时调用该函数,编译器都会自动插入正确的字典 - 除非调用函数也是多态的,在这种情况下它本身会收到一个字典,所以只需传递它.

事实上,缺乏多态性的函数通常更快,因为缺乏函数查找,但因为知道类型允许进行额外的优化.例如,我们的多态linear函数将适用于数字,向量,基质,比率,复数,任何东西.现在,如果编译器知道我们想要在它上面使用它Double,那么现在所有操作都成为单个机器代码指令,所有操作数都可以在处理器寄存器中传递,依此类推.所有这些都会产生极其高效的代码.即使它是带有Double组件的复杂数字,我们也可以使它变得美观和高效.如果我们不知道我们会得到什么类型,我们就无法进行任何优化......这就是大多数速度差异通常来自的地方.

对于像线性这样的微小函数,它很可能在每次被调用时都被内联,导致没有多态性开销和少量代码重复 - 而不像C++模板.对于更大,更复杂的多态函数,可能会有一些成本.一般情况下,编译器决定这一点,而不是你 - 除非你想开始在这个地方撒上pragma.;-)或者,如果你实际上没有使用任何多态,你可以只给出所有单形类型的签名...