Hello everyone,
I'm trying to reduce the memory footprint (and possibly execution time,
too) of a small program
I wrote. It's from the project Euler context, produces the correct
result, but it is unsatifiing as
indicated by a profiling run:
2,633,675,888 bytes allocated in the heap
1,221,377,976 bytes copied during GC
27,240,696 bytes maximum residency (22 sample(s))
1,576,200 bytes maximum slop
80 MB total memory in use (1 MB lost due to fragmentation)
Generation 0: 5002 collections, 0 parallel, 1.38s, 1.36s elapsed
Generation 1: 22 collections, 0 parallel, 0.62s, 0.64s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.76s ( 1.80s elapsed)
GC time 1.99s ( 2.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.76s ( 3.81s elapsed)
%GC time 53.1% (52.6% elapsed)
Alloc rate 1,494,074,809 bytes per MUT second
Productivity 46.9% of total user, 46.3% of total elapsed
Not only is the actual memory consumption quite high, but the
GC/computation ratio is almost 1:1.
I assume that there is something to be done regarding strictness, but a
series of experiments with
BangPatterns return no yields at all (using foldr instead of foldl'
produces stack overflow)
Here is my program:
-- project euler p75.hs
import qualified Data.Map as Map
import Data.List -- strict foldl
circum :: Int -> Int -> Int
circum a b = 2*a*(a+b)
count :: Int -> (Map.Map Int Int) -> Int -> (Map.Map Int Int)
count lmt mp c = foldl' step mp $ takeWhile (<=lmt) [k*c | k <- [1..] ]
where step m x = Map.insertWith' (+) x 1 m
solve :: Int -> Int
solve l = Map.size $ Map.filter (== 1) primitive
where lmt = floor $ sqrt $ (fromIntegral l)/2
cand = [c | m <- [2..lmt],
n <- [1..m],
odd (m+n),
1 == gcd m n,
let c = circum m n,
l >= c]
primitive = foldl' (count l) (Map.empty) cand
main = do print $ solve 1500000
Any advice and or tips welcome, as I'm quite new to Haskell.
Best regards.
