[Haskell-beginners] Stack space overflow with foldl'

[Mathew de Detrich]

Shouldn't this be reported as a bug?

On 11/09/2010 12:22 AM, "Daniel Fischer" <daniel.is.fischer at web.de> wrote:

On Friday 10 September 2010 11:29:56, Ryan Prichard wrote:
> 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...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100910/feb44ff3/attachment-0001.html