类型类函数调用的GHC代码生成

Question

在Haskell中定义类型类的实例,您需要提供类型类所需的函数字典.即定义一个实例Bounded,你需要为minBound和提供一个定义maxBound.

出于这个问题的目的,让我们将这个字典vtbl称为类型类实例.如果这是一个很糟糕的类比,请告诉我.

我的问题在于当我调用类型类函数时,我可以从GHC期望什么样的代码生成.在这种情况下,我看到三种可能性:

1. 用于查找实现函数的vtbl查找在运行时关闭
2. vtbl查找在编译时完成,并在生成的代码中发出对实现函数的直接调用
3. vtbl查找在编译时完成,实现函数在调用站点内联

我想了解每一个发生的时间 - 或者是否有其他可能性.

另外,如果类型类是在单独编译的模块中定义而不是作为"主"编译单元的一部分,那有关系吗？

在一个可运行的程序中,似乎Haskell知道程序中所有函数和表达式的类型.因此,当我调用类型类函数时,编译器应该知道vtbl是什么以及确切调用哪个实现函数.我希望编译器至少生成对实现函数的直接调用.这是真的？

(我在这里说"runnable program",以区别于编译你没有运行的模块.)

Answer 1

与所有好问题一样,答案是"它取决于".经验法则是任何类型类多态代码都有运行时成本.但是,库作者在使用GHC的重写规则消除这种成本方面具有很大的灵活性,特别是有一个{-# SPECIALIZE #-}pragma可以自动创建多态函数的单态版本,并且只要推断出多态函数可以用于单态函数,就可以使用它们.类型.(我认为这样做的代价是库和可执行文件的大小.)

您可以使用ghc的-ddump-simpl标志回答任何特定代码段的问题.例如,这是一个简短的Haskell文件:

vDouble :: Double
vDouble = 3
vInt = length [2..5]
main = print (vDouble + realToFrac vInt)

如果没有优化,您可以看到GHC在运行时执行字典查找:

Main.main :: GHC.Types.IO ()
[GblId]
Main.main =
  System.IO.print
    @ GHC.Types.Double
    GHC.Float.$fShowDouble
    (GHC.Num.+
       @ GHC.Types.Double
       GHC.Float.$fNumDouble
       (GHC.Types.D# 3.0)
       (GHC.Real.realToFrac
          @ GHC.Types.Int
          @ GHC.Types.Double
          GHC.Real.$fRealInt
          GHC.Float.$fFractionalDouble
          (GHC.List.length
             @ GHC.Integer.Type.Integer
             (GHC.Enum.enumFromTo
                @ GHC.Integer.Type.Integer
                GHC.Enum.$fEnumInteger
                (__integer 2)
                (__integer 5)))))

......相关的一点是realToFrac @Int @Double.在-O2,在另一方面,你可以看到它没有字典查找静态和内联执行,其结果是对单个呼叫int2Double#:

Main.main2 =
  case GHC.List.$wlen @ GHC.Integer.Type.Integer Main.main3 0
  of ww_a1Oq { __DEFAULT ->
  GHC.Float.$w$sshowSignedFloat
    GHC.Float.$fShowDouble_$sshowFloat
    GHC.Show.shows26
    (GHC.Prim.+## 3.0 (GHC.Prim.int2Double# ww_a1Oq))
    (GHC.Types.[] @ GHC.Types.Char)
  }

图书馆作者也可以选择将多态函数重写为对单态函数的调用,但不能内联单态函数的实现; 这意味着您提出的所有可能性(以及更多)都是可能的.

Answer 2

如果编译器可以在编译时"告诉"您正在使用的实际类型,那么方法查找在编译时发生.否则它会在运行时发生.如果查找发生在编译时,该方法的代码可能取决于方法有多大被内联.(这也适用于常规函数:如果编译器知道您正在调用哪个函数,那么如果该函数"足够小",它将内联它.)

例如,考虑一下(sum [1 .. 10]) :: Integer.这里编译器静态地知道列表是一个take列表Integer,因此它可以为+函数内联Integer.另一方面,如果你做了类似的事情

foo :: Num x => [x] -> x
foo xs = sum xs - head x

然后,当你调用时sum,编译器不知道你正在使用什么类型.(这取决于给出的类型foo),因此它不能进行任何编译时查找.

另一方面,使用{-# SPECIALIZE #-}pragma,你可以做类似的事情

{-# SPECIALIZE foo:: [Int] -> Int #-}

这样做是告诉编译器编译一个特殊版本foo的输入是Int值列表.这显然意味着对于该版本,编译器可以在编译时进行所有方法查找(并且几乎可以肯定地将它们全部内联).现在有两个版本foo- 一个适用于任何类型并执行运行时类型查找,一个仅适用于Int,但[可能]更快.

调用该foo函数时,编译器必须决定调用哪个版本.如果编译器可以在编译时"告诉"你想要的Int版本,它就会这样做.如果它无法"告诉"你将使用什么类型,它将使用较慢的任何类型版本.

请注意,您可以拥有单个函数的多个特化.例如,你可以这样做

{-# SPECIALIZE foo :: [Int] -> Int #-}
{-# SPECIALIZE foo :: [Double] -> Double #-}
{-# SPECIALIZE foo :: [Complex Double] -> Complex Double #-}

现在,只要编译器可以告诉您正在使用其中一种类型,它就会使用硬编码的版本.但是如果编译器无法分辨你正在使用什么类型,它将永远不会使用专用版本,并且永远不会使用多态版本.(这可能意味着您需要专门调用调用的函数foo.)

如果您在编译器的Core输出周围进行爬行,您可以准确地弄清楚它在任何特定情况下的作用.你可能会疯狂地疯狂......

Answer 3

正如其他答案所描述的那样,任何这些都可能在不同情况下发生 对于任何特定的函数调用,唯一可以确定的方法是查看生成的核心.也就是说,在某些情况下,您可以很好地了解将会发生什么.

在单态类型中使用类型类方法.

在类型在编译时完全已知的情况下调用类型类方法时,GHC将在编译时执行查找.例如

isFive :: Int -> Bool
isFive i = i == 5

这里编译器知道它需要Ints Eq字典,因此它会发出代码来静态调用该函数.是否内联该调用取决于GHC通常的内联规则,以及INLINEpragma 是否适用于类方法定义.

揭示多态函数

如果从编译模块中公开了多态函数,那么基本情况是需要在运行时执行查找.

module Foo (isFiveP) where

isFiveP :: (Eq a, Num a) => a -> Bool
isFiveP i = i == 5

GHC实际上做的是将其转换为形式的函数(或多或少)

isFiveP_ eqDict numDict i = (eq_op eqDict) i (fromIntegral_fn numDict 5)

所以函数查找需要在运行时执行.

无论如何,这是基本情况.实际发生的事情是GHC对跨模块内联非常积极. isFiveP足够小,它将被内联到呼叫站点.如果可以在调用站点确定类型,则字典查找将全部在编译时执行.即使在调用站点没有直接内联多态函数,由于GHC通常的函数转换,字典查找仍然可以在编译时执行,如果代码到达一个函数(带有类字典参数)可以的形式适用于静态知名词典.