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