Am Mittwoch 10 März 2010 23:01:28 schrieb Arnoldo Muller:

Hello Daniel:

Thanks! I employed mapM'_ but I am still getting the space leak. Any other hint?

Hmm, offhand, I don't see why that isn't strict enough. With some datafiles, I could try to investigate. One question, how does programme C with main = do [input, output, windowSize] <- getArgs let wSize = (read windowSize)::Int genomeExecute output wSize filterWindow input behave? Space leak or not? But yes, a few other hints I have (though they're not likely to squash the space leak). Generally, ByteString IO is often orders of magnitude faster than String IO and uses much less memory, so using (lazy) ByteStrings is worthy of consideration.

Arnoldo

-- define a window type Sequence = [Char] -- Window data data Window = Window { sequen :: Sequence,                        chrom :: Chromosome,                        pos   :: Int                      } -- print a window instance Show Window where     show w =  (sequen w) ++ "\t" ++ show (chrom w) ++ "\t" ++ show (pos w) -- Reading fasta files with haskell -- Initialize the main = do        -- get the arguments (intput is        [input, output, windowSize] <- getArgs        -- get directory contents (only names)        names <- getDirectoryContents input        -- prepend directory        let fullNames = filter isFastaFile $ map (\x -> input ++ "/" ++ x) names ********* let fullNames = map ((input ++) . ("/" ++)) $ filter isFastaFile names saves a little work *********        let wSize = (read windowSize)::Int        -- process the directories        mapM (genomeExecute output wSize filterWindow)  fullNames -- read the files one by one and write them to the output file genomeExecute :: String -> Int -> (Window -> Bool) -> String -> IO () genomeExecute  outputFile windowSize f inputFile = do   fileData <- readFile inputFile   appendFile outputFile $ fastaExtractor fileData windowSize f ********* The arguments of fastaExtractor should be reversed, then genomeExecute outputFile windowSize f inputFile = appendFile outputFile . fastaExtractor' f windowSize =<< readFile inputFile ********* -- isFastaFile :: String -> Bool isFastaFile fileName = isSuffixOf ".fa" fileName -- fasta extractor (receives a Fasta String and returns a windowed string ready to be sorted) -- an example on how to compose several functions to parse a fasta file fastaExtractor :: String -> Int -> (Window -> Bool) -> String fastaExtractor input wSize f = printWindowList $ filter f $ readFasta  wSize input ********* fastaExtractor' f wSize = printWindowList . filter f . readFasta wSize ********* -- MAIN FILTER that removes N elements from the strings! filterWindow :: Window -> Bool filterWindow w = not (elem 'N' (sequen w)) ********* filterWindow w = 'N' `notElem` sequen w ********* -- print a window list (the printing makes it ready for output as raw data) printWindowList :: [Window] -> String printWindowList l = unlines $ map show l -- read fasta, remove stuff that is not useful from it -- removes the readFasta :: Int -> [Char] -> [Window] readFasta windowSize sequence =     -- get the header     let (header:rest) = lines sequence         chr = parseChromosome header         in -- We now do the following: --      take window                  create counter remove newlines    map (\(i, w) -> Window w chr i) $ zip [0..]  $ slideWindow windowSize  $ filter ( '\n' /= )  $ unlines rest ********* filter ('\n' /=) . unlines is odd. What about concat? Or readFasta wSize chrseq = case span (/= '\n') chrseq of (header, _:rest) -> let chr = parseChromosome header in map (\(i,w) -> Window w chr i) . zip [0 .. ] . slideWindow wSize $ filter (/= '\n') rest _ -> [] if your input file format had no other newline than the one between header and body, that'd be nice. ********* slideWindow :: Int -> [Char] -> [[Char]] slideWindow _ [] = [] slideWindow windowSize l@(_:xs)  = take windowSize l : slideWindow windowSize xs ********* slideWindow wSize = map (take wSize) . tails *********

Daniel, Thank you so much for helping me out with this issue! Thanks to all the other answers from haskel-cafe members too! As a newbie, I am not able to understand why zip and map would make a problem... Is there any link I could read that could help me to understand why in this case zip and map created a leak? What are some function compositions that should be avoided when doing lazy I/O? Regards, Arnoldo On Thu, Mar 11, 2010 at 11:46 PM, Daniel Fischer wrote:

Am Donnerstag 11 März 2010 00:24:28 schrieb Daniel Fischer:

...

Hmm, offhand, I don't see why that isn't strict enough.

Turns out, mapM_ was a red herring. The villain was (zip and map). I must confess, I don't know why it sort-of worked without the mapM_, though. "sort-of", because that also hung on to unnecessarily much memory, the space leak was just smaller than with the mapM_.

A very small change that eliminates the space leak, is

readFasta :: Int -> [Char] -> [Window] readFasta windowSize sequence = -- get the header let (header,rest) = span (/= '\n') sequence chr = parseChromosome header go i (w:ws) = Window w chr i : go (i+1) ws go _ [] = [] in go 0 $ slideWindow windowSize $ filter (/= '\n') rest

You can improve performance by eliminating slideWindow and the intermediate Window list (merging fastaExtractor and readFasta),

{-# LANGUAGE BangPatterns #-}

readFasta2 :: (String -> Bool) -> Int -> String readFasta2 test windowSize sequence = let (header,rest) = span (/= '\n') sequence chr = parseChromosome header schr = show chr go !i st@(_:tl) | test w = w ++ '\t' : schr ++ '\t' : show i ++ '\n' : go (i+1) tl | otherwise = go (i+1) tl where w = take windowSize st go _ [] = [] in go 0 (filter (/= '\n')) rest

Jason, I am trying to use haskell in the analysis of bio data. One of the main reasons I wanted to use haskell is because lazy I/O allows you to see a large bio-sequence as if it was a string in memory. In order to achieve the same result in an imperative language I would have to write lots of error-prone iterators. I saw lazy I/O as a very strong point in favor of Haskell. Besides the space leaks that can occur and that are a bit difficult to find for a newbie like me, are there any other reasons to avoid Lazy I/O? Arnoldo. On Sat, Mar 13, 2010 at 6:46 PM, Jason Dagit wrote:

On Thu, Mar 11, 2010 at 3:44 PM, Arnoldo Muller wrote:

...

Daniel,

Thank you so much for helping me out with this issue!

Thanks to all the other answers from haskel-cafe members too!

As a newbie, I am not able to understand why zip and map would make a problem...

Is there any link I could read that could help me to understand why in this case zip and map created a leak? What are some function compositions that should be avoided when doing lazy I/O?

Actually, it's lazy I/O itself that should be avoided.

Jason

On Sat, Mar 13, 2010 at 8:58 PM, Arnoldo Muller wrote:

Jason,

I am trying to use haskell in the analysis of bio data. One of the main reasons I wanted to use haskell is because lazy I/O allows you to see a large bio-sequence as if it was a string in memory. In order to achieve the same result in an imperative language I would have to write lots of error-prone iterators. I saw lazy I/O as a very strong point in favor of Haskell.

What about mmap function? It's available on Linux, you can use it on C and probably a lot of other imperative languages. Was the non-portability factor the issue with using it?

Am Sonntag 14 März 2010 00:58:09 schrieb Arnoldo Muller:

Jason,

I am trying to use haskell in the analysis of bio data. One of the main reasons I wanted to use haskell is because lazy I/O allows you to see a large bio-sequence as if it was a string in memory. In order to achieve the same result in an imperative language I would have to write lots of error-prone iterators. I saw lazy I/O as a very strong point in favor of Haskell.

Besides the space leaks that can occur and that are a bit difficult to find for a newbie like me, are there any other reasons to avoid Lazy I/O?

You may be happy to hear that the space leak you encountered had __nothing whatsoever__ to do with lazy IO. It's true that lazy IO offers some pitfalls for the unwary (and some, but much fewer, for the wary), but I think the dangers of lazy IO tend to be exaggerated. For your application, readFile and appendFile are absolutely fine, the space leak occurred in the pure code. Below is a variant of your programme that doesn't use file-IO, the one readFasta function has the space leak, the currently commented-out one not. Compile with -O2, run with e.g. ./leak +RTS -s -M400M -RTS 3 10000000 10 one runs in constant space, the other not.

Arnoldo.

---------------------------------------------------------------------- {-# LANGUAGE BangPatterns #-} module Main (main) where import Data.List import System.Environment (getArgs) data Chromosome =    C1                 | C2                 | C3                 | C4                 | C5                 | C6                 | C7                 | C8                 | C9                 | C10                 | C11                 | C12                 | C13                 | C14                 | C15                 | C16                 | C17                 | C18                 | C19                 | CX                 | CY                 | CMT                   deriving (Show) type Sequence = [Char] data Window = Window { sequen :: Sequence,                        chrom :: Chromosome,                        pos   :: Int                      } instance Show Window where     show w =  (sequen w) ++ "\t" ++ show (chrom w) ++ "\t" ++ show (pos w) main = do        [ct, len, windowSize] <- getArgs        let wSize = (read windowSize)::Int ln = read len inData = [(cn,ln) | cn <- [1 .. read ct]]        mapM_ (uncurry $ genomeExecute filterWindow wSize) inData countLines :: String -> Int countLines = go 0 where go !acc [] = acc go !acc ('\n':cs) = go (acc+1) cs go !acc (_:cs ) = go acc cs genomeExecute :: (Window -> Bool) -> Int -> Int -> Int -> IO () genomeExecute flt wSize cn ln = print . countLines $ fastaExtractor ("chromosome " ++ show cn ++ ",\n" ++ replicate (cn*ln) 'A') wSize flt fastaExtractor :: String -> Int -> (Window -> Bool) -> String fastaExtractor input wSize f = printWindowList $ filter f $ readFasta  wSize input filterWindow :: Window -> Bool filterWindow w = not (elem 'N' (sequen w)) printWindowList :: [Window] -> String printWindowList l = unlines $ map show l {- readFasta :: Int -> [Char] -> [Window] readFasta windowSize sequence =     let (header,rest) = span (/= '\n') sequence         chr = parseChromosome header go i (w:ws) = Window w chr i : go (i+1) ws go _ [] = [] in go 0 $ slideWindow windowSize $ filter (/= '\n') rest -} readFasta :: Int -> [Char] -> [Window] readFasta windowSize sequence =     let (header,rest) = span (/= '\n') sequence         chr = parseChromosome header in map (\(i, w) -> Window w chr i) $ zip [0..]  $ slideWindow windowSize  $ filter ( '\n' /= ) rest slideWindow :: Int -> [Char] -> [[Char]] slideWindow _ [] = [] slideWindow windowSize l@(_:xs)  = take windowSize l : slideWindow windowSize xs parseChromosome :: [Char] -> Chromosome parseChromosome line     | isInfixOf "chromosome 1," line = C1     | isInfixOf "chromosome 2," line = C2     | isInfixOf "chromosome 3," line = C3     | isInfixOf "chromosome 4," line = C4     | isInfixOf "chromosome 5," line = C5     | isInfixOf "chromosome 6," line = C6     | isInfixOf "chromosome 7," line = C7     | isInfixOf "chromosome 8," line = C9     | isInfixOf "chromosome 10," line = C10     | isInfixOf "chromosome 11," line = C11     | isInfixOf "chromosome 12," line = C12     | isInfixOf "chromosome 13," line = C13     | isInfixOf "chromosome 14," line = C14     | isInfixOf "chromosome 15," line = C15     | isInfixOf "chromosome 16," line = C16     | isInfixOf "chromosome 17"  line = C17     | isInfixOf "chromosome 18"  line = C18     | isInfixOf "chromosome 19"  line = C19     | isInfixOf "chromosome X"   line = CX     | isInfixOf "chromosome Y"   line = CY     | isInfixOf "mitochondrion"  line = CMT     | otherwise = error "BAD header" ----------------------------------------------------------------------

Ketil Malde wrote:

Lazy IO always worked well for me, so althouhg I feel I should look more deeply into "real" solutions, like Iteratee, my half-hearted attemts to do so have only resulted in the conclusion that it was more complicated, and thus postponed for some rainy day... lazy IO for lazy programmers, I guess.

If you have a huge data set and a large address space (say, a 64-bit processor), you may want to use bytestring-mmap. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Bulat, The same happens, the memory starts to quickly fill up... Arnoldo On Wed, Mar 10, 2010 at 11:16 PM, Bulat Ziganshin

wrote:

Hello Arnoldo,

Wednesday, March 10, 2010, 11:45:56 PM, you wrote:

...

I am learning haskell and I found a space leak that I find difficult to solve. I've been asking at #haskell but we could not solve the issue.

what if you use program B on single file?

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com