Problem with space leak in GHC compiled code using fix

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Problem with space leak in GHC compiled code using fix

Will Ness-2
Hi, could someone please help me understand this, thanks.

In reformulation of a code with no space leak, the leak reappeares.

It takes near constant space to get at the n-th elt in the produced list here
(http://ideone.com/wxmR5):

 {-# OPTIONS_GHC -O2 -fno-cse #-}
 primes = 2 : ([3,5..] `minus`
                foldi (\(x:xs) -> (x:) . union xs)
                      [[x*x, x*x+2*x..] | x<- ys])
  where
   ys = 3 : ([5,7..] `minus`
                foldi (\(x:xs) -> (x:) . union xs)
                      [[x*x, x*x+2*x..] | x<- ys])
   
 foldi f (x:xs)  = f x (foldi f (pairs f xs))
 pairs f (x:y:t) = f x y : pairs f t

Here the memory usage grows linearly at least (https://ideone.com/qpnqe):

 {-# OPTIONS_GHC -O2 #-}
 primes = 2 : g (fix g)
  where
   g = (3:) . ([5,7..] `minus`)
            . foldi (\(x:xs) -> (x:) . union xs)
            . map (\x-> [x*x, x*x+2*x..])

I expected the 2nd to be equivalent to the 1st. This also impacts its
performance: the 2nd code runs at empirical complexity of O(n^1.24) instead of
O(n^1.20) of the 1st one (in ''n'' primes produced).

In Hugs (Nov 2002) the reported stats and run times are very similar for the
both versions.

Is this a GHC thing, or a language thing? Can anything be done to have the
shorter 2nd variant without a space leak?

Thanks,