Почему GHC рассматривает синтаксически LHS * при встраивании?
В соответствии с GHC docs:
... GHC будет только встроить функцию, если она будет полностью применена, где "полностью примененные" средства применяются к множеству аргументов, которые появляются (синтаксически) на LHS определения функции.
Если приведенный пример представляет собой два семантически эквивалентных определения:
comp1 :: (b -> c) -> (a -> b) -> a -> c
{-# INLINE comp1 #-}
comp1 f g = \x -> f (g x)
comp2 :: (b -> c) -> (a -> b) -> a -> c
{-# INLINE comp2 #-}
comp2 f g x = f (g x)
Мои вопросы:
-
Это только при наличии прагм INLINE, что мы получаем это строгое
поведение (т.е. строгий синтаксический взгляд на LHS,
оптимизация)?
-
когда не заданы прагмы INLINE, делает ли GHC когда-либо преобразование функции
как comp2
до comp1
?
-
Если нет, то почему? Это слишком сложно вообще для компилятора посмотреть
в семантике функции и решить, сколько и где
частично применять и INLINE?
-
что произойдет, если GHC просто преобразует все функции в
каскад выражений let... in
с lambdas и отсутствие привязок на
LHS?
Ответы
Ответ 1
Что делать, если в этом примере c
сам по себе является типом функции? Я не понимаю, как ваше предложение будет работать в этом сценарии.
В любом случае, есть определенные случаи, когда вы не хотите, чтобы все аргументы функции "вытягивались на передний план". Например, у вас может быть такой код:
foo :: [Int] -> Int -> Int -> Int
foo list = let
-- expensive precomputation here
bar x y = ...
in \ x y -> bar x y
Вы хотите, чтобы foo
был частично применен, а затем для нескольких приложений получаемой функции, чтобы делиться дорогостоящей работой перед вычислением. Если вместо этого вы вытащили его вперед как foo list x y
, вы не смогли бы поделиться этой дорогостоящей предварительной оценкой. (Я столкнулся с этим случаем в серьезных приложениях.)
Ответ 2
Это хороший вопрос. Я прочитал секреты Glasgow Haskell Compiler Inliner для некоторых подсказок, но не нашел много.
Вот ручное волновое объяснение. GHC на самом деле время от времени принимает comp1
до comp2
- который он называет "eta expansion". См. Эту тему для некоторых деталей: http://www.haskell.org/pipermail/glasgow-haskell-users/2011-October/020979.html
Также существует (или была) проблема, при которой это расширение может тонко изменить строгость. См. Это фиксацию в документах (которые, похоже, не находятся в текущих, поэтому либо они не были восстановлены, либо исправлены, но не уверены, что): http://permalink.gmane.org/gmane.comp.lang.haskell.cvs.ghc/57721
В любом случае приведенный выше поток имеет SPJ, объясняющий, почему мы, как всегда, хотим идти в этом направлении, когда это возможно. Поэтому сознательно идти в другом направлении, чтобы улучшить inlining, кажется немного глупым. Как обсуждается секретная статья, непродуманное вложение не является самой большой идеей - превращение прагмы в более грубый молот, так что функции были включены, независимо от того, имеет ли это смысл делать это, вероятно, повредит больше, чем поможет в целом, не говоря уже об увеличении кода, так как модули должны были бы поддерживать разные уровни функций eta-shifted вокруг всех одновременно.
В любом случае, поскольку кто-то очень не является основным разработчиком GHC, это то, что кажется мне наиболее вероятным.
Ответ 3
Хорошо, лучше поздно, чем никогда. Думаю.
comp1
и comp2
не только эквивалентны семантически, но даже синтаксически.
Написание аргументов на LHS знака равенства означает просто синтаксический сахар, поэтому эти две функции эквивалентны:
id1 x = x
id2 = \x -> x
Изменить: я понял, что не ответил на ваши вопросы, так что вот вы:
-
Существует разница для GHC, когда они аннотируются с помощью INLINE
pragmas, так как GHC хранит в своем представлении Core разворот функции и для которой можно развернуть ее (это часть Guidance=ALWAYS_IF(arity=1,...)
), поэтому на практике это может фактически иметь дело.
-
Я не думаю, что это происходит, поскольку comp1
и comp2
нельзя отличить после desugaring к Core, на котором работают все оптимизации. Поэтому, когда GHC хочет создать новое развертывание, он, вероятно, сделает это для манифестации (например, числа ведущих lambdas).
-
Вкладывание в основном не выгодно для ненасыщенных связей, см. ниже. То же самое касается примера comp1
: причина, по которой мы хотим, чтобы это произошло, заключается не в том, что мы заботимся об устранении вызова функции. Скорее мы хотим, чтобы comp1
был специализирован для параметров f
и g
, независимо от того, какой конкретный x
применяем специализацию. Фактически есть пропуск оптимизации, который должен выполнять такую работу, называемую специализацией конструктора (подробнее об этом ниже). INLINE
является даже довольно неудачным для использования здесь: это все равно не будет специализироваться на вызове типа comp1 (const 5)
, где "очевидно", что это должно быть уменьшено до const 5
.
-
Следовательно, это не сильно изменится, если вы не побрызгаете каждую связанную вещь с помощью INLINE
прагм. Даже тогда это сомнительно, если это приносит какую-либо пользу: дело в том, что просто не имеет смысла встраивать ненасыщенные вызовы без каких-либо дальнейших мотивов (например, специализация функции к конкретному аргументу) и, кроме того, она просто взорвет размер кода при в какой-то момент, поэтому, возможно, это даже может замедлить работу.
Конец редактирования
Одна из причин, почему я считаю, почему ненасыщенные вызовы привязок не включены, заключается в том, что в основном они не приносят никаких новых возможностей оптимизации.
f = \x y -> 1 + (x * y)
g = \x y -> (1 + x) * y
Вложение f 16
дает \y -> 1 + (16*y)
, что на самом деле не намного проще, чем f 16
. Напротив, размер кода значительно увеличился (что является самым большим недостатком вложения).
Теперь, если бы появился вызов типа g 16
, это дало бы \y -> (1 + 16) * y
, который оптимизировался бы до \y -> 17 * y
. Но такие возможности обнаруживаются другим проходом оптимизации, конструктором или специализацией call-pattern. Здесь понимается, что 1 + x
можно упростить, если мы знаем значение x
. Поскольку мы называем g
литералом (например, значением), полезно специализировать g
для этого конкретного сайта вызова, например. g16 = \y -> 17 *y
. Нет необходимости встраивать g
, а также другие сайты вызовов могут совместно использовать код, сгенерированный для g16
.
Это всего лишь один пример того, как сделать инкрустацию не нужно, имея при этом эффективный код. Есть много других оптимизаций, которые во взаимодействии с Inliner достигают того, чего вы хотите. Например, расширение Eta гарантирует, что вызовы будут максимально насыщенными:
main = print (f 2)
f = g 1
g x y = x + y
Так как f
всегда вызывается с 1 аргументом, мы можем его расширять:
f eta = g 1 eta
Теперь вызов g
насыщен и может быть встроен. Dito для f
, поэтому в итоге это уменьшится до
main = print 3
f eta = 1 + eta
g x y = x + y
Удаление мертвого кода Modulo.