[haskell] загадочное время исполнения

Landstreicher

Я написал четыре вариант вычисления простых арифметических выражений с переменными.
- eval1 - простой вычислитель на основе монад;
- eval2 - простое вычисление выражения "в лоб";
- compile1 - попытка сделать компиляцию для ускорения;
- compile2 - попытка слегка соптимизировать compile2.
Основной интерес представляло сравнение скорости их работы. Для этого значения выражений вычислялись 1000000 различных наборах переменных. Вот результаты измерений:
- eval1 - 17.47 с
- eval2 - 3.71 с
- compile1 - 3.79 с
- compile2 - 3.74 с
Эти числа поставили меня в тупик.
1) Предполагалось, что eval1 и eval2 будут работать примерно одинаково. В действительности, eval1 в 4.7 раза медленнее, чем eval2.
2) Предполагалось, что compile{1,2} будут работать значительно быстрее, чем eval{1,2} (компиляция vs интерпретация). На практике, никакого ускорения не было обнаружено.
Кто-нибудь может объяснить эти результаты?
Использовался GHC 6.6 on Linux-2.6/Athlon XP/Debian Etch.
Для сравнения - эквивалентная программа на C++ работает за 1.04 с.


import Data.Array.Unboxed

import Data.Array.Base

import Control.Monad.Reader

import Data.Int



foldl' f z []     =  z

foldl' f z (x:xs) =  (foldl' f $! f z x) xs



type Value = Int32

data Expr = Const !Value | Var !Int | Add !Expr !Expr | Sub !Expr !Expr | Mul !Expr !Expr

type Env = UArray Int Value



eval1 :: Expr -> Reader Env Value

eval1 e =

    case e of

      Const c -> return c

      Var n -> do { env <- ask; return $ env ! n }

      Add e1 e2 -> do

             v1 <- eval1 e1

             v2 <- eval1 e2

             return $ v1 + v2

      Sub e1 e2 -> do

             v1 <- eval1 e1

             v2 <- eval1 e2

             return $ v1 - v2

      Mul e1 e2 -> do

             v1 <- eval1 e1

             v2 <- eval1 e2

             return $ v1 * v2



eval2 :: Expr -> Env -> Value

eval2 e env =

    case e of

      Const c -> c

      Var n -> env ! n

      Add e1 e2 -> eval2 e1 env + eval2 e2 env

      Sub e1 e2 -> eval2 e1 env - eval2 e2 env

      Mul e1 e2 -> eval2 e1 env * eval2 e2 env



compile1 :: Expr -> (Env -> Value)

compile1 e =

    case e of

      Const c -> \env -> c

      Var n -> \env -> env ! n

      Add e1 e2 -> \env -> (compile1 e1) env + (compile1 e2) env

      Sub e1 e2 -> \env -> (compile1 e1) env - (compile1 e2) env

      Mul e1 e2 -> \env -> (compile1 e1) env * (compile1 e2) env



compile2 :: Expr -> (Env -> Value)

compile2 e =

    case e of

      Const c -> \env -> c

      Var n -> \env -> env ! n

      Add e1 e2 -> let c1 = compile2 e1 in

                   let c2 = compile2 e2 in

                   \env -> c1 env + c2 env

      Sub e1 e2 -> let c1 = compile2 e1 in

                   let c2 = compile2 e2 in

                   \env -> c1 env - c2 env

      Mul e1 e2 -> let c1 = compile2 e1 in

                   let c2 = compile2 e2 in

                   \env -> c1 env * c2 env



test1 :: Expr

test1 = Add (Mul (Add (Var 0) (Var 1 (Add (Var 0) (Var 1

            (Mul (Sub (Var 0) (Var 1 (Sub (Var 0) (Var 1



test :: Expr

test = Add (Mul test1 test1) (Add test1 test1)



do_test :: (Env -> Value) -> Value

do_test e =

    foldl' (+) 0 (map (\n -> e (array (0, 1) [(0, n (1, n)] [0..1000000])



main = do

  putStrLn "testing empty expr"

  let res0 = do_test (\env -> 0)

  putStrLn $ "result is " ++ show res0

  putStrLn "testing compile 1"

  let res1 = do_test (compile1 test)

  putStrLn $ "result is " ++ show res1

  putStrLn "testing compile 2"

  let res2 = do_test (compile2 test)

  putStrLn $ "result is " ++ show res2

  putStrLn "testing eval 1"

  let res3 = do_test (runReader (eval1 test

  putStrLn $ "result is " ++ show res3

  putStrLn "testing eval 2"

  let res4 = do_test (eval2 test)

  putStrLn $ "result is " ++ show res4

  return

Papazyan

Что касается eval1 и eval2, то такое поведение логично. Монада выполнение не ускоряет, при каждой монадной операции имеется оверхед. И еще надо посмотреть, что из себя представляет Reader, вроде, не сильно быстро работает по определению (помню, где-то предлагали вместо него parsec применять).

Papazyan

Почему compile1 и compile2 должны работать быстрее, не понял. Тебе еще повезло, что они так же как eval2 работают. Ведь по сути это одно и тоже, только первые специально переусложнены.

Marinavo_0507

Почему compile1 и compile2 должны работать быстрее, не понял.
Потому что убирается конструкция case. То есть, ветвления заменяются косвенными вызовами. По идее, это от архитектуры процессора должно зависеть сильно.

Landstreicher

> И еще надо посмотреть, что из себя представляет Reader, вроде, не сильно быстро работает
> по определению (помню, где-то предлагали вместо него parsec применять).
Parsec вместо Reader? Это как?
По определению, Reader e a = e -> a. То есть просто, добавляется один параметр в функцию. По идее eval1 и eval2 должны превращаться в одно и тоже после syntactic desugaring.

Landstreicher

> Потому что убирается конструкция case. То есть, ветвления заменяются косвенными вызовами. По
> идее, это от архитектуры процессора должно зависеть сильно.
IMHO тут ситуация такая
код типа
switch (tag) {
case 1: r = f(x); break;
case 2: r = g(y); break;
заменяется на
r = *h(x);
То есть (case + прямой вызов) на (косвенный вызов). Насколько я понимаю, второе всегда быстрее первого. Можешь привести пример архитектуры, где это не так?

Marinavo_0507

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

Landstreicher

> Судя по тому, что времена выполнения очень близки, дело, наверное, всё-таки не в инструкциях.
> Видимо, какой-то ещё оверхед превышает эту разницу во много раз.
Наверное. Есть какие-то методы это проверить/измерить?
> Может, управление памятью и boxing?
Заменил Int в Int# в половине мест. В остальной половине пока не понял как — на UArray Int# Int# компилятор ругается. Время уменьшилось с 3.71 до 3.58, разница осталась такого же порядка. Надо как-то переписать доступ к переменным и do_test, чтобы без списков обходился.

Papazyan

Фишка может быть в том, что Хаскель сам за счет ленивости реализует поведение compile. (eval2 e) самостоятельный редекс, который будет адаптирован под е. Надо бы тоже самое на OCaml написать, тогда этот вопрос прояснится, но у меня его сейчас нет. Или на Хаскеле вызывать eval2 e env одним выражением для всех env.
Оставить комментарий
Имя или ник:
Комментарий: