Оптимизация в Haskell

1. нет. попробуй, к примеру, посчитать числа фибоначчи рекурсией

2. modifyIORef' i (+1)

upd: во 2-м со штрихом, потому что при использовании нестрогой версии без штриха из-за лени возникают проблеы с памятью

Всегда ли чистые функции для одинаковых аргументов выполняются один раз?

Наоборот это почти всегда не так.

modifyIORef

Так она новое значение не возвращает. Получается что-то вроде

modifyIORef' i (+1)
readIORef i >>= return

Наоборот это почти всегда не так.

А тогда в чём преимущество от того, что они чистые? Причём мемоизацию, я так понимаю, только через unsafePerformIO можно сделать?

Тогда уж так

modifyIORef' i (+1) >> readIORef i

Тогда уж так

Спасибо!

Наоборот это почти всегда не так.

Нашёл https://wiki.haskell.org/Memoization

Спасибо!

А тогда в чём преимущество от того, что они чистые?

Что ты в данном контексте называешь «чистые»?

Причём мемоизацию, я так понимаю, только через unsafePerformIO можно сделать?

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

facts :: [Integer]
facts = scanl (*) 1 [1..]

Что ты в данном контексте называешь «чистые»?

Для одинаковых аргументов возвращает одинаковые значения. Например, в моём примере

f yy = (yy, myCalc $ head yy)
g = (myCalc y, f [y])

=>

g = (myCalc y, ([y], myCalc $ head [y]))

=>

g = (myCalc y, ([y], myCalc y))

=>

g = (x, ([y], x))
where x = myCalc y

Встретилась ситуация, где нужен аргумент и результат вычислений. Если передавать результат вычислений, то это дополнительный аргумент ко всем функциям. Функция String -> String, поэтому трюк со списком не сработает, а делать Data.Map — перебор.

А тогда в чём преимущество от того, что они чистые?

В reference transparency. Компилятор спокойно может преобразовывать соовтетствующие термы => проще делать оптимизации

Компилятор спокойно может преобразовывать соовтетствующие термы => проще делать оптимизации

Я надеялся, что такую оптимизацию он может делать.

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

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

Я имел в виду не кэширование, а ситуации типа myCalc $ head $ [y] <==> myCalc y. То есть, когда несколько вызовов сводятся подстановкой к одному параметру, но при этом находятся в разных функциях.

Про кэширование уже понял.

Я имел в виду не кэширование, а ситуации типа myCalc $ head $ [y] <==> myCalc y.

В случае myCalc $ head $ [y] компилятор скорее всего заинлайнит head $ [y], с-но получится myCalc y, но кажется ты в ОП-посте не про это говорил.

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

кажется ты в ОП-посте не про это говорил

Я в ОП-посте привёл конкретный пример. Просто для одной функции можно добавить where и всё однозначно, а для двух-трёх уже (насколько я знаю) никак. Можно передавать через дополнительную переменную или поле параметра, но это неоправданно усложняет код

компилятор скорее всего заинлайнит

Вот и хотелось узнать, «скорее всего заинлайнит» или «заинлайнит» и вычисления myCalc в двух местах сведёт к одному вызову или нет. Есть где-то формальное описание?

Лучше тогда так:

Prelude Data.IORef> ref <- newIORef 1
Prelude Data.IORef> atomicModifyIORef' ref (\i -> let i' = i+1 in (i',i'))
2

atomicModifyIORef

Красиво. А в документации про возвращаемое значение ничего не сказано :-( Вообще, документация по пакетам Haskell какая-то очень лаконичная. Или кроме http://hackage.haskell.org/ что-то ещё есть?

В подавляющем большинстве случаев нет. С другой стороны, в случае с atomicModifyIORef из типа и так всё ясно, не?

atomicModifyIORef :: IORef a -> (a -> (a, b)) -> IO b

практичный вариант выглядит, видимо, так:

modifyAndReturn ref f = atomicModifyIORef' ref $ (\i -> (i,i)) . f

Вот и хотелось узнать, «скорее всего заинлайнит» или «заинлайнит» и вычисления myCalc в двух местах сведёт к одному вызову или нет. Есть где-то формальное описание?

так в случае myCalc $ gead $ [y] только один вызов в любом случае, хоть инлайнить хоть не инлайнить

С другой стороны, в случае с atomicModifyIORef из типа и так всё ясно, не?

А для типа

after :: Extract source => Int -> source -> source

Вот такой же тип:

Prelude Data.IORef> let modify ref f = atomicModifyIORef ref (\a -> (fst (f a), snd (f (fst (f a)))))
Prelude Data.IORef> :t modify
modify :: IORef a -> (a -> (a, b)) -> IO b

так в случае myCalc $ gead $ [y] только один вызов в любом случае

Вот пример:

f yy = (yy, myCalc $ head yy)
g = (myCalc y, f [y])

Здесь при вычислении g, сколько раз myCalc выполнится?

Всегда ли чистые функции для одинаковых аргументов выполняются один раз?

нет.

т.е. [код] обязан скомпилироваться в одно и тоже

Точно не *обязан*. А именно этот код вообще не скомпилирутся, т.к. в g нету y. Но если исправить, то вполне может. Вообще если это волнует, то смотреть в core.

можно ли сделать короче?

modifyIORef', если в многопоточном окружении то atomicallyModifyIORef'

я должен предположить, что after возвращает свой второй аргумент?

Нет, т.к. в типе есть Extract source.

modify :: IORef a -> (a -> (a, b)) -> IO b здесь тип не такой же.

А именно этот код вообще не скомпилирутся, т.к. в g нету y

Также как и myCalc. Предполагается, что y и myCalc определены выше.

Вообще если это волнует, то смотреть в core.

Можешь ссылку дать?

Также как и myCalc. Предполагается, что y и myCalc определены выше.

ok.

Можешь ссылку дать?

это параметр компиляции -ddump-simpl, покажет представление в core language.

покажет представление в core language.

Что-то загадочное он показывает.

Попробовал сделать

$ cat Test.hs
module Test where

y = 123
myCalc x = x*x+x

f yy = (yy, myCalc $ head yy)
g = (myCalc y, f [y])

Получил

a_rhj =
  GHC.Num.+
    @ GHC.Integer.Type.Integer
    GHC.Num.$fNumInteger
    (GHC.Num.*
       @ GHC.Integer.Type.Integer GHC.Num.$fNumInteger Test.y Test.y)
    Test.y

...

a1_rhl =
  GHC.Base.$
    @ GHC.Integer.Type.Integer
    @ GHC.Integer.Type.Integer
    (Test.myCalc @ GHC.Integer.Type.Integer GHC.Num.$fNumInteger)
    (GHC.List.head @ GHC.Integer.Type.Integer yy_rhk)


a2_rhm = (yy_rhk, a1_rhl)
...
Test.g = (a_rhj, a2_rhm)

Я правильно понял, что оптимизации не получилось и вычисляется дважды?

Ай, затупил. Надо не просто -ddump-simpl, а -ddump-simpl -O2. Тогда работает

Здесь при вычислении g, сколько раз myCalc выполнится?

Компилятор может сделать common subexpression elimination, а может не сделать. Зависит исключительно от реализации компилятора.

хотя бы -O

Да, пишем *высокоуровневом языке*. А интересно, кто на асме пишет, больше с бубнами вокруг кода бегают или меньше?

Да, пишем *высокоуровневом языке*.

Так писать на нём проще. Но чтобы программа выполнялась быстро, надо представлять, что под капотом.

А интересно, кто на асме пишет, больше с бубнами вокруг кода бегают или меньше

При желании оптимизировать — больше. Так как развёртка циклов и отслеживание регистров по критерию «как быстрее» превращают код в кашу.

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

Тут нужно понимать три момента.

М1. Если встречаются в одном месте два выражения f x и еще один f x, то при оптимизации O2, скорее всего, f x будет вычислен всего один раз, а результат использован дважды. Это из-за ссыльной прозрачности (которая является достаточным условием чистоты).

Еще до кучи, раз уж ты упомянул мемоизацию в треде, пункт номер M2:

M2. В хаскеле широко используется такая техника как мемоизация. Чем глубже будешь копать, тем чаще будешь ее встречать. Это fix, MonadFix и ArrowLoop.

Значение сначала представляется как еще невычисленный thunk. Значит, значение может зависеть от самого себя. Когда приходит необходимость, thunk раскрывается и далее при ссылке на него возвращается уже вычисленный thunk, даже если этот thunk зависит от самого себя. Так работают рекурсивные вычисления.

M3. Компилятор Haskell генерирует эффективный код, а потому всякой фигней не занимается типа поиска одинаковых аргументов. Не жди от него того, чего он предоставить не может.

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

Немного в сторону. Тут есть такая интересная штука, связанная с thunk и многопоточностью, которая меня просто обескураживает. Думаю, тебе понравится :)

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

Теперь многопоточность. Как раскрыть thunk, если он используется одновременно из нескольких потоков? В других языках, например, Lazy<T> из .NET, используются блокировки, потому что там нет ссылочной прозрачности. В Haskell не так. Мы можем оптимизировать. Есть специальная техника, которая, кажется, называется black holes. В детали особо не вдавался. Если даже и используются блокировки, то не на таком уровне, как в .NET. А блокировки - это безусловный тормоз.

В общем, Haskell таит в себе много интересного :)

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

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

Есть специальная техника, которая, кажется, называется black holes.

Black Hole - это заглушка вместо thunk'а, который вычисляется в данный момент. То есть, цепочка выглядит так: thunk -> black hole -> value. По сути это и есть блокировка.

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

Нет, если внутри thunk'а нет какого-нибудь unsafePerformIO. Небольшие функции намного быстрее вычислить несколько раз, чем обеспечивать синхронизацию тредов.

Компилятор Haskell генерирует эффективный код

А че он тогда отжирает столько памяти и такой ужасно медленный?

Теперь многопоточность. Как раскрыть thunk, если он используется одновременно из нескольких потоков? В других языках, например, Lazy<T> из .NET, используются блокировки, потому что там нет ссылочной прозрачности. В Haskell не так. Мы можем оптимизировать. Есть специальная техника, которая, кажется, называется black holes. В детали особо не вдавался. Если даже и используются блокировки, то не на таком уровне, как в .NET. А блокировки - это безусловный тормоз.

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

Нет, если внутри thunk'а нет какого-нибудь unsafePerformIO. Небольшие функции намного быстрее вычислить несколько раз, чем обеспечивать синхронизацию тредов.

Абсолютно ВСЕ вычисления, которые совершаются во время исполнения твоей программы, находятся внутри ИО. Если ф-я не внутри ИО, то она просто не будет никогда вычисляться.

Чем плох ЛОР, так это тем, что все время какое-нибудь какой-нибудь аноним вылазит.

Кстати, не знаешь, почему в Haskell в многострочных списках запятая ставится в начале? Чем

   [ 1
   , 2
   , 3 ]

лучше чем

   [ 1,
     2,
     3 ]

module Test (g) where

cse_me :: Int -> Int
cse_me x = x * (x + x * x) + x

g :: Int -> (Int, Int)
g z = (cse_me z, cse_me z)

Для изучения высокоуровневых оптимизаций можно юзать всякие '-ddump-*' ключи ('ghc --show-options | grep ddump').

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

Посмотрим, что делает ghc:

$ ghc -c Test.hs -Wall -fforce-recomp -O2 -ddump-cse -ddump-rule-firings -ddump-inlinings -dsuppress-all -ddump-simpl -dsuppress-uniques -ddump-stg

Специализирует полиморфные операторы:

Rule fired: Class op *
Rule fired: Class op +
Rule fired: Class op *
Rule fired: Class op +
Inlining done: $fNumInt_$c+
Inlining done: $fNumInt_$c*
Inlining done: $fNumInt_$c+
Inlining done: $fNumInt_$c*

CSE pass не находит дубля:

==================== Common sub-expression ====================
Result size of Common sub-expression
  = {terms: 22, types: 12, coercions: 0}

cse_me
cse_me =
  \ x -> case x of wild { I# x -> I# (+# (*# x (+# x (*# x x))) x) }

g
g = \ z -> (cse_me z, cse_me z)

и в STG так и остается два вызова 'cse_me':

cse_me =
    \r srt:SRT:[] [x]
        case x of _ {
          I# x1 ->
              case *# [x1 x1] of sat {
                __DEFAULT ->
                    case +# [x1 sat] of sat {
                      __DEFAULT ->
                          case *# [x1 sat] of sat {
                            __DEFAULT -> case +# [sat x1] of sat { __DEFAULT -> I# [sat]; };
                          };
                    };
              };
        };
g = \r srt:SRT:[] [z]
        let { sat = \u srt:SRT:[] [] cse_me z; } in
        let { sat = \u srt:SRT:[] [] cse_me z; } in  (,) [sat sat];

https://ghc.haskell.org/trac/ghc/ticket/2940 - похож на известный баг GHC (функция h) :)

Абсолютно ВСЕ вычисления, которые совершаются во время исполнения твоей программы, находятся внутри ИО.

Это в данном случае не имеет значения.

Видимо, просто кому-то из основоположников нравится такой стиль. Мне так - не очень.

Кстати, не знаешь, почему в Haskell в многострочных списках запятая ставится в начале? Чем

Чтобы отличаться от быдла. Это условный знак для других посанов, что перед тобой реальный посан, чтобы никто вдруг случайно не попутал рамс.