Почему полиморфизм настолько дорог в haskell (GHC)?

Ответ 1

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

Для крошечной функции, такой как линейная, очень вероятно, что она будет вставляться каждый раз, когда она будет вызвана, что приведет к отсутствию накладных расходов полиморфизма и небольшому дублированию кода - скорее, подобно шаблону С++. Для большей, более сложной полиморфной функции могут быть некоторые затраты. В общем, компилятор решает это, а не вы - если вы не хотите начать поливать прагмы вокруг места.;-) Или, если вы фактически не используете какой-либо полиморфизм, вы можете просто предоставить все мономорфные сигнатуры типов...

Ответ 2

С полиморфным кодом обычно существует компромисс между размером кода и скоростью кода. Либо вы создаете отдельную версию того же кода для каждого типа, на котором он будет работать, что приводит к увеличению кода, либо вы создаете одну версию, которая может работать на нескольких типах, что будет медленнее.

С++ реализации шаблонов выбирают в пользу увеличения скорости кода за счет увеличения размера кода. По умолчанию GHC принимает противоположный компромисс. Тем не менее, можно получить GHC для выпуска отдельных версий для разных типов, используя прагмы SPECIALIZE и INLINABLE. Это приведет к полиморфному коду, который имеет скорость, аналогичную мономорфному коду.

Ответ 3

Я хочу дополнить ответ Dirk, сказав, что INLINABLE обычно рекомендуется по SPECIALIZE. Аннотация INLINABLE для функции гарантирует, что модуль экспортирует исходный код функции, чтобы он мог быть специализированным в точке использования. Обычно это устраняет необходимость предоставления отдельных прагм SPECIALIZE для каждого случая использования.

В отличие от INLINE, INLINABLE не изменяет эвристику оптимизации GHC. Он просто говорит: "Пожалуйста, экспортируйте исходный код".