[Haskell-beginners] Memory tuning

Thorsten Hater th at tp1.rub.de
Mon Oct 11 10:14:11 EDT 2010


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.





More information about the Beginners mailing list