Hello, 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/fiifl): {-# 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 it doesn't (http://ideone.com/m744a): {-# OPTIONS_GHC -O2 -fno-cse #-} 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. 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? Thanks,
Hi Will,
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/fiifl):
{-# 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 it doesn't (http://ideone.com/m744a):
{-# OPTIONS_GHC -O2 -fno-cse #-} 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..])
This is entirely expected. What is gobbling up the memory is the shared [5,7..] list that some invocation of g consume while others hang onto the head of the same list. (Note that g is a constant.) If you change the code to make g pointful, and compile with -fno-full-laziness, then the memory usage will go down again. {-# OPTIONS_GHC -O2 -fno-full-laziness #-} primes :: [Int] primes = 2 : g (fix g) where g xs = (3:) . ([5,7..] `minus`) . foldi (\(x:xs) -> (x:) . union xs) . map (\x-> [x*x, x*x+2*x..]) $ xs With -ffull-laziness, ghc will notice that [5,7..] does not depend on xs, and float it out to the surrounding scope, essentially turning the code into {-# OPTIONS_GHC -O2 #-} primes :: [Int] primes = 2 : g (fix g) where g xs = (3:) . (odds `minus`) . foldi (\(x:xs) -> (x:) . union xs) . map (\x-> [x*x, x*x+2*x..]) $ xs odds = [5,7..] and the [5,7..] list will be shared once more. Using -fno-cse has no effect in this example, because there are no duplicate subexpressions in the code. It is still a good idea to try this option when one encounters odd space leaks. Bertram
Bertram Felgenhauer <bertram.felgenhauer <at> googlemail.com> writes:
Hi Will,
in reformulation of a code with no space leak, the leak reappeares.
This is entirely expected. What is gobbling up the memory is the shared [5,7..] list that some invocation of g consume while others hang onto the head of the same list. (Note that g is a constant.) If you change the code to make g pointful, and compile with -fno-full-laziness, then the memory usage will go down again.
{-# OPTIONS_GHC -O2 -fno-full-laziness #-} primes :: [Int] primes = 2 : g (fix g) where g xs = (3:) . ([5,7..] `minus`) . foldi (\(x:xs) -> (x:) . union xs) . map (\x-> [x*x, x*x+2*x..]) $ xs
With -ffull-laziness, ghc will notice that [5,7..] does not depend on xs, and float it out to the surrounding scope, essentially turning the code into
{-# OPTIONS_GHC -O2 #-} primes :: [Int] primes = 2 : g (fix g) where g xs = (3:) . (odds `minus`) . foldi (\(x:xs) -> (x:) . union xs) . map (\x-> [x*x, x*x+2*x..]) $ xs odds = [5,7..]
and the [5,7..] list will be shared once more.
Using -fno-cse has no effect in this example, because there are no duplicate subexpressions in the code. It is still a good idea to try this option when one encounters odd space leaks.
Bertram
Hi Bertram, thanks so much for your help! I could only get rid of the leak, with your advice, using the switch -fno-full-laziness, with pointful "g" code, and this (correction at the bottom!): ([5,7..] `minus`), or this (odds () `minus`), where odds () = [5,7..] (notice the (), without it there's a huge leak), or with this (gaps 5) where gaps k s@(x:xs) = if k<x then k:gaps (k+2) s else gaps (k+2) xs There was no way that I could find to achieve this without that switch. (correction at the bottom!!!) I would expect at least the (gaps 5) version to run with no leak, without that switch, but no. Strange, isn't it? Adding bang arguments didn't help. Sometimes adding the -fno-cse increased the leak hugely, at least 4 times more. The test entries are on ideone, which uses ghc-6.8.2: http://ideone.com/qpnqe -- g (fix g) http://ideone.com/wxmR5 -- twice-code The code itself is the result of discussions on haskell-cafe some time back, btw. CORRECTION: just with "gaps" (but not the other ones), changing the "g" function from composed pieces into a "normal" code, it did it! (probably some ghc version-specific stuff at play): g xs = 3 : gaps 5 ( foldi (\(x:xs) -> (x:) . union xs) [[x*x, x*x+2*x..] | x <- xs] ) This even runs ~ 9% faster than the twice-code version, at empirical complexity of O(n^1.21..1.22), in "n" primes produced, for first few million primes. :) It is practically the same as for the priority queue-based code, for which it is about O(n^1.20..1.21) empirically, BTW. Thanks!
Will Ness <will_n48 <at> yahoo.com> writes:
Bertram Felgenhauer <bertram.felgenhauer <at> googlemail.com> writes:
Hi Will,
in reformulation of a code with no space leak, the leak reappeares.
This is entirely expected. (.....)
{-# OPTIONS_GHC -O2 #-} primes :: [Int] primes = 2 : g (fix g) where g xs = (3:) . (odds `minus`) . foldi (\(x:xs) -> (x:) . union xs) . map (\x-> [x*x, x*x+2*x..]) $ xs odds = [5,7..]
CORRECTION: just with "gaps" (but not the other ones), changing the "g" function from composed pieces into a "normal" code, it did it! (probably some ghc version-specific stuff at play): g xs = 3 : gaps 5 ( foldi (\(x:xs) -> (x:) . union xs) [[x*x, x*x+2*x..] | x <- xs] ) addition: with gaps k xs = minus [k,k+2..] xs it also runs without the space leak, but with gaps k = minus [k,k+2..] the leak reappears. (?)
Hi Will, Will Ness wrote:
Will Ness <will_n48 <at> yahoo.com> writes:
CORRECTION: just with "gaps" (but not the other ones), changing the "g" function from composed pieces into a "normal" code, it did it! (probably some ghc version-specific stuff at play):
g xs = 3 : gaps 5 ( foldi (\(x:xs) -> (x:) . union xs) [[x*x, x*x+2*x..] | x <- xs] )
addition: with gaps k xs = minus [k,k+2..] xs it also runs without the space leak, but with gaps k = minus [k,k+2..] the leak reappears.
I'm not sure that I tried the same code as you did, but for me both these versions were leaky. I cannot explain why, but I see that in the resulting core (ghc ... -ddump-simpl) the [5,7..] list ends up as a top level constant, despite -fno-full-laziness. So the cause of the space leak remains the same -- the [5,7..] list is being shared among several invocations of g. Tricky. Bertram
Bertram Felgenhauer <bertram.felgenhauer <at> googlemail.com> writes:
Hi Will,
Will Ness wrote:
addition: with gaps k xs = minus [k,k+2..] xs it also runs without the space leak, but with gaps k = minus [k,k+2..] the leak reappears.
I'm not sure that I tried the same code as you did, but for me both these versions were leaky. I cannot explain why, but I see that in the resulting core (ghc ... -ddump-simpl) the [5,7..] list ends up as a top level constant, despite -fno-full-laziness. So the cause of the space leak remains the same -- the [5,7..] list is being shared among several invocations of g. Tricky.
Bertram
Hi, I've ended up with primes = 2 : g (fix g) where g xs = 3 : gaps 5 (unionAll [[x*x, x*x+2*x..] | x <- xs]) Here's the test entry: https://ideone.com/qpnqe The both "gaps" leak (25MB for 500k run) if "fix" is made internal function and there's no -fno-cse switch. But with the switch, one stops leaking, and the other goes to 120MB. Tricky, one could say, is an understatement. :) I wish (avoidable) space leaks could/would be considered a "bug" and compiler would find ways to avoid it, all by itself (or with a super-switch, "-fno- leaks" say). Then we'd needn't worry about such things, and could just write such "mythical one-liners" with confidence. :) Cheers, and thanks a lot, Will
participants (2)
-
Bertram Felgenhauer -
Will Ness