Re: Program runs out of memory using GHC 7.6.3

[David Spies]

Oh,
Now I feel really silly for not noticing that that number was 8 MB.  I saw
the 8 at the beginning all this time and just assumed it meant 8 GB.

I'm sorry,
In the future I'll post queries like this on the GHC-users mailing list.
I'm guessing Kattis doesn't bother to change the default stack size when
they run the program.  I'll email to let them know.

Thank you,
David


On Sun, Dec 14, 2014 at 4:03 AM, Matthias Fischmann m...@zerobuzz.net wrote:


 sorry, you're right, my mistake.  makeCounts has no obvious complexity
 issues.

 my next guess: the default stack size (+RTS -Kn) for 7.6.3 is 8M,
 the default for 7.8.3 is 80% of physical memory (see 7.8.1 release
 notes).  i think this is the reason why the 7.8.3 executable does not
 run out of stack, whlie the 7.6.3 one does.

 anyway, if you want to continue this discussion on ghc-dev, you should
 probably provide some evidence that it is a bug.  performance
 improvements between releases are intentional.  (-:

 thanks for the kattis link, btw!

 cheers,
 m.


 On Sat, Dec 13, 2014 at 02:10:25PM -0700, David Spies wrote:
  Date: Sat, 13 Dec 2014 14:10:25 -0700
  From: David Spies dnsp...@gmail.com
  To: Matthias Fischmann m...@zerobuzz.net
  Cc: ghc-devs@haskell.org ghc-devs@haskell.org
  Subject: Re: Program runs out of memory using GHC 7.6.3
 
  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

Re: Program runs out of memory using GHC 7.6.3

[David Spies]

I tried all optimization levels of 7.6.3 and it runs out of memory
I tried all optimization levels of 7.8.3 and it doesn't

So it must be something the compiler does even without any optimization.

On Sat, Dec 13, 2014 at 3:05 AM, Mikolaj Konarski miko...@well-typed.com
wrote:

 tt may be that GHC 7.8 optimizes the program better.
 Compile with -O0 and see if it runs out of memory, too.
 If so, you can just optimize the program by hand.
 I'd suggest making a heap profilie with -O0 or in GHC 7.6
 and finding out where the memory goes.

 Of course, it's possible you've hit a compiler bug,
 but it makes sense not to start with that assumption.

 Have fun,
 Mikolaj

 On Sat, Dec 13, 2014 at 10:06 AM, David Spies dnsp...@gmail.com wrote:
  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
 
 
  ___
  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

___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs

Re: 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 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

Re: Program runs out of memory using GHC 7.6.3

[David Spies]

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

Re: -O/-O2 causes program to run too slow

[David Spies]

Yes, it got faster when compiled with -fno-state-hack.  It also got faster
when I added a second (useless) reference to cf (changing the definition of
doProbs to cf `seq` replicateM_ m doProb)

Also, when profiling, the number of entries into findChain decreased
significantly after adding -fno-state-hack


On Wed, Dec 10, 2014 at 10:49 AM, Simon Peyton Jones simo...@microsoft.com
wrote:

  Just to check, when you say that “I found it was an instance of…” do you
 mean “I compiled with –fno-state-hack as the only change, and it got faster
 again”?   Otherwise how would you know this was the cause?



 Simon



 *From:* ghc-devs [mailto:ghc-devs-boun...@haskell.org] *On Behalf Of *David
 Spies
 *Sent:* 07 December 2014 19:44
 *To:* ghc-devs@haskell.org
 *Subject:* Re: -O/-O2 causes program to run too slow



 Ok, so I found that it was an instance of this:
 https://ghc.haskell.org/trac/ghc/ticket/1168

 and I read through this whole thread:
 https://www.haskell.org/pipermail/glasgow-haskell-users/2008-February/014259.html

 I don't understand the state-hack optimization.  It's clearly not safe and
 I'm not convinced that it actually is an optimization.  In what
 circumstances does the state-hack identify a single-entry function that
 can't be identified as single-entry by some other (safe) method?





 On Sun, Dec 7, 2014 at 10:52 AM, David Spies dnsp...@gmail.com wrote:

   I have a program I wrote to submit for the Car Game problem on Kattis:
 https://open.kattis.com/problems/cargame

 but it runs over the 5-second time-limit



 I downloaded the test data and found that on GHC 7.8.3, if I switch from
 -O2 to -O0, it runs three times faster (almost certainly fast enough for
 Kattis to accept).  Can someone tell me what's going on?  Is this a bug?



___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs

Re: -O/-O2 causes program to run too slow

[David Spies]

Ok, so I found that it was an instance of this:
https://ghc.haskell.org/trac/ghc/ticket/1168
and I read through this whole thread:
https://www.haskell.org/pipermail/glasgow-haskell-users/2008-February/014259.html

I don't understand the state-hack optimization.  It's clearly not safe and
I'm not convinced that it actually is an optimization.  In what
circumstances does the state-hack identify a single-entry function that
can't be identified as single-entry by some other (safe) method?


On Sun, Dec 7, 2014 at 10:52 AM, David Spies dnsp...@gmail.com wrote:

 I have a program I wrote to submit for the Car Game problem on Kattis:
 https://open.kattis.com/problems/cargame
 but it runs over the 5-second time-limit

 I downloaded the test data and found that on GHC 7.8.3, if I switch from
 -O2 to -O0, it runs three times faster (almost certainly fast enough for
 Kattis to accept).  Can someone tell me what's going on?  Is this a bug?


___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs