Генерация кода GHC для вызовов функций класса типов

Как и на все хорошие вопросы, ответ «это зависит». Эмпирическое правило состоит в том, что любой код, полиморфный по классам типов, требует времени выполнения. Однако авторы библиотек имеют большую гибкость в устранении этих затрат с помощью правил перезаписи GHC, и, в частности, существует {-# SPECIALIZE #-} pragma, которая может автоматически создавать мономорфные версии полиморфных функций и использовать их всякий раз, когда предполагается, что полиморфная функция может использоваться в мономорфном типе. (Я думаю, цена за это - размер библиотеки и исполняемого файла.)

Вы можете ответить на свой вопрос для любого конкретного сегмента кода, используя флаг -ddump-simpl ghc. Например, вот короткий файл 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)
  }

Также автор библиотеки может решить переписать полиморфную функцию в вызов мономорфной, но не встраивать реализацию мономорфной; это означает, что все предложенные вами возможности (и даже больше) возможны.

Если компилятор может «сказать» во время компиляции, какой фактический тип вы используете, то поиск метода происходит во время компиляции. В противном случае это происходит во время выполнения. Если поиск происходит во время компиляции, код метода может быть встроенным, в зависимости от размера метода. (Это относится и к обычным функциям: если компилятор знает, какую функцию вы вызываете, он встроит ее, если эта функция «достаточно мала».)

Рассмотрим, например, (sum [1 .. 10]) :: Integer. Здесь компилятор статически знает, что список представляет собой список Integer дублей, поэтому он может встроить функцию + для Integer. С другой стороны, если вы сделаете что-то вроде

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

затем, когда вы вызываете sum, компилятор не знает, какой тип вы используете. (Это зависит от того, какой тип задан для foo), поэтому он не может выполнять поиск во время компиляции.

С другой стороны, используя прагму {-# SPECIALIZE #-}, вы можете сделать что-то вроде

{-# 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 компилятора, вы, вероятно, сможете точно определить, что он делал в каждом конкретном случае. Вы, наверное, сойдете с ума, хотя...

Как описывают другие ответы, любое из них может произойти в разных ситуациях. Для любого конкретного вызова функции единственный способ убедиться в этом — посмотреть на сгенерированное ядро. Тем не менее, есть некоторые случаи, когда вы можете получить хорошее представление о том, что произойдет.

Использование метода класса типов для мономорфного типа.

Когда метод класса типа вызывается в ситуации, когда тип полностью известен во время компиляции, GHC выполнит поиск во время компиляции. Например

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

Здесь компилятор знает, что ему нужен словарь Ints Eq, поэтому он создает код для статического вызова функции. Будет ли этот вызов встроенным, зависит от обычных правил встраивания GHC и от того, применяется ли прагма INLINE к определению метода класса.

Предоставление полиморфной функции

Если полиморфная функция предоставляется из скомпилированного модуля, то в базовом случае поиск должен выполняться во время выполнения.

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, если код когда-либо достигает формы, в которой функция (с параметрами словаря класса) может применяться к статически известному словарю.