search

haskell / pretty

Haskell Pretty-printer library
Other
69 stars 30 forks source link

Write a test and a fix for a stack overflow bug when trying to build very large documents. #9

Closed Peaker closed 9 years ago

Peaker commented 11 years ago

The foldr applications in vcat, hsep, and hcat use a function which is strict on its second argument.

This is a recipe for stack overflows which indeed happen when trying to build very large Doc values.

Added a test to reproduce the problem.

The fix is moving the canonization of Empty values into reduceAB, and doing it in a maximally-lazy fashion.

dterei commented 9 years ago

@Peaker closing, as I've re-created the PR with some small changes here: https://github.com/haskell/pretty/pull/16

dterei commented 9 years ago

Thanks for the PR though! Sorry I ignored it till now

thomie commented 9 years ago

After applying "Resolve foldr-strictness stack overflow bug" and "Special-case reduce for horiz/vert" to GHC's copy of pretty, the following test regresses.

In a GHC tree, run the command ./inplace/bin/ghc-stage2 nofib/spectral/simple/Main.hs -fforce-recomp -Rghc-timing with a devel2 build of HEAD (commit 85179b5821bb1010eede7cec43280c2cd7e59bd3 + https://phabricator.haskell.org/D1132).

    Before these two patches: 3677235496 bytes allocated
    After these two patches: 3778455656 bytes allocated
dterei commented 9 years ago

That may be fine, the patches do change laziness and the increase in allocation for that test is only ~ 3%.

thomie commented 9 years ago

Some more benchmark results from https://perf.haskell.org/ghc/#compare/ec68618bac918f365a7760062eb351cba3e4ddb3/cb828c0d43148dfdfa407a82310279ce98601233. These are compiler/perf tests, before and applying the patches by @Peaker to compiler/utils/Pretty.hs.

tests/alloc/T1969   575205848   + 11.01%    638535056   bytes
tests/alloc/T3064   241185432   + 3.73% 250182344   bytes
tests/alloc/T3294   2661675144  + 25.9% 3351169320  bytes
tests/alloc/T4801   395203440   + 15.36%    455919080   bytes
tests/alloc/T5321FD     427386568   + 6.08% 453358104   bytes
tests/alloc/T5321Fun    449961544   + 5.78% 475962416   bytes
tests/alloc/T5837   35517072    + 13.86%    40438320    bytes
tests/alloc/T783    468652880   + 11.75%    523717152   bytes
tests/alloc/T9961   680274680   + 3.16% 701745240   bytes

Based on these number, I'm reluctant to apply these changes. But it would be better to look at compiler cputime (who cares about memory usage). Unfortunately GHC doesn't have a reliable measurement framework for that yet.