haskell n00b question

[thedeemon]

Для одной задачки всхотелось мне сделать интерпретатор крайне простого язычка: есть память на дюжину целых чисел и AST из трех операций - сравнение двух ячеек, копирование из одной в другую и обмен значениями меж двух ячеек. Стал делать на хаскеле и сразу столкнулся с тем, что наивное решение в лоб тормозит: аналогичный код на окамле в 4 раза быстрее, а на Ди - в 10 раз. Вот так выглядит мой позор на хаскеле:

data Exp = IfGt Int Int Block Block
         | Swap Int Int
         | Copy Int Int
         deriving Show

type Block = [Exp] 

eval :: STUArray s Int Int -> Exp -> ST s (STUArray s Int Int, Int)
eval a (IfGt i j b1 b2) = do
  ai <- readArray a i
  aj <- readArray a j
  let b = if ai > aj then b1 else b2
  (r, n) <- evalBlock a b 
  return (r, n+1)
eval a (Swap i j) = do 
  ai <- readArray a i 
  aj <- readArray a j
  writeArray a i aj
  writeArray a j ai
  return (a, 1)  
eval a (Copy i j) = do
  aj <- readArray a j
  writeArray a i aj
  return (a, 1)

evalBlock :: STUArray s Int Int -> Block -> ST s (STUArray s Int Int, Int)
evalBlock a blk = foldM f (a,0) blk where
  f (a,cnt) exp = fmap (\(r, n) -> (r, cnt + n)) $ eval a exp

А вот прямой перевод на Окамл, почти вчетверо быстрее:

type exp = IfGt of int * int * block * block
         | Swap of int * int
         | Copy of int * int
and block = exp list;;

let rec eval a = function
  | IfGt(i, j, b1, b2) -> 
      let (r,n) = evalBlock a (if a.(i) > a.(j) then b1 else b2) in
      (r, n+1)
  | Swap(i, j) -> 
      let ai = a.(i) and aj = a.(j) in
      a.(i) <- aj; a.(j) <- ai; (a, 1)
  | Copy(i, j) -> 
      a.(i) <- a.(j); (a, 1)

and evalBlock a blk = 
  let f (m, cnt) exp = let (r,n) = eval m exp in (r, cnt + n) in
  List.fold_left f (a,0) blk

А теперь вопрос: как хаскельный вариант следует переписать, чтобы он стал побыстрее и выглядел не слишком страшно?

Полные тексты тестов:
Haskell - 7.19 s
OCaml - 1.85 s
D - 0.69 s (использовался DMD - наименее оптимизирующий из компиляторов D, т.е. можно еще быстрее)

Upd: исправлен баг в окамловской версии, время перемеряно.
Upd2: не, не было там бага.

Comments

[kodt-rsdn.livejournal.com]

Наверно, там ленивость сыграла злую шутку, и хаскелл вместо вычислений рожает мега-санки, которые отрабатывают лишь в самом конце. А это удар по памяти, вот и тормоза.
Самле простое - натыкать форсирования вычислений гле только можно (на возврате из eval?) - оператор $! емнип.

[thedeemon.livejournal.com]

А как этот оператор с монадой ST сочетается?
Если что, STUArray - мутабельный строгий анбоксед массив, живущий в ST.
Но где-то санки могут действительно копиться, ибо аллоцируют приведенные функции как черти.

[permea-kra.livejournal.com]

Оптимизации включать пробовали?

[thedeemon.livejournal.com]

-O2
GHC 7.6.3

[permea-kra.livejournal.com]

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

upd. Конкретно, посмотрите вот эту прагму: https://downloads.haskell.org/~ghc/7.0.2/docs/html/users_guide/pragmas.html#unpack-pragma . Потому что у вас в тесте, насколько я понимаю, в АСТ инты завернуты в отдельные танки. Нужно их как миниум распаковать, иначе сравнение нечестное.

[thedeemon.livejournal.com]

data Exp = IfGt {-# UNPACK #-} !Int {-# UNPACK #-} !Int Block Block 
         | Swap {-# UNPACK #-} !Int {-# UNPACK #-} !Int 
         | Copy {-# UNPACK #-} !Int {-# UNPACK #-} !Int 

7.08 s. Крайне незначительное улучшение.

Еще пробовал unsafeRead/unsafeWrite для массива, еще около секунды дало выигрыш, тоже маловато.

[antilamer.livejournal.com]

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

А вообще надо смотреть core.

[udpn.livejournal.com]

Куда смотреть?

[qnikst (from livejournal.com)]

Не стоит использовать foldM из Control.Monad, там нужно минимум добавлять строгости.

Если использовать Data.Foldable то начинает выполняться нормально у меня за 0.05с, при том, что изначальная версия за 5с.

Ссылку на полный код можно найти на форке гиста, т.к. боюсь в жж её не запостить.

UPD. т.е. import Data.Foldable (foldlM) и использовать его вместо foldM.
так же по желанию добавить ! к аккумулятору f, т.е. f (!a, !cnt) ...

UPD2. с Data.Foldable можно оставлять вариант с fmap и убирать там явное вычисление, т.к. ghc уже справляется.

[qnikst (from livejournal.com)]

core, промежуточный код, где используется минимум языка и на котором начинаются оптимизации. Получать по -ddump-simpl (-ddump-to-file).

[udpn.livejournal.com]

Да это понятно, просто при последних экспериментах я ничего из этого не смог завести. Пеняю на Windows. Сейчас пофиксили?

[qnikst (from livejournal.com)]

извиняюсь, что лезу, но я не понял, что именно не завелось. -ddump-simpl -ddump-to-file должно работать, без -ddump-to-file может выводит куда не туда т.к. это промежуточный язык при компиляции кода и без него никак, если версия кода, то тоже странно т.к. даже дополнительные библиотеки вне состава ghc не используются.

К сожалению windows под рукой у меня нету, так что проверить не могу, но ситуация там может быть чуть хуже, чем на linux.

[qnikst (from livejournal.com)]

Ну и как обычно, Array далеко не лучшая штука, что есть в Haskell, поэтому если существует возможность, то лучше использовать пакет vectors и подходящие вектора оттуда. В последней версии gist (https://gist.github.com/qnikst/3517def97f21555dea83) я отвоевал ещё 10% (итого 0.4с), при этом не модифицируя изначальные вектора (что в прочем на таких размерах не важно).

Я попробую еще сделать код поаккуратнее, но думаю, что вопрос в треде он снимать должен.

[jdevelop.livejournal.com]

и вот всегда так в хаскеле - пишешь красивый идиоматичный код, монады там, аппликативы

а в продакшне, матерясь, переписываешь в кашу из бангов и unsafePerformIO на MVar

[qnikst (from livejournal.com)]

попрошу заметить, что ни один использованый функтор и монада не пострадали, а ещё вылез дополнительный бифунктор (чисто для красоты). При этом код не потерял ни долю идиоматичности.. В общем тут чисто вопрос выбора инструментов и знания основных библиотек и их особенностей.

[qnikst (from livejournal.com)]

UPD 4. Я таки решил включить мозг и заметил, что тут в eval и evalBlock идет работа с изменяемым вектором, поэтому никакого смысла возвращать его в результате нет, т.к. у вызывающей функции уже есть этот вектор (и все изменения в нём), исправление этого недоразумения приводит к тому, что код выполняется 0.03с вместо 0.05c.

В очередной версии гиста положено.

[urod.livejournal.com]

> А вот прямой перевод на Окамл, почти вчетверо быстрее

...И вдвое короче.

[stas binko (from livejournal.com)]

Прошу прощения что вмешиваюсь, но я честно говоря просто в шоке от того что такой вот дифф:

+ import Data.Foldable as F hiding (minimum)
- evalBlock a blk = foldM f (a,0) blk where
+ evalBlock a blk = F.foldlM f (a,0) blk where
- calcScore blk = sum $ map (numSteps blk) inputs
+ calcScore blk = F.sum $ map (numSteps blk) inputs

дает разницу в производительности почти в 100 раз (ок, ладно, не в 100, у меня на ноуте в 85).

Не подскажете что читать/куда смотреть/на что обращать внимание на тему понимания производительности вот таких вот штук в х-ле?

Я вот интереса ради пытался профайлить этот пример - непонятно было вообще ничего (разве что кол-во аллокаций памяти смущало - у меня получалось что-то около 14G - но что с этим делать не понял). С одной стороны круто что от х-ля можно получить перфоманс сравнимый с D, с другой стороны выглядит как совершенно непонятный black magic.

[thedeemon.livejournal.com]

O, супер, спасибо!
У меня работает за 0.075 с, т.е. в 95 раз быстрее, чем было, и почти в 10 раз быстрее D. Подозрительно быстро (4 такта на 1 узел AST?), но если это не глюк, то просто чудо.

Upd. нашел обман:
main = print $ minimum $ replicate 40 (calcScore sornet)
тут мы не 40 раз считаем, а лишь один раз. Отсюда и невероятное ускорение.
Если считать на 40 формально отличающихся программах одинакового размера
main = print . minimum . map calcScore $ [Copy 10 (x `mod` 10) : sornet | x <- [1..40]]
то получается 1.40 с, уже реалистичное время. Быстрее окамла, но вдвое медленнее D.

[thedeemon.livejournal.com]

В новом варианте вместо 40 раз считалось 1, отсюда и бешенное ускорение.
Реальное ускорение вышло в 5 раз. Результат несколько быстрее окамла и вдвое медленнее Ди. См. коммент рядом.

[antilamer.livejournal.com]

Разница на самом деле получилась не в 100 раз (см. другой коммент выше по треду), но все равно большая. Подозреваю, дело тут в том, что foldM - это правая свертка (ленивая, строящая большую телегу из thunk'ов, а потом ее вычисляющая), а fold*l*M - левая (Data.Foldable, видимо, нужен лишь для того, что в Control.Monad левой свертки нету, а в Data.Foldable есть). См. классический пример foldr (+) 0 [0..1000000] против foldl' (+) 0 [0..1000000].
Замена sum на F.sum тут, скорее всего, роли не играет - насколько я понимаю, этот sum в масштабах этой программы вызывается редко и на маленьких списках.

[qnikst (from livejournal.com)]

В собственную защиту скажу, что последнее я оставил т.к. у меня эффекта не давало и 7.8 и так замечал этот обманобман и применял его.

В принципе мне кажется там можно ещё попробовать поускорять, но это будет чёрная магия.

[antilamer.livejournal.com]

Еще чуть побыстрее становится, если Exp сделать всячески строгим (на моей машине 0.8 => 0.7с). И еще (0.53с) вот так: https://gist.github.com/jkff/7d85da1e409c8725f282

[qnikst (from livejournal.com)]

Отвечу чуть больше чем просится. Обычно не здоровое поведение Haskell обозначает thunk-leak (часто называют memory leak) и я оно вызвано слишком ленивым кодом.

Обычно первые кандидаты на просмотр это функции с аккумулятором, как в данном случае верно заметил [user]antilamer[/user]. В таких функциях хорошо бы чтобы в документации было написано про Свёрток бывает 2:
1. Правая свертка (foldlr) (1+(1+..)), такая свертка удобна тогда когда функция ленивая по второму аргументу
2. Левая свёртка (foldl) ((1+..)+1) эта свертка удобна для строгих функций.

Если эти правила не выполняются, то возможна излишняя ленивость и потребление памяти. В данном случае мы имеем дело с левой сверткой без форсирования вычисления аккумулятора (аналог foldl), такая функция будет гарантировано слишком ленивой и для неёнеё (почти) никогда нету мест применения (см. блог у well typed).
Соответственно решение заключается в том, чтобы сделать аккумулятор строгим, напр. переписав foldM с явным `seq` аккумулятора, но или использованием готового библиотечного.

Однако проблему это не устранит, т.к. мы возвращаем кортеж, а как известно поля кортежа ленивые и форсирование значений идёт до WHNF ((,) undefined undefined) то просто строгости не хватит и надо чтобы ещё и поля вычислялиствычислялись, что и сделано с помощью BangPatterns.

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

P.S. набиралось с телефона, так что извиняюсь за опечатки, если будет возможность - поправлю.

[thedeemon.livejournal.com]

Да, 7.6 при чуть другой расстановке . и $ тоже это дело оптимизирует до однократного вычисления.