I tried adding strictness to everything, forcing each line with "evaluate . force"
It still runs out of memory and now running with -hc blames the extra memory on "trace elements" which seems somewhat unhelpful. On Sat, Dec 13, 2014 at 2:10 PM, David Spies <dnsp...@gmail.com> wrote: > > 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 <m...@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 <dnsp...@gmail.com> >> > To: "ghc-devs@haskell.org" <ghc-devs@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@haskell.org >> > http://www.haskell.org/mailman/listinfo/ghc-devs >> >
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs