[Haskell-beginners] Stack space overflow with foldl'
Daniel Fischer
daniel.is.fischer at web.de
Sat Sep 11 18:54:55 EDT 2010
On Saturday 11 September 2010 23:30:50, Ryan Prichard wrote:
> > 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'm using Data.ByteString.ByteString:
>
> Prelude> :info Data.ByteString.ByteString
> data Data.ByteString.Internal.ByteString
> = Data.ByteString.Internal.PS !(GHC.ForeignPtr.ForeignPtr
> GHC.Word.Word8)
> !Int
> !Int
>
> If I evaluate a value of this type into WHNF, I think the fields are
> also evaluated into WHNF due to the strictness annotations. That
> should remove thunks from the Int arguments. I wonder if the
> ForeignPtr field could still have a thunk.
No, the pointer is just a memory address, no thunk there, a (strict)
ByteString in WHNF is fully evaluated.
The question is what you do with your ByteStrings in the fold.
>
> I suppose I really wanted an NFData instance for ByteString so I could
> use rnf.
In general, you don't need an NFData instance for ByteStrings, since WHNF =
NF for (strict) ByteStrings and reducing lazy ByteStrings to normal form
would sort of defeat their purpose. If you need an NFData instance because
you want to rnf e.g. a Map ByteString stuff, the default implementation of
rnf is enough.
>
> I looked at the NFData instance for a list. It's just:
>
> instance NFData a => NFData [a] where
> rnf [] = ()
> rnf (x:xs) = rnf x `seq` rnf xs
>
> If I just want to evaluate each list element to WHNF, I think I could
> write:
>
> forceList [] = ()
> forceList (x:xs) = x `seq` forceList xs
Yes.
>
> This function is simpler than foldl'2, and it turns into a
> tail-recursive function in Core. Maybe I could also use
> "forceList = foldr seq ()".
>
Exactly the same. But of course you need to evaluate forceList list to WHNF
to have it do any work,
case forceList list of
() -> foo
let !() = forceList list in bar
or something.
> > > I might have fixed my original stack overflow problem. I was
> > > applying sum to a large list of integers, and sum is lazy.
> >
> > For [Int] and [Integer], sum is specialised, so when compiled with
> > optimisations, ghc should use a strict version for those types.
>
> I retested my original program that used sum. It overflows the stack
> with -O0, but it doesn't overflow with -O or "-O -fno-strictness". With
> -v4 -ddump-simpl-stats -O, I see
>
> 1 RuleFired
> 1 SPEC Data.List.sum
>
> I don't see this output with -O0 instead of -O.
Specialisations are only used when compiled with optimisations since the
specialised versions have different names and are inserted via rewrite
rules. And rewrite rules are ignored with -O0.
So without optimisations, you get the vanilla sum with lazy accumulator.
To avoid stack overflows without optimisations, use foldl' (+) 0 instead of
sum.
>
> -Ryan
More information about the Beginners
mailing list