Ответ 1

Вы по сути ответили на свой вопрос, как заявили другие. Но я полагаю, что вам может понадобиться более подробный и конкретный пример того, где использование фазового управления в сочетании с RULES/INLINE полезно. * Вы не видите их вне сильно оптимизированных библиотек, которые часто сложны, поэтому замечательно видеть меньшие случаи.

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

Быстрое введение в катаморфизм

Начнем с Mu, типа фиксированной точки и определения Algebra, который является просто причудливым синонимом функции, которая "деконструирует" значение f a для возврата a.

newtype Mu f = Mu { muF :: f (Mu f) }

type Algebra f a = f a -> a

Теперь мы можем определить два оператора: ffold и fbuild, которые являются высокоразвитыми версиями традиционных операторов foldr и build для списков:

ffold :: Functor f => Algebra f a -> Mu f -> a
ffold h = go h 
  where go g = g . fmap (go g) . muF
{-# INLINE ffold #-}

fbuild :: Functor f => (forall b. Algebra f b -> b) -> Mu f
fbuild g = g Mu
{-# INLINE fbuild #-}

Грубо говоря, ffold разрушает структуру, определенную Algebra f a, и дает a. fbuild вместо этого создает структуру, определенную ее Algebra f a, и дает значение Mu. Это значение Mu соответствует любому рекурсивному типу данных, о котором вы говорите. Как и обычные foldr и build: мы деконструируем список, используя его минусы, и мы также создаем список, используя его минусы. Идея состоит в том, что мы просто обобщили эти классические операторы, чтобы они могли работать над любым рекурсивным типом данных (например, списками или деревьями!)

Наконец, существует закон, который сопровождает эти два оператора, которые будут вести наш общий RULE:

forall f g. ffold f (build g) = g f

Это правило существенно обобщает оптимизацию обезлесения/слияния - удаление промежуточной структуры. (Я полагаю, что доказательство правильности указанного закона оставлено как упражнение для читателя. Должно быть довольно легко с помощью эквациональных рассуждений.)

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

data ListF a f = Nil | Cons a f
  deriving (Eq, Show, Functor)
type List a = Mu (ListF a)

instance Eq a => Eq (List a) where
  (Mu f) == (Mu g) = f == g

lengthL :: List a -> Int
lengthL = ffold g
  where g Nil = 0
        g (Cons _ f) = 1 + f
{-# INLINE lengthL #-}

И мы также можем определить функцию map:

mapL :: (a -> b) -> List a -> List b
mapL f = ffold g
  where g Nil = Mu Nil
        g (Cons a x) = Mu (Cons (f a) x)
{-# INLINE mapL #-}

Встраивание FTW

Теперь у нас есть средство записи термов по этим рекурсивным типам, которые мы определили. Однако, если бы мы должны были написать такой термин, как

lengthL . mapL (+1) $ xs

Тогда, если разложить определения, мы по существу получим композицию из двух операторов ffold:

ffold g1 . ffold g2 $ ...

И это означает, что мы на самом деле уничтожаем структуру, а затем восстанавливаем ее и снова уничтожаем. Это действительно расточительно. Кроме того, мы можем переопределить mapL в терминах fbuild, поэтому он, мы надеемся, сработает с другими функциями.

Ну, у нас уже есть наш закон, поэтому a RULE в порядке. Пусть кодифицирует, что:

{-# RULES
-- Builder rule for catamorphisms
"ffold/fbuild" forall f (g :: forall b. Algebra f b -> b).
                  ffold f (fbuild g) = g f
-}

Далее мы переопределим mapL в терминах fbuild для целей слияния:

mapL2 :: (a -> b) -> List a -> List b
mapL2 f xs = fbuild (\h -> ffold (h . g) xs)
  where g Nil = Nil
        g (Cons a x) = Cons (f a) x
{-# INLINE mapL2 #-}

Ааааа и мы закончили, да? Неправильно!

Фазы для удовольствия и прибыли

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

lengthL . mapL2 (+1) $ xs

Мы хотели бы, чтобы определения lengthL и mapL2 были вложены, так что правило ffold/fbuild может запускать послесловия по телу. Поэтому мы хотим перейти к:

ffold f1 . fbuild g1 ...

через inlining, а затем перейдите к:

g1 f1

через наш RULE.

Ну, это не гарантировано. По сути, в одной фазе упрощения GHC может не только встраивать определения lengthL и mapL, но также может встраивать определения ffold и fbuild на свои сайты использования. Это означает, что у ПРАВИЛА никогда не будет возможности стрелять, так как фаза "сожрала" все соответствующие идентификаторы и вложила их в ничто.

Наблюдение состоит в том, что мы хотели бы как можно позже вставить ffold и fbuild. Таким образом, мы постараемся предоставить как можно больше возможностей для нашего ПРАВИЛА для стрельбы. И если этого не произойдет, тогда тело вступит в силу, и GHC все равно приложит все усилия. Но, в конечном счете, мы хотим, чтобы это было поздно; RULE сохранит нам большую эффективность, чем любая умная оптимизация компилятора.

Итак, здесь исправить аннотацию ffold и fbuild и указать, что они должны срабатывать только на этапе 1:

ffold g = ...
{-# INLINE[1] ffold #-}

fbuild g = ...
{-# INLINE[1] fbuild #-}

Теперь mapL и друзья будут вставлены очень рано, но они придут очень поздно. GHC начинается с некоторого номера фазы N, а числа фаз уменьшаются до нуля. Фаза 1 является последней фазой. Также возможно встроить fbuild/ffold раньше фазы 1, но это по существу означает, что вам нужно начать увеличивать количество фаз, чтобы компенсировать это, или начать убеждаться, что ПРАВИЛО всегда срабатывает на более ранних этапах.

Заключение

Вы можете найти все это и многое другое в моей статье **, со всеми упомянутыми определениями и примерами здесь. В нем также приведен критерий критерия нашего примера: с помощью наших фазовых аннотаций GHC может сократить время выполнения lengthL . mapL2 пополам по сравнению с lengthL . mapL1, когда срабатывает RULE.

Если вы хотите увидеть это самостоятельно, вы можете скомпилировать код с помощью -ddump-simpl-stats и увидеть, что правило ffold/fbuild запущено во время конвейера компиляции.

Наконец, большинство тех же принципов применяются к библиотекам, таким как vector или bytestring. Хитрость заключается в том, что у вас может быть несколько уровней вложения здесь и намного больше правил. Это связано с тем, что методы, такие как слияние потоков/массивов, имеют тенденцию эффективно сливать циклы и массивы повторного использования - в отличие от здесь, где мы просто делаем классическое обезлесение, путем удаления промежуточной структуры данных. В зависимости от традиционного "шаблона" генерируемого кода (скажем, из-за векторизованного, параллельного понимания списка), может быть очень полезно чередовать или, в частности, оптимизацию фазы таким образом, что очевидные недостатки устраняются ранее. Или оптимизируйте для случаев, когда a RULE в сочетании с INLINE приведет к увеличению RULE (следовательно, пошаговые фазы, которые вы видите иногда - это в основном чередует фазу вставки.) По этим причинам вы также можете управляйте фазами, в которых срабатывает a RULE.

Итак, в то время как RULE с фазами может сэкономить нам много времени, они могут потратить много времени, чтобы получить право. Вот почему вы часто видите их только в самых "высокопроизводительных", сильно оптимизированных библиотеках.

Примечания

• * Ваш первоначальный вопрос: "Какие функции выигрывают от контроля фазы", ​​который мне звучит как "спрашивать", какие функции выигрывают от постоянного устранения подвыражения ". Я не уверен, как точно ответить на это, если это возможно! Это скорее часть компилятора, чем любой теоретический результат о том, как действуют функции или программы - даже с помощью математических законов, а не для всех" оптимизаций "есть ожидаемые результаты. В результате ответ действительно" вы, вероятно, знаете, когда пишете и сравниваете его".

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

Ответ 2

Во-первых, я должен отметить, что поведение GHC по умолчанию в большинстве случаев является оптимальным. Если у вас нет проблемы, вы, вероятно, лучше всего позволяете очень умным людям, которые думают о haskell весь день каждый день, в основном правы (P.S. Я не из тех людей), но вы спросили...

В моем понимании есть две причины для использования этого.

• Сделайте программу более быстрой сближением с ней:

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

• Избегайте сближения с локальным минимумом

  Есть случаи, когда применение правила A предотвратит применение лучшего правила B. Тогда важно, чтобы B приходилось до A. Правила оптимизации по умолчанию хорошо разработаны, чтобы избежать этой проблемы, но, как говорится в документации, они также очень консервативны. По мере добавления дополнительных правил вы неизбежно начнете нарушать другие возможные оптимизации. Затем вам нужно найти место в цепочке правил, где этого не произойдет. Насколько мне известно, единственный способ рассказать - это пробная версия и ошибка.