Improve memory behaviour

[nh2]

In the GHC source code:

module Main where

import Language.Haskell.Exts.Annotated

main = print . length . show =<< parseFile "testsuite/tests/perf/compiler/parsing001.hs"

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

You have to compile with ghc, since ghci does not stack space overflow.

The example file can be obtained at https://raw.github.com/ghc/testsuite/master/tests/perf/compiler/parsing001.hs.

[nh2]

This is my output with stack traces on, using ghc --make Test.hs -rtsopts -prof -fprof-auto && ./Test +RTS -xc:

*** Exception (reporting due to +RTS -xc): (THUNK_1_0), stack trace: 
  Language.Haskell.Exts.Annotated.parseFileWithMode,
  called from Language.Haskell.Exts.Annotated.parseFile,
  called from Main.main,
  called from Main.CAF
  --> evaluated by: Language.Haskell.Exts.Annotated.ppContents,
  called from Language.Haskell.Exts.Annotated.parseFileContentsWithMode.md,
  called from Language.Haskell.Exts.Annotated.parseFileContentsWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileWithMode,
  called from Language.Haskell.Exts.Annotated.parseFile,
  called from Main.main,
  called from Main.CAF
*** Exception (reporting due to +RTS -xc): (THUNK_STATIC), stack trace: 
  Language.Haskell.Exts.Annotated.Fixity.leafFix.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.leafFix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.mapM,
  called from Language.Haskell.Exts.Annotated.Fixity.appFixDecls,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.InternalParser.applyFixities',
  called from Language.Haskell.Exts.ParseMonad.>>=,
  called from Language.Haskell.Exts.InternalParser.modeParse,
  called from Language.Haskell.Exts.InternalParser.parseModuleWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileContentsWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileWithMode,
  called from Language.Haskell.Exts.Annotated.parseFile,
  called from Main.main,
  called from Main.CAF
  --> evaluated by: Language.Haskell.Exts.ParseMonad.>>=,
  called from Language.Haskell.Exts.InternalParser.modeParse,
  called from Language.Haskell.Exts.InternalParser.parseModuleWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileContentsWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileWithMode,
  called from Language.Haskell.Exts.Annotated.parseFile,
  called from Main.main,
  called from Main.CAF
*** Exception (reporting due to +RTS -xc): (THUNK_STATIC), stack trace: 
  Language.Haskell.Exts.Annotated.Fixity.leafFix.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.leafFix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities.fix,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.Annotated.Fixity.mapM,
  called from Language.Haskell.Exts.Annotated.Fixity.appFixDecls,
  called from Language.Haskell.Exts.Annotated.Fixity.applyFixities,
  called from Language.Haskell.Exts.InternalParser.applyFixities',
  called from Language.Haskell.Exts.ParseMonad.>>=,
  called from Language.Haskell.Exts.InternalParser.modeParse,
  called from Language.Haskell.Exts.InternalParser.parseModuleWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileContentsWithMode,
  called from Language.Haskell.Exts.Annotated.parseFileWithMode,
  called from Language.Haskell.Exts.Annotated.parseFile,
  called from Main.main,
  called from Main.CAF
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

[nh2]

I think the error is in

    App l e1 e2               -> trace "App"             $ liftM2 (App l) (fix e1) (fix e2)

[nh2]

See also: http://www.haskell.org/pipermail/haskell-cafe/2013-August/108570.html

[nh2]

The mentioned commit fixes the problem as it occurs in the file I mentioned; haskell-src-exts can now parse all files in the ghc test suite (or at least there are none which make it stack overflow).

However, looking at the code, there are a lot of other cases where seqs are missing (see my commit for an example), which is why haskell-src-exts consumes excessive memory and will probably quickly stack overflow on other large Haskell files (I only dealt with the case for many Apps).

For example, if you just make the example file 10 times bigger, you will stack overflow again, in a different piece of code.

Please note that without http://ghc.haskell.org/trac/ghc/ticket/8189, code like

check2Exprs e1 e2 f = do
    e1 <- checkExpr e1
    e2 <- checkExpr e2
    return (f e1 e2)

can never work. It's frustrating, but there are only three choices:

• an infinite stack is implemented
• you avoid all standard monadic code like this and use ContT everywhere
• you manually implement some queue, which removes all benefits of do notation.

If you think this makes sense, please reply to my haskell-cafe thread :)

[niklasbroberg]

I will readily admit that space leaks and stack sizes are not my area of expertise. It appears the referenced GHC ticket has been fixed and merged, but I assume that's not really a fix per se, or?

Two things hold me back from snap-merging this patch:

1. The added dependencies on deepseq and mtl.
2. The added complexity of involving ContT.

I understand that sometimes it's necessary evil to introduce complexity for the sake of efficiency. However, if there are other options - such as fixing it "under the hood" - then I would very much prefer that.

Please enlighten me about our chances here.

[nh2]

The infiinite stack that is implemented for GHC 7.8 is actually fixing the core issue.

The seqs in certain places can still be very beneficial to reduce memory use substantially, but the before now unavoidable problem that haskell-src-exts would blow up on large files, even if you put them into all possible places, is gone (yay).

So I think it only remains to memory profile h-s-e a bit to see where seqs can do us good.

Concerning this specific pull request, we can drop the ContT and build-depens, and work with seq from the Prelude.

[niklasbroberg]

Great! So then this goes from a "bug" to an "enhancement" to improve memory behaviour. That's nowhere near as intrusive.