#12425: With -O1 and above causes ghc to use all available memory before being killed by OOM killer -------------------------------------+------------------------------------- Reporter: erikd | Owner: Type: bug | Status: new Priority: high | Milestone: 8.0.3 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Thomie, THANK YOU for the small repro case in comment:3. With its help I rapidly nailed the bug. Here's what is happening. Suppose we have {{{ let rec { f = ...g...g... ; g = ...f...f... } in case x of True -> ...f.. False -> ..f... }}} In each iteration of the simplifier the occurrence analyser `OccAnal` chooses a loop breaker. Suppose in iteration 1 it choose `g` as the loop breaker. That means it is free to inline `f`. Suppose that GHC decides to inline `f` in the branches of the `case`, but (for some reason; eg it is not satureated) in the rhs of `g`. So we get {{{ let rec { f = ...g...g... ; g = ...f...f... } in case x of True -> ...g...g..... False -> ..g..g.... }}} Now suppose that, for some reason, in the next iteraion the occurrence analyser chooses `f` as the loop breaker, so it can freely inling `g`. And again for some reason the simplifer inlines `g` at its calls in the `case` branches, but not in the RHS of `f`. Then we get {{{ let rec { f = ...g...g... ; g = ...f...f... } in case x of True -> ...(...f...f...)...(...f..f..)..... False -> ..(...f...f...)...(..f..f...).... }}} You can see where this is going! Each iteration of the simplifier doubles the number of calls to `f` or `g`. No wonder GHC is slow! (In the particular example in comment:3, `f` and `g` are the two mutually recursive `fmap` instances for `CondT` and `Result`. They are both marked INLINE which, oddly, is why they don't inline in each other's RHS, because the call there is not saturated.) The root cause is that we flip-flop on our choice of loop breaker. I always thought it didn't matter, and indeed for any single iteration to terminate, it doesn't matter. But when we iterate, it matters a lot!! I think this was not happening before because, by a fluke, we tended to always choose the same one. But, perhaps as a resul of Bartosz's work on making GHC deterministic, the occurrence analyser now reliably flip-flops in each iteration, as above. Trac #12234 turns out to be ''exactly'' the same issue ------------------- What to do? We want the occurrence analyser to choose a loop breaker based on stable criteria, not arbitrary things. Simple idea: if two or more potential loop breakers look equally plausible, ''choose the one that was a loop breaker in the previous iteration''. That should make it stable. Stay tuned. But I thought I'd explain what is happening in case I get distracted. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12425#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler