Подтвердить что ты не робот

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

В Haskell для определения экземпляра класса типа вам необходимо предоставить словарь функций, требуемых классом типа. То есть для определения экземпляра Bounded вам необходимо предоставить определение для minBound и maxBound.

Для этого вопроса позвоните в этот словарь vtbl для экземпляра класса типа. Дайте мне знать, если это плохая аналогия.

Мой вопрос о том, какого рода генерации кода я могу ожидать от GHC, когда я вызываю функцию класса типа. В таких случаях я вижу три возможности:

  • Поиск vtbl для поиска функции реализации во время выполнения
  • поиск vtbl выполняется во время компиляции, и прямой вызов функции реализации испускается в сгенерированном коде
  • просмотр vtbl выполняется во время компиляции, а функция выполнения встроена на сайт вызова

Я хотел бы понять, когда это происходит, или если есть другие возможности.

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

В запущенной программе кажется, что Haskell знает типы всех функций и выражений в программе. Поэтому, когда я вызываю функцию класса типа, компилятор должен знать, что такое vtbl, и какую именно функцию реализации вызывать. Я ожидаю, что компилятор, по крайней мере, вызовет прямой вызов функции реализации. Это правда?

(я говорю "runnable program" здесь, чтобы отличить его от компиляции модуля, который вы не запускаете.)

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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