Shouldn't this be reported as a bug?
On 11/09/2010 12:22 AM, "Daniel Fischer"
Hi,
I see a stack overflow with thi... Neither do I, really, but ghc is being too clever for its own good - or not clever enough.
I looked at the Core output with ghc-core, with or without optimizations, and I see a $wlgo r...
Without optimisations, I see a nice tail-recursive lgo inside foldl'2, pretty much what one would like to see. With optimisations, you get a specialised worker $wlgo: Rec { Main.$wlgo :: [GHC.Types.Int] -> (##) GblId [Arity 1 NoCafRefs Str: DmdType S] Main.$wlgo = \ (w_sms :: [GHC.Types.Int]) -> case case w_sms of _ { [] -> GHC.Unit.(); : x_adq xs_adr -> case x_adq of _ { GHC.Types.I# _ -> case Main.$wlgo xs_adr of _ { (# #) -> GHC.Unit.() } } } of _ { () -> GHC.Prim.(##) } end Rec } and it's here that ghc shows the wrong amount of cleverness. What have we? At the types () and [Int], with f = flip seq, the step in lgo unfolds to lgo z (x:xs) ~> let z' = f z x in lgo z' xs ~> case f z x of z'@() -> lgo z' xs ~> case (case x of { I# _ -> z }) of z'@() -> lgo z' xs Now flip seq returns its first argument unless its second argument is _|_ and () has only one non-bottom value, so the ()-argument of lgo can be eliminated (here, the initial ()-argument is known to be (), in general the wrapper checks for _|_ before entering the worker), giving wlgo :: [Int] -> () wlgo [] = () wlgo (x:xs) = case (case x of { I# _ -> () }) of () -> wlgo xs It would be nice if the compiler rewrote the last equation to wlgo (x:xs) -> case x of { I# _ -> wlgo xs } , but apparently it can't. Still, that's pretty good code. Now comes the misplaced cleverness. Working with unboxed types is better (faster) than working with boxed types, so let's use unboxed types, giving $wlgo the type [Int] -> (##) (unboxed 0-tuple). But it wasn't clever enough to directly return (# #) in the case of an empty list - that would've allowed the core to be \ (w_sms :: [GHC.Types.Int]) -> case w_sms of _ { [] -> GHC.Prim.(##) : x_adq xs_adr -> case x_adq of _ { GHC.Types.I# _ -> Main.$wlgo xs_adr } } and all would've been fine and dandy. So it chose [] -> GHC.Unit.() and that forced the second branch to also have that type, hence you can't have a tail call there but have to box the result of the recursive call (only to unbox it again). So you get superfluous boxing, unboxing, reboxing in addition to a stack- eating recursion. But you've hit a rare case here, if you use foldl'2 (flip seq) at a type with more than one non-bottom value, the first argument of lgo is not eliminated and you don't get the boxing-unboxing dance, instead you get a nice tail-recursion, even if foldl'2 is used only once and not exported. Why GHC does that for (), beats me.
I don't see any let expressions in the folding code, so I assume no thunks are being created. ... Perhaps http://www.haskell.org/pipermail/beginners/2010-August/005016.html
?
2. Instead of using the __GLASGOW_HASKELL__ version of foldl', use the other version:
f...
But that needs to pass also the function, which is generally slower than having it as a static argument. 3. {-# NOINLINE foldl'2 #-} But that's not so good for performance in general. Option 1 gives the best Core, but it changes behaviour, with that, foldl' (\_ _ -> 1) undefined [0] = 1 foldl'2 (\_ _ -> 1) undefined [0] = _|_ To retain the behaviour of foldl', foldl'2 f z0 xs0 = case xs0 of [] -> z0 (x:xs) -> lgo (f z0 x) xs where lgo !z [] = z lgo z (y:ys) = lgo (f z y) ys
My test case is contrived. Originally, I had a program that read lines from a file as Data.B...
That's probably a different matter, foldl' evaluates the accumulation parameter only to weak head normal form, if it's not of simple type, it can still contain thunks that will overflow the stack when demanded.
I might have fixed my original stack overflow problem. I was applying sum to a large list of...
For [Int] and [Integer], sum is specialised, so when compiled with optimisations, ghc should use a strict version for those types.
I don't think I have any real code anymore that overflows the stack, but I'm uncomfortable be... I don't think the language definition treats that, so technically it's allowed then. But it shouldn't happen.
Thanks, -Ryan
_______________________________________________ Beginners mailing list Beginne...