[Haskell-cafe] Re: optimization help

[apfelmus at quantentunnel.de]

>  I have been trying to do some CSV-style processing. My code works
> fine for small input (up to 10MB), but performs poorly for moderate to
> large input (it can't seem to finish 100MB of input with 700MB heap
> space). I have gone through several optimization passes with profiler
> help, and now I am hoping someone else can point out some other
> approaches to improving the code's performance (both space and time).
> 
>  The code breaks a large file into smaller files all of whose entries
> have the same date.

First of all, for this problem and 100 MB input, you have to think
carefully about what you do. I'll point out three quirks in your code
and afterwards discuss how a better solution looks like.

> module Main where
> 
> import Debug.Trace
> import Control.Monad
> import Data.List
> import qualified Data.ByteString.Lazy.Char8 as B
> import qualified Data.Map as M
> import System.Environment (getArgs)
> 
> dataDir = "dataH/"
> 
> myRead file = do
> v <- B.readFile file
> let (cols' : rows) = map (B.split ',') $ B.lines v
> let cols = foldl' (\mp (k,v) -> M.insert k v mp) M.empty (zip cols' [0 ..])
> return (cols, rows)
> 
> getColId cols col = M.lookup col cols
>
> getCol cols col row = do
> i <- getColId cols col
> return $! row!!i
>
> 
> dates file nRows = do
>   (cols, rows) <- myRead file
>   let addDate mp row | mp `seq` row `seq` False = undefined
>                                | otherwise = do

When using addDate in foldM like below, you certainly don't want to
search the cols for the string "Date" again and again everytime addDate
is called. The index of the "Date" field is a number determined when
parsing the header. That and only that number has to be plugged in here.
Thus the next line should read
            let date = row !! datefieldindex
instead of
>           date <- getCol cols (B.pack "\"Date\"") row

>           let old = M.findWithDefault [] date mp
>           return $ M.insert date (row:old) mp

The main thing in the code that makes me feel very very ill is the fact
that the code is quite "impure" (many many dos). The next line promptly
bites back:

>   res <- foldM addDate M.empty $ take nRows rows

Did you notice this appeal to addDate makes its callee getCol live in
the IO-Monad? From the use of M.lookup in getColId, I think you intended
to have getCol :: _ -> Maybe _, do you? M.lookup recently got the more
general type
   M.lookup :: Monad m => _ -> m a,
so it happily lives in IO.
I strongly suggest that you restructure your code and restrict IO to one
place only:

   main = do
     ..
     input <- B.readFile file
     let outs = busywork input
     mapM_ [writeFile name contents | (name,contents) <- outs]

where busywork does the work and is purely functional.

>   mapM_ writeDate $ M.toList res
> where
>   fmt = B.unpack . B.map (\x -> if x == '-' then '_' else x) .
> B.takeWhile (/= ' ')
>   writeDate (date,rows) =
>       B.writeFile (dataDir++fmt date)

The following line does unnecessary work: myRead splits a row to get
access to the date, but now you join it without having changed any
field. It would be wiser to split for the date but to keep an intact
copy of the line so that you can pass it here without join. This will
reduce memory footprint.

>                   (B.unlines $ map (B.join (B.pack ",")) rows)

>
> main = do
>   args <- getArgs
>   case args of
>     ["dates",file,nRows] -> dates file (read nRows)


To summarize, the code is not very clean and several things slipped in,
just as one would expect from an imperative style. The key is to
separate concerns, which means here: IO will just do very dumb in and
output, fetching the index of the "Date" from the header is handled
separately, grouping the lines by date is to be separated from the
to-be-output-contents of the lines.



Now, we'll think about how to solve the task in reasonable time and space.

Your current solutions reads the input and "calculates" all output files
before writing them to disk in a final step. This means that the
contents of the output files has to be kept in memory. Thus you need
least a constant * 100MB of memory. I don't know how ByteString
interacts with garbage collection, but it may well be that by keeping
the first line (you "cols") in memory, the entire input file contents is
also kept which means an additional constant * 100 MB. It is likely that
both can be shared if one resolves the code quirks mentioned above.

A better solution would be to begin output before the the whole input is
read, thus making things more lazy. This can be done the following way:
from the input, construct a lazy list of (date,line) pairs. Then, let
foldM thread a map from dates to corresponding output file pointers
through the list and, at the same time, use the file pointers to output
the line in question via appendFile. This way, every line consumed is
immediately dispatched to its corresponding output file and things
should only require memory for the different dates, besides buffering.



In a setting without IO, the task corresponds to the "Optimization
Problem" discussed at length in September on this list. The problem here
is that writeFile currently cannot be interleaved lazily, this has to be
simulated with appendFile. We can read files lazily but we cannot output
them lazily.
Can this be remedied? Can there be a version of writeFile which is, in a
sense, dual to getContents?


Regards,
apfelmus