Program runs out of memory using GHC 7.6.3

[David Spies]

I think there's some confusion about makeCounts's behavior.  makeCount
never traverses the same thing twice.  Essentially, the worst-case size of
the unevaluated thunks doesn't exceed the total size of the array of lists
that was used to create them (and that array itself was created with
accumArray which is strict).
Nonetheless, I've tried adding strictness all over makeCounts and it
reduces the memory usage a little bit, but it still fails a later input
instance with OOM.  It's not a significant reduction like in GHC 7.8.3


On Sat, Dec 13, 2014 at 3:06 AM, Matthias Fischmann <mf at zerobuzz.net> wrote:
>
>
> Hi David,
>
> I don't think this is a ghc issue.
>
> I suspect you have too many unevaluated function calls lying around
> (this would cause the runtime to run out of *stack* as opposed to
> *heap*).  Different versions of ghc perform different optimizations on
> your code, and 7.8 knows a way to fix it that 7.6 doesn't know.
>
> This is usually solved by adding strictness: Instead of letting the
> unevaluated function calls pile up, you force them (e.g. with `print`
> or `Control.DeepSeq.deepseq`).
>
> I would take a closer look at your makeCounts function: you call
> traverse the input list, and traverse the entire list (starting from
> each element) again in each round.  Either you should find a way to
> iterate only once and accumulate all the data you need, or you should
> start optimizing there.
>
> hope this helps,
> cheers,
> matthias
>
>
> On Sat, Dec 13, 2014 at 02:06:52AM -0700, David Spies wrote:
> > Date: Sat, 13 Dec 2014 02:06:52 -0700
> > From: David Spies <dnspies at gmail.com>
> > To: "ghc-devs at haskell.org" <ghc-devs at haskell.org>
> > Subject: Program runs out of memory using GHC 7.6.3
> >
> > I have a program I submitted for a Kattis problem:
> > https://open.kattis.com/problems/digicomp2
> > But I got memory limit exceeded.  I downloaded the test data and ran the
> > program on my own computer without problems.  Eventually I found out that
> > when compiling with GHC 7.6.3 (the version Kattis uses) rather than
> 7.8.3,
> > this program runs out of memory.
> > Can someone explain why it only works on the later compiler?  Is there a
> > workaround so that I can submit to Kattis?
> >
> > Thanks,
> > David
>
> > module Main(main) where
> >
> > import           Control.Monad
> > import           Data.Array
> > import qualified Data.ByteString.Char8 as BS
> > import           Data.Int
> > import           Data.Maybe
> >
> > readAsInt :: BS.ByteString -> Int
> > readAsInt = fst . fromJust . BS.readInt
> >
> > readVert :: IO Vert
> > readVert = do
> >   [s, sl, sr] <- liftM BS.words BS.getLine
> >   return $ V (fromBS s) (readAsInt sl) (readAsInt sr)
> >
> > main::IO()
> > main = do
> >   [n, m64] <- liftM (map read . words) getLine :: IO [Int64]
> >   let m = fromIntegral m64 :: Int
> >   verts <- replicateM m readVert
> >   let vside = map getSide verts
> >   let vpar = concat $ zipWith makeAssoc [1..] verts
> >   let parArr = accumArray (flip (:)) [] (1, m) vpar
> >   let counts = makeCounts n m $ elems parArr
> >   let res = zipWith doFlips counts vside
> >   putStrLn $ map toChar res
> >
> > doFlips :: Int64 -> Side -> Side
> > doFlips n
> >   | odd n = flipSide
> >   | otherwise = id
> >
> > makeCounts :: Int64 -> Int -> [[(Int, Round)]] -> [Int64]
> > makeCounts n m l = tail $ elems res
> >   where
> >     res = listArray (0, m) $ 0 : n : map makeCount (tail l)
> >     makeCount :: [(Int, Round)] -> Int64
> >     makeCount = sum . map countFor
> >     countFor :: (Int, Round) -> Int64
> >     countFor (i, Up) = ((res ! i) + 1) `quot` 2
> >     countFor (i, Down) = (res ! i) `quot` 2
> >
> > fromBS :: BS.ByteString -> Side
> > fromBS = fromChar . BS.head
> >
> > fromChar :: Char -> Side
> > fromChar 'L' = L
> > fromChar 'R' = R
> > fromChar _ = error "Bad char"
> >
> > toChar :: Side -> Char
> > toChar L = 'L'
> > toChar R = 'R'
> >
> > makeAssoc :: Int -> Vert -> [(Int, (Int, Round))]
> > makeAssoc n (V L a b) = filtPos [(a, (n, Up)), (b, (n, Down))]
> > makeAssoc n (V R a b) = filtPos [(a, (n, Down)), (b, (n, Up))]
> >
> > filtPos :: [(Int, a)] -> [(Int, a)]
> > filtPos = filter ((> 0) . fst)
> >
> > data Vert = V !Side !Int !Int
> >
> > getSide :: Vert -> Side
> > getSide (V s _ _) = s
> >
> > data Side = L | R
> >
> > data Round = Up | Down
> >
> > flipSide :: Side -> Side
> > flipSide L = R
> > flipSide R = L
>
>
> > _______________________________________________
> > ghc-devs mailing list
> > ghc-devs at haskell.org
> > http://www.haskell.org/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20141213/86d150c6/attachment.html>