[Haskell-cafe] memory issues

[Daniel Fischer]

Am Freitag, 27. Februar 2009 23:18 schrieb Rogan Creswick:
>
> \begin{code}
> -- Compiled with:
> -- $ ghc --make offsetSorter.hs
> --
> --  (ghc v. 6.8.2)
> --
> -- Run with:
> -- $ time ./offsetSorter data/byteOffsets.txt > haskOffsets.txt
> -- offsetSorter: out of memory (requested 1048576 bytes)
> --
> -- real	4m12.130s
> -- user	3m4.812s
> -- sys	0m5.660s
> --(OOM happened after consuming just over 3000mb of Virt, 2.6gb Res,
> according to top.)
> --
>
> import System (getArgs)
> import Data.Maybe
> import Monad
> import Text.Printf (printf)
> import Data.Function (on)
> import Data.List (sort)
> import Data.ByteString (ByteString)
> import qualified Data.ByteString.Char8 as C8
> import qualified Data.ByteString as B
>
>
> -- get the lines
> -- parse each line to get the offset.
> -- scan the list of offsets
>
> -- | The full file size:
> maxSize :: Integer
> maxSize = 2807444044080
>
> -- | Block is a contiguous chunk of data.
> -- The first entry is the offset, the second is the length.
> data Block = Block {
>       offset::Integer
>     , size::Integer
>     } deriving (Eq)
>
> -- | Ordering of Blocks is based entirely on the block size.
> instance Ord Block where
>     compare = compare `on` size
>
> instance Show Block where
>     show (Block o s) = (show o) ++ "  " ++ (show s)
>
> -- turn the file into a list of offsets:
> getOffsets :: ByteString -> [Integer]
> getOffsets = catMaybes . map parseOffset . C8.lines
>
> -- | Pull out the offsets frome a line of the file.
> parseOffset :: ByteString -> Maybe Integer
> parseOffset s = do
>   (i, _) <- C8.readInteger (C8.filter (/=':') s)

Why the C8.filter (/= ':')?
That just costs and doesn't help anything (in fact, if your file contains 
lines like 1234:5678, it gives wrong results).

If you know that your file contains only lines of the form offset: <page>,
you can have

getOffsets = map (fst . fromJust . C8.readInteger) . C8.lines

which seems to do a little good.

>   Just i
>
> -- | Get the offsets between entries in a list
> getSizes :: [Integer]  -> [Integer]
> getSizes (x:y:[]) = [y - x]
> getSizes (x:y:ys) = (y - x):(getSizes (y:ys))
>
> -- | creates and returns a list of Blocks, given a file's content.
> blocks :: ByteString -> [Block]
> blocks s = zipWith (Block) offsets sizes
>            where offsets = getOffsets s
>                  sizes   = getSizes (offsets ++ [maxSize])
>
> main :: IO ()
> main = do
>   args <- getArgs
>   content <- B.readFile (args!!0)


>   printf "%s" $ unlines $ map (show) (sort $! blocks content)

Bad!
Use
	mapM_ print $ sort $ blocks content

> \end{code}