Выполнение подвыражения один раз

Хорошо, так что это меня беспокоило какое-то время, поэтому я подумал, что приду и спрошу кого-нибудь, кто мог бы действительно узнать ответ.

Предположим, что у меня есть следующая функция:

foobar x y = expensive x + cheap y

Предположим, что эта часть программы принимает в качестве входных данных foobar 5 и выполняет эту функцию миллионы раз в замкнутом цикле. Ясно, что я хочу, чтобы expensive 5 вычислялся один раз, а не миллион раз.

Я мог оставить код таким, какой он есть, или я могу изменить его на

foobar x = let k = expensive x in \ y -> k + cheap y

Мне это интересно...

  • Является ли GHC достаточно умным, чтобы устранить дублируемую работу? (I.e., делает ли первая версия то, что я хочу?)

  • Если нет, действительно ли вторая версия исправляет проблему? (I.e., оптимизатор просто преобразует его обратно в тот же код, что и первая версия?)

Ответы

Ответ 1

Is GHC smart enough to eliminate the duplicated work by itself? (I.e., does the first version do what I want already?)

Я думаю, что еще один способ задать вопрос: будет ли GHC inline foobar x y, чтобы expensive x делился между вычислениями?

Я спросил аналогичный вопрос, который прояснил несколько вещей, но оставил меня немного неудовлетворенным. Насколько я понимаю, определение того, как и когда делать inline или eta-expand/уменьшать вещи (и при столь тонком изменении поведения/семантики строгости) действительно сложно для компилятора, поэтому GHC в значительной степени зависит от того, как вы синтаксически определили вашу функцию.

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

Ответ 2

Интуитивно мой ответ был бы отрицательным, и да. Но позвольте мне ответить на ваш вопрос, попробовав его. Рассмотрим этот код:

import Debug.Trace

expensive :: Int -> Int
expensive x = trace ("expensive evaluated for " ++ show x) $ x
{-# NOINLINE expensive #-}

cheap :: Int -> Int
cheap x = x
{-# NOINLINE cheap #-}

foobar x y = expensive x + cheap y

foobar' x = let k = expensive x in \ y -> k + cheap y

part f = sum [f i| i<-[0..10]]

main = do
    print $ part (foobar 5)
    print $ part (foobar' 5)

Если мы запустим этот результат, получим

$ ./Test 
expensive evaluated for 5
110
expensive evaluated for 5
110

чтобы компилятор был достаточно умен, чтобы оптимизировать исходную версию. Но почему? Поскольку он ввел определение foobar в main, то заметил, что он мог бы выгрузить выражение expensive 5 из вызова part. Если мы отключим вставку для foobar и foobar' (или, альтернативно, не используем -O), она больше не работает:

$ ./Test 
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
110
expensive evaluated for 5
110

Итак, хотя GHC может в некоторых ситуациях делать правильные вещи, вы всегда должны проверить, действительно ли это так, если вы хотите положиться на нее. Либо используйте такие инструменты, как Debug.Trace, либо просматривая ядро ​​(-ddump-simpl).

Ответ 3

Читая одну из различных статей STG, похоже, что это так называемая полная трансформация лени. Кажется, что [в момент написания статьи] GHC применяет это преобразование, но не все время, так как это может привести к утечке пространства.

Канонический пример:

foo x = map f [1..1000000]

Если мы преобразуем это в

foo x = map f big

big = [1..1000000]

теперь у нас один гигантский CAF, висящий навсегда - что, вероятно, не то, что планировал программист! (Я лично был укушен именно таким образом, на самом деле...)