[Haskell-beginners] Memory leak after going from type Integer to Int
andlem at arcor.de
Thu Oct 11 19:33:23 CEST 2012
I wrote a simple program that returns the n-th prime number when given n as
its command-line argument:
isPrime n | n < 2 = False
| n == 2 = True
| otherwise = not $ any (`divides` n) dividerList
where a `divides` b = b `mod` a == 0
dividerList = 2:[3, 5 .. floor $ sqrt $ fromIntegral n]
primes = filter isPrime [1 ..]
main = do
[arg] <- getArgs
print $ primes !! (read arg)
I compiled it with "ghc -O2". As expected, it runs in constant space, i. e.
space complexity O(1). Then, I added the declaration: "primes :: [Int]",
expecting a performance improvement. Runtime was indeed reduced by about
50%. However, it no longer runs in constant space. Memory usage rises
significantly for arguments > 1e5.
I tried all sorts of strictness annotations, which did not help. Turning on
profiling with "ghc -O2 -prof -auto-all" made the problem disappear, so I
could not analyze the memory leak using the profiler. Only if I remove the
cases "n < 2" and "n == 2" from the definition of isPrime, does the program
run in constant space with type Int. If I replace the guards by an if
statement or pattern matching, the problem remains.
I have no idea how to continue from here. Can anyone explain why going from
type Integer to Int causes a different space complexity? How would I have to
change the program to get it to run in constant space with type Int?
I used ghc 7.4.1.
More information about the Beginners