thedeemon | haskell n00b question

Для одной задачки всхотелось мне сделать интерпретатор крайне простого язычка: есть память на дюжину целых чисел и 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: не, не было там бага.

Flat | Top-Level Comments Only

From:

kodt-rsdn.livejournal.com

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

From:

thedeemon.livejournal.com

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

From:

permea-kra.livejournal.com

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

From:

thedeemon.livejournal.com

-O2
GHC 7.6.3

Edited Date: 2015-01-05 06:16 pm (UTC)

From:

permea-kra.livejournal.com

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

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

Edited Date: 2015-01-05 06:32 pm (UTC)

From:

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 для массива, еще около секунды дало выигрыш, тоже маловато.

From:

antilamer.livejournal.com

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

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

From:

udpn.livejournal.com

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

From:

qnikst (from livejournal.com)

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

haskell n00b question

Page Summary

Style Credit

Expand Cut Tags