Hello,
I've been playing with the INTEST problem on SPOJ which demonstrates
the ability to write a program which processes large quantities of
input data. http://www.spoj.pl/problems/INTEST/
I came across some curious behavior while cleaning up the program.
The original program, which runs fast (enough), is:
module Main(main) where
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as B
divisibleBy :: Int -> Int -> Bool
a `divisibleBy` n = a `rem` n == 0
main :: IO ()
main = do
[n,k] <- (map int . B.split ' ') `fmap` B.getLine :: IO [Int]
let
doLine :: Int -> Int -> IO Int
doLine r _ = B.getLine >>= testDiv r
testDiv r l
| int l `divisibleBy` k = return (r + 1)
| otherwise = return r
foldM doLine 0 [1..n] >>= print
where
int :: B.ByteString -> Int
int = fst . fromJust . B.readInt
But when I make a slight modification, the program chews up a ton more memory
and takes more time:
module Main(main) where
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as B
divisibleBy :: Int -> Int -> Bool
a `divisibleBy` n = a `rem` n == 0
main :: IO ()
main = do
[n,k] <- (map int . B.split ' ') `fmap` B.getLine :: IO [Int]
let
doLine :: Int -> Int -> IO Int
doLine r _ = B.getLine >>= return . testDiv r
-- 'return' moved here ^^
testDiv r l
| int l `divisibleBy` k = r + 1
| otherwise = r
foldM doLine 0 [1..n] >>= print
where
int :: B.ByteString -> Int
int = fst . fromJust . B.readInt
This program will generate sample data:
import System.Random
import System.Environment
import Control.Monad
main = do
[n] <- map read `fmap` getArgs :: IO [Int]
k <- randomRIO (1, 100)
putStrLn $ unwords [show n, show k]
replicateM_ n $ randomRIO (1, 10^9) >>= print
Note that the same behavior occurs even if I manually inline the local
function and try: return (if .. then .. else).
Some sample runs:
$ ghc/compiler/ghc-inplace
ghc-6.7.20070601: no input files
$ ghc/compiler/ghc-inplace --make -O2 intest.hs
[1 of 1] Compiling Main ( intest.hs, intest.o )
Linking intest ...
$ ghc/compiler/ghc-inplace --make -O2 intest_slow.hs
[1 of 1] Compiling Main ( intest_slow.hs, intest_slow.o )
Linking intest_slow ...
$ time ./intest +RTS -tstderr -RTS < test1
./intest +RTS -tstderr
8830
<