LINUX.ORG.RU

Haskell, монады, память, и все-все-все

 ,


7

2

Есть задача - пройтись по текстовому файлу и найти максимальное число одинаковых последовательно идущих строчек. Задача весьма синтетическая, просто надо продемонстрировать, что

  • Потоково обрабатывается некий объем данных;
  • Есть состояние - надо помнить предыдущую строку в файле при обращении к следующей.

Решение в лоб на IORef-ах (m1.hs):

module Main where

import Data.IORef
import Control.Monad (forM)

main :: IO ()
main = do
   input    <- getContents
   lastLine <- newIORef (Nothing)
   counter  <- newIORef (0)
   result   <- newIORef (0)

   let incr    = modifyIORef counter (\x -> x `seq` x+1)
       reset s = do c <- readIORef counter
                    r <- readIORef result
                    writeIORef result (max c r)
                    writeIORef lastLine (Just s)
                    writeIORef counter  1

   forM (lines input) $ \line -> do
     ml <- readIORef lastLine
     case ml of
       (Just s) -> if s == line then incr else reset line
       Nothing  -> reset line

   r <- readIORef result
   putStrLn $ "Largest subsequence of equal lines: " ++ show r

Более модное решение с трансформером StateT (m2.hs):

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Main where

import Control.Monad (forM)
import Control.Monad.State.Strict

data AppContext = AppContext { ctxLastLine :: Maybe String
                             , ctxCounter  :: Integer
                             , ctxResult   :: Integer
                             }

initialContext :: AppContext
initialContext = AppContext { ctxLastLine = Nothing
                            , ctxCounter  = 0
                            , ctxResult   = 0
                            }

newtype App a = App (StateT AppContext IO a)
                deriving (Monad, MonadIO, MonadState AppContext)

runApp (App app) = execStateT app

incr :: App ()
incr = do
   cnt <- gets ctxCounter
   modify $ \s -> s { ctxCounter = cnt+1 }

reset :: String -> App ()
reset l = do
   cnt <- gets ctxCounter
   res <- gets ctxResult
   modify $ \s -> s { ctxLastLine = Just l
                    , ctxCounter  = 1
                    , ctxResult   = max res cnt
                    }

processLine :: String -> App ()
processLine line = do
   ll <- gets ctxLastLine
   case ll of
      (Just s) -> if line == s then incr else reset line
      Nothing  -> reset line

main :: IO ()
main = do
   input <- getContents
   s <- runApp (forM (lines input) processLine) initialContext
   putStrLn $ "Largest subsequence of equal lines: " ++ show (ctxResult s)

Интересно, как поведут себя оба варианта на обработке, скажем, «Улисс» Джойса (txt, 1.6 MB):

[dmatveev@localhost memq]$ ghc --make m1.hs -rtsopts -prof
[1 of 1] Compiling Main             ( m1.hs, m1.o )
Linking m1 ...
[dmatveev@localhost memq]$ ghc --make m2.hs -rtsopts -prof
[1 of 1] Compiling Main             ( m2.hs, m2.o )
Linking m2 ...
[dmatveev@localhost memq]$ du -sh ulysses.txt
1.6M    ulysses.txt
[dmatveev@localhost memq]$ wc -l ulysses.txt
33055 ulysses.txt
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m1 +RTS -hd -i0.001
Largest subsequence of equal lines: 5

real    0m1.599s
user    0m1.577s
sys     0m0.021s
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m2 +RTS -hd -i0.001
Largest subsequence of equal lines: 5

real    0m19.360s
user    0m19.123s
sys     0m0.091s

ШОК! Посмотрим, что там с памятью:

[dmatveev@localhost memq]$ hp2ps -e8in -c m1.hp
[dmatveev@localhost memq]$ hp2ps -e8in -c m2.hp

m1.png, m2.png

Очевидно, что во втором примере что-то течёт, а я что-то глобально упустил.

Вопросы:

  1. ЧЯДНТ?
  2. Как быть?
  3. Как правильно готовить монадические ивентлупы с изменяемым состоянием?

З.Ы. Да, я знаю, что на awk это решается проще и быстрее, суть-то не в этом, а в вопросе №3. Извините за неровный почерк.

★★★★★

Чуть не забыл, ghc 7.0.4 (то, что есть под рукой)

yoghurt ★★★★★ ()

Код не читал, но это не хацкель. В IORef значение ленивое и нужно его форсить руками иначе ьедет thunk leak. Код на хацкеле напишу чуть позже.

qnikst ★★★★★ ()
Последнее исправление: qnikst (всего исправлений: 1)
Ответ на: комментарий от qnikst

В IORef значение ленивое и нужно его форсить руками

\x -> x `seq` x+1 же есть (в моей base версии нет strict-варианта). Или этого недостаточно?

Код не читал, но это не хацкель.

Прочитай вопросы (в конце) и то, что нужно продемонстрировать (в начале). Меня не интересуют бесточечные однострочники :) Меня интересует именно вот такая императивщина.

yoghurt ★★★★★ ()

Можно использовать Conduit, ну просто чтобы не изобретать велосипед и не ломать голову над теми проблемами над которым ломали голову авторы https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-week/con...

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

zinfandel ★★ ()
Последнее исправление: zinfandel (всего исправлений: 1)
Ответ на: комментарий от yoghurt

Или этого недостаточно?

вроде нет, или atomicModifyIORef', или посмотри как сделана строгая версия в новых base. Т.к. тут у тебя `seq` внутри функции модификации, а должен быть снаружи.

имеративщина

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

qnikst ★★★★★ ()
Ответ на: комментарий от zinfandel

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

qnikst ★★★★★ ()
Ответ на: комментарий от yoghurt

Действительно, даже в m1.hs был маленький танк лик, спасибо за замечание. Наверное пофиксил:

module Main where

import Data.IORef
import Control.Monad (forM)

main :: IO ()
main = do
   input    <- getContents
   lastLine <- newIORef (Nothing)
   counter  <- newIORef (0)
   result   <- newIORef (0)

   let incr    = modifyIORef counter (\x -> x `seq` x+1)
       reset s = do c <- readIORef counter
                    r <- readIORef result
                    writeIORef result   $! (max c r)
                    writeIORef lastLine $! (Just s)
                    writeIORef counter  1

   forM (lines input) $ \line -> do
     ml <- readIORef lastLine
     case ml of
       (Just s) -> if s == line then incr else reset line
       Nothing  -> reset line

   r <- readIORef result
   putStrLn $ "Largest subsequence of equal lines: " ++ show r

Стало ещё быстрее и компактнее (png):

[dmatveev@localhost memq]$ time cat ulysses.txt | ./m1 +RTS -hd -i0.001
Largest subsequence of equal lines: 5

real    0m0.807s
user    0m0.794s
sys     0m0.015s

Вот эта синяя штука на графике, которая растёт - тоже лик?

Но проблема-то всё равно с m2.hs.

yoghurt ★★★★★ ()
Ответ на: комментарий от qnikst

Да. Сейчас еще раз поглядел, возможно кондуиты тут и не помогут. Мозг увидел слова «поток», «память» и среагировал кондуитами.

zinfandel ★★ ()
Ответ на: комментарий от qnikst

т.е. для начала сделать:

module Main where

import Control.Applicative
import Data.List

main = print =<<  (go <$> getContents)

go :: String -> Int
go = maximum . map length . group . lines

для того, чтобы смотрящие понимали, что ты знаешь, что тут есть правильное решение. Заметь, что память тут не течет и все итеративно.

Сейчас попробую состояние поверх накрутить.

qnikst ★★★★★ ()
Ответ на: комментарий от yoghurt

В типе данных строгие поля минимум:

State.Strict вычисляет State то WHNF т.е. ApplicationData <thunk> <thunk> <thunk>, таким образом никакого эффекта не дает.

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

stateFullComp state (i:nput) = do { smth >>= \s' -> statefullComp s nput}

с необходимым ветвлением и возвращением результата.

В данном случае кстати и Data.Foldable хватило бы.

qnikst ★★★★★ ()
Ответ на: комментарий от qnikst

[dmatveev@localhost memq]$ cat m3.hs
module Main where

import Control.Applicative
import Data.List

main = print =<<  (go <$> getContents)

go :: String -> Int
go = maximum . map length . group . lines
[dmatveev@localhost memq]$ ghc --make m3.hs -rtsopts -prof
[1 of 1] Compiling Main             ( m3.hs, m3.o )
Linking m3 ...
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m3 +RTS -hd -i0.001
5

real    0m4.476s
user    0m4.402s
sys     0m0.055s

Течёт: png

yoghurt ★★★★★ ()
Ответ на: комментарий от zinfandel

я вот паттерны, где scan-ы использовать надо никогда не вижу. Причем когда это во всяких задачках - то это пофиг, а вот когда при создании обработчика потока в netwire, например, это уже не приятно. Хоть заставить кого-нибудь придумать упражнения на это.

qnikst ★★★★★ ()
Ответ на: комментарий от yoghurt

ghc --make -m3.hs -O -rtsopts -prof, можно и -O2 но это дольше. Кстати вариант со трансформерами (при строгих полях) у меня тоже не течет.

qnikst ★★★★★ ()
Ответ на: комментарий от qnikst

Так вот оно что. Занятно. Пересобрал всё с -О, получил

[dmatveev@localhost memq]$ ghc --make m1.hs -O -rtsopts -prof
[1 of 1] Compiling Main             ( m1.hs, m1.o )
Linking m1 ...
[dmatveev@localhost memq]$ ghc --make m2.hs -O -rtsopts -prof
[1 of 1] Compiling Main             ( m2.hs, m2.o )
Linking m2 ...
[dmatveev@localhost memq]$ ghc --make m3.hs -O -rtsopts -prof
[1 of 1] Compiling Main             ( m3.hs, m3.o )
Linking m3 ...
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m1 +RTS -hd -i0.001
Largest subsequence of equal lines: 5

real    0m0.470s
user    0m0.462s
sys     0m0.011s
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m2 +RTS -hd -i0.001
Largest subsequence of equal lines: 5

real    0m0.471s
user    0m0.465s
sys     0m0.011s
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m3 +RTS -hd -i0.001
5

real    0m0.156s
user    0m0.157s
sys     0m0.005s

...и более-менее ровненькие графики использования памяти. Интересно, то, что по умолчанию оно работает так, а с -O - уже сяк - это баг, или фича? Где можно прочитать про эти оптимизации?

Большое спасибо!

yoghurt ★★★★★ ()
Ответ на: комментарий от qnikst

сюда-же забудь о `forM` из Control.Monad и используй Data.Traverable/Data.Foldable

А где можно почитать именно про принципиальную разницу в плане производительности?

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

читать про rewriting rules и конкретно тут list deforestation:

qnikst ★★★★★ ()
Ответ на: комментарий от yoghurt

в плане производительности нету (насколько я помню), есть в плане общности и правильности реализации

qnikst ★★★★★ ()

И ещё. Не совсем по теме, но всё-таки.

Вот так:

   cnt <- gets ctxCounter
   res <- gets ctxResult
   modify $ \s -> s { ctxLastLine = Just l
                    , ctxCounter  = 1
                    , ctxResult   = max res cnt
                    }
писать НЕ НАДО.

А надо так:

   modify $ \s -> s { ctxLastLine = Just l
                    , ctxCounter  = 1
                    , ctxResult   = max (ctxResult s) (ctxCounter s)
                    }
либо так
   cnt <- gets ctxCounter
   res <- gets ctxResult
   put $ \s -> s { ctxLastLine = Just l
                    , ctxCounter  = 1
                    , ctxResult   = max res cnt
                    }

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Спасибо. А чем вариант с put отличается от изначального с modify? Ну, если представить, что в структуре есть ещё другие поля.

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

Упс. Извини, насчёт put я наглючил, там должно было быть так:

   cnt <- gets ctxCounter
   res <- gets ctxResult
   put $ AppContext { ctxLastLine = Just l
                    , ctxCounter  = 1
                    , ctxResult   = max res cnt
                    }
Вообще, лучше пользуйся modify, только без лишних чтений. Короче и понятнее.

Miguel ★★★★★ ()

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

vertexua ★★★★★ ()
Последнее исправление: vertexua (всего исправлений: 2)
Ответ на: комментарий от vertexua

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

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

qnikst ★★★★★ ()
Последнее исправление: qnikst (всего исправлений: 1)
Ответ на: комментарий от qnikst

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

vertexua ★★★★★ ()
Ответ на: комментарий от vertexua

Утечка памяти этот ситуация когда память становится не доступной для освождения.

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

Тут есть много других тредов, где ты можешь пригодиться - просто уйди из этого.

qnikst ★★★★★ ()
Ответ на: комментарий от qnikst

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

qnikst ★★★★★ ()
Ответ на: комментарий от qnikst

или следует общепринятым нормам при написании кода.

Так это, где про нормы почитать-то? Я со своей базой из RWH про стрикт-поля вообще не знал (может, пропустил) и честно надеялся на State.Strict :(

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

Brian O'Sullivan в своём курсе читал, я домой вернусь попробую найти ссылку, и может от себя (хотя я никакой не авторитет) что дописать.

qnikst ★★★★★ ()
Ответ на: комментарий от yoghurt

А, не ошибся, это Йохан был.. http://johantibell.com/files/haskell-performance-patterns.html

vertexua знаком с Йоханом, кстати? А.. хотя он вроде в другом офисе работает.

qnikst ★★★★★ ()
Последнее исправление: qnikst (всего исправлений: 2)
Ответ на: комментарий от qnikst

естественно часть этих советов нужна, когда действительно нужно выжимать скорость. А так понимания нормальных форм, строгости/ленивости и правых и левых сверток и как они соотносятся должно быть достаточно.

qnikst ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.