haskell - スタックスペースのオーバーフロー (mapM に関連している可能性があります)

Question

ディレクトリ内の各画像ファイルに対して 1 つのコマンドを含むシェルスクリプトを作成するプログラムを作成しています。ディレクトリには 667,944 個の画像があるため、厳密性と遅延性の問題を適切に処理する必要があります。

これが私に与える簡単な例ですStack space overflow。を使用してより多くのスペースを与えると機能しますが、ほとんどのメモリで実行でき+RTS -Ksize -RTS、すぐに出力を生成できるはずです。だから、私は Haskell wiki と Haskell の wikibook で厳密性に関するものを読んで、問題を解決する方法を見つけようとしました。それは私を悲しませている mapM コマンドの 1 つであると思いますが、まだ解決していません。問題を分類するための厳密さについて十分に理解していません。

関連すると思われる SO に関するその他の質問をいくつか見つけました ( Is mapM in Haskell strict? Why does this program get a stack overload? and Is Haskell's mapM not lazy? )、しかし啓発はまだ私を逃れています。

import System.Environment (getArgs)
import System.Directory (getDirectoryContents)

genCommand :: FilePath -> FilePath -> FilePath -> IO String
genCommand indir outdir file = do
  let infile = indir ++ '/':file
  let angle = 0 -- have to actually read the file to calculate this for real
  let outfile = outdir ++ '/':file
  return $! "convert " ++ infile ++ " -rotate " ++ show angle ++ 
    " -crop 143x143+140+140 " ++ outfile

main :: IO ()
main = do
  putStrLn "#!/bin/sh"
  (indir:outdir:_) <- getArgs
  files <- getDirectoryContents indir
  let imageFiles = filter (`notElem` [".", ".."]) files
  commands <- mapM (genCommand indir outdir) imageFiles
  mapM_ putStrLn commands

編集:テスト #1

これがサンプルの最新バージョンです。

import System.Environment (getArgs)
import System.Directory (getDirectoryContents)
import Control.Monad ((>=>))

genCommand :: FilePath -> FilePath -> FilePath -> IO String
genCommand indir outdir file = do
  let infile = indir ++ '/':file
  let angle = 0 -- have to actually read the file to calculate this for real
  let outfile = outdir ++ '/':file
  return $! "convert " ++ infile ++ " -rotate " ++ show angle ++ 
    " -crop 143x143+140+140 " ++ outfile

main :: IO ()
main = do
  putStrLn "TEST 1"
  (indir:outdir:_) <- getArgs
  files <- getDirectoryContents indir
  putStrLn $ show (length files)
  let imageFiles = filter (`notElem` [".", ".."]) files
  -- mapM_ (genCommand indir outdir >=> putStrLn) imageFiles
  mapM_ (\filename -> genCommand indir outdir filename >>= putStrLn) imageFiles

コマンドでコンパイルしますghc --make -O2 amy2.hs -rtsopts。コマンド./amy2 ~/nosync/GalaxyZoo/table2/images/ wombatで実行すると、次のようになります

TEST 1
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

代わりにコマンド./amy2 ~/nosync/GalaxyZoo/table2/images/ wombat +RTS -K20Mで実行すると、正しい出力が得られます...最終的には：

TEST 1
667946
convert /home/amy/nosync/GalaxyZoo/table2/images//587736546846572812.jpeg -rotate 0 -crop 143x143+140+140 wombat/587736546846572812.jpeg
convert /home/amy/nosync/GalaxyZoo/table2/images//587736542558617814.jpeg -rotate 0 -crop 143x143+140+140 wombat/587736542558617814.jpeg

...等々。

score 6 · Accepted Answer

これは厳密性の問題(*)ではなく、評価の順序の問題です。遅延評価された純粋な値とは異なり、モナド効果は決定論的な順序で発生する必要があります。mapM指定されたリスト内のすべてのアクションを実行し、結果を収集しますが、アクションのリスト全体が実行されるまで戻ることができないため、純粋なリスト関数と同じストリーミング動作は得られません。

この場合の簡単な修正は、との両方genCommandをputStrLn同じ内で実行することmapM_です。mapM_中間リストを構築していないため、同じ問題に悩まされないことに注意してください。

mapM_ (genCommand indir outdir >=> putStrLn) imageFiles

上記は、モナド関数を除いて関数合成演算子に似た「kleisli合成演算子」>=>を使用しています。通常のバインドとラムダを使用することもできます。Control.Monad.

mapM_ (\filename -> genCommand indir outdir filename >>= putStrLn) imageFiles

小さいモナドストリームプロセッサ間でより優れたコンポーザビリティが必要な、より複雑な I/O アプリケーションの場合は、conduitやなどのライブラリを使用する必要がありますpipes。

-Oまた、またはのいずれかでコンパイルしていることを確認してください-O2。

(*) 正確には、厳密性の問題でもあります。メモリ内に大きな中間リストを構築することに加えて、怠惰はmapM不要なサンクを構築し、スタックを使い果たすためです。

編集：だから、主な犯人はそうかもしれませんgetDirectoryContents。関数のソースコードを見ると、本質的にはと同じ種類のリストの蓄積を内部的に行っていmapMます。

ストリーミングディレクトリリストを実行するにはSystem.Posix.Directory、残念ながらプログラムを非 POSIX システム (Windows など) と互換性を持たせるために使用する必要があります。たとえば、継続渡しスタイルを使用して、ディレクトリの内容をストリーミングできます

import System.Environment (getArgs)
import Control.Monad ((>=>))

import System.Posix.Directory (openDirStream, readDirStream, closeDirStream)
import Control.Exception (bracket)

genCommand :: FilePath -> FilePath -> FilePath -> IO String
genCommand indir outdir file = do
  let infile = indir ++ '/':file
  let angle = 0 -- have to actually read the file to calculate this for real
  let outfile = outdir ++ '/':file
  return $! "convert " ++ infile ++ " -rotate " ++ show angle ++
    " -crop 143x143+140+140 " ++ outfile

streamingDirContents :: FilePath -> (FilePath -> IO ()) -> IO ()
streamingDirContents root cont = do
    let loop stream = do
            fp <- readDirStream stream
            case fp of
                [] -> return ()
                _   | fp `notElem` [".", ".."] -> cont fp >> loop stream
                    | otherwise -> loop stream
    bracket (openDirStream root) loop closeDirStream


main :: IO ()
main = do
  putStrLn "TEST 1"
  (indir:outdir:_) <- getArgs
  streamingDirContents indir (genCommand indir outdir >=> putStrLn)

を使用して同じことを行う方法は次のconduitとおりです。

import System.Environment (getArgs)

import System.Posix.Directory (openDirStream, readDirStream, closeDirStream)

import Data.Conduit
import qualified  Data.Conduit.List as L
import Control.Monad.IO.Class (liftIO, MonadIO)

genCommand :: FilePath -> FilePath -> FilePath -> IO String
genCommand indir outdir file = do
  let infile = indir ++ '/':file
  let angle = 0 -- have to actually read the file to calculate this for real
  let outfile = outdir ++ '/':file
  return $! "convert " ++ infile ++ " -rotate " ++ show angle ++
    " -crop 143x143+140+140 " ++ outfile

dirSource :: (MonadResource m, MonadIO m) => FilePath -> Source m FilePath
dirSource root = do
    bracketP (openDirStream root) closeDirStream $ \stream -> do
        let loop = do
                fp <- liftIO $ readDirStream stream
                case fp of
                    [] -> return ()
                    _  -> yield fp >> loop
        loop

main :: IO ()
main = do
    putStrLn "TEST 1"
    (indir:outdir:_) <- getArgs
    let files    = dirSource indir $= L.filter (`notElem` [".", ".."])
        commands = files $= L.mapM (liftIO . genCommand indir outdir)

    runResourceT $ commands $$ L.mapM_ (liftIO . putStrLn)

の良いところは、やconduitのコンジットバージョンなどで機能の一部を構成する能力を取り戻すことです。オペレーターは、チェーン内を前方にストリーミングし、ストリームをコンシューマーに接続します。filtermapM$=$$

現実の世界は複雑で、効率的で堅牢なコードを作成するには、リソース管理でいくつかの困難を乗り越える必要があります。そのため、すべての操作はResourceTモナドトランスフォーマーで機能します。モナドトランスフォーマーは、たとえば開いているファイルハンドルを追跡し、それらが不要になったとき、または例外によって計算が中止された場合 (これは、lazy I を使用するのとは対照的です) /O を使用し、ガベージコレクターに依存して最終的に不足しているリソースを解放します)。

ただし、これは、 a )最終的な結果のコンジット操作をで実行する必要があること、runResourceTおよびb)liftIO eg を直接書き込む代わりに、を使用して変換されたモナドに I/O 操作を明示的に持ち上げる必要があることを意味しL.mapM_ putStrLnます。

haskell - スタック スペースのオーバーフロー (mapM に関連している可能性があります)

1 に答える 1

Related

Reference

haskell - スタックスペースのオーバーフロー (mapM に関連している可能性があります)