#13080: Constant values are not floated out of the loop -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): Floating out `return ()` won't help much. Even if you do that, the program looks like {{{ worker = let l = poll () in forever l r = return () poll a = r >> poll a }}} so executing `l` will cause `l` to be evaluated as `r >> r >> r >> r >> ...` and we still have a live reference to `l` from within `forever`. If you instead define {{{ poll a = r >>= \_ -> poll a }}} and compile ''without optimization'' then `l` now looks like `r >>= (\_ -> ...)` and the space leak is gone. But turning on optimizations seems to cause GHC to rewrite the above to {{{ poll a = r >>= (let s = poll a in \_ -> s) }}} which now has the original problem again. (BTW I am always compiling with `-fno-state-hack`, since that just adds another layer of confusion to an already confusing situation.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Constant values are not floated out of the loop -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Constant values are not floated out of the loop -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Feuerbach): Reid: you're probably right and the `return ()` is a red herring. I guess I still don't completely understand how this works. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Constant values are not floated out of the loop -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): I missed something. It seems that `{-# NOINLINE #-}` here is effectively preventing `poll` from being specialized within its own RHS. While the constant argument ends up going away, the constant `Monad` dictionary does not. Writing {{{#!hs poll :: (Monad m) => x -> m a poll = go where go action = do return () go action }}} fixes the leak. So maybe something needs to be changed to allow internal specialization in the face of `NOINLINE`? Of course, that could have some other downside. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Feuerbach): I think I now understand what's going on here. (Basically, what Reid said.) I summarized my thoughts in this blog post: https://ro- che.info/articles/2017-01-10-nested-loop-space-leak I don't know what ghc can do here, but hopefully there is something. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): In the blog post you write

Let’s change (“eta-expand”) the poll code as if then had arity 4, without actually changing then or thenIO or their runtime arities:

and that this fixes the space leak. Isn’t this eta-expansion exactly what the state hack is about? So why does it not not work here? Ah, becuase `poll` is not at type `IO a` but rather for an arbitrary `Monad`… yeah, then it’s harder. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):

I thought that the state hack doesn't change the arity of functions, just marks them single-entry.

That’s how it works, but the ultimate goal of the state hack (the way I see it) is to eta-expand them. Usually this works by treating a `State#`-typed lambda as one-shot: {{{ foo = bar x >> baz y }}} will, after inlining `>>` (if that happens, but it usually does for IO) look like this: {{{ foo = let a = bar x b = baz y in \s0 -> case a s0 of (_,s1) -> b s1 }}} which is usually bad because of the allocations of `a` and `b`. (But I say “usually” because it is good if `bar x` is expensive and `foo` is used many times – these are the instances when people complain about the state hack removing this sharing). Now because `s0` is treated as one-shot, two optimizations are enabled, both of which have ultimately the same effect: * The inliner feels empowered to inline `a` and `b` into the lambda, because it is one shot. Then we obtain {{{ foo = \s0 -> case bar x s0 of (_,s1) -> baz y s1 }}} which we want. * The arity analysis uses the one-shot information on the lambda to determine that `foo` has arity 1 and eta-expands it: {{{ foo = \s -> (let a = bar x b = baz y in \s0 -> case a s0 of (_,s1) -> b s1) s }}} which then gets simplified to {{{ foo = \s -> case bar x s of (_,s1) -> baz y s1 }}} again. I once had an idea for a less intrusive state hack variant which would do this eta-expansion directly (but otherwise do not meddle with the one- shotness of `State#`-typed lambdas, which can be wrong), but did not follow through with it. See [ticket:9388#comment:6] for some background. But this is all `State#`-specific, while your bug is about abstractly monad code, where the compiler may now use knowledge about `IO`’s bind, right? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Feuerbach): Simon: as a matter of fact, I would expect all the calls to expensive to be recomputed. I think most programmers would interpret the above code as {{{ while (1) { for (n = 1; 1 <= 10000; n++) { print(expensive(n)); } } }}} If I wanted the calls to expensive to be shared, I would probably put them into a list. (Of course, a similar piece of code could be intended for `m = []`; but based on `print`, it looks like something intended for an `IO`-like monad.) I do understand the tradeoffs involved, and I'm not saying that this should be obvious to the compiler. I'm just saying that this might not be the most convincing example where the current behavior is the one a programmer would expect. What if a programmer could annotate variables (like `worker` or `poll`) as "function-like" vs "value-like"? "Function-like" means "I don't care about this value, feel free to recompute it" and "value-like" means "please cache it if possible". -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Feuerbach): David: If `foo` is marked as function-like by the programmer, `bar` and `baz` are recomputed on each invocation of `foo`. If `foo` is marked as value-like and is shared, `bar` and `baz` are shared, too. Furthermore, `bar` and `baz` could have their own annotations. Examples: {{{#!hs {-# FUNCTION_LIKE fib #-} fib = (fibs !!) where {- VALUE_LIKE fibs #-} fibs = 0 : 1 : zipWith (+) fibs (tail fibs) }}} {{{#!hs {-# VALUE_LIKE val #-} val = sum $ map f [1..10^6] where {-# FUNCTION_LIKE f #-} f = (+5) . (^2) }}} Now, what would FUNCTION_LIKE mean, exactly? In the `fib` example above, there can be two interpretations: 1. Don't bother "remembering" the PAP `(!!) fibs`, but do remember something like `fibs !! n`. 2. Don't even remember `fibs !! n`. The second interpretation is useful in cases like {{{#!hs mk_action :: Monad m => Int -> m () mk_action = flip replicateM_ (return ()) }}} where we may want to say, "don't bother to remember either the expansion or the result of mk_action". So, simple FUNCTION_LIKE can be ambiguous. What if we annotated functions with arities? Assigning an explicit arity to a function means that: 1. ghc attempts to perform eta reductions or expansions to match the declared arity; 2. ghc doesn't float things out of lambdas with declared arity >= 1. E.g. following Reid's example (https://ghc.haskell.org/trac/ghc/timeline?from=2017-01-07T14%3A42%3A24Z&precision=second), he could write {{{#!hs poll a = r >>= f where {-# ARITY 1 f #-} f _ -> poll a }}} and ghc would not transform `f` to `(let s = poll a in \_ -> s)`. And, of course, the original problem could be easily solved by annotating `poll` with the correct arity, as I point out in the blog post. It is also possible that these two things — forcing eta-expansion and not floating out local bindings — should be two different and orthogonal pragmass. What do you all think? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

So, it seems to me we need a new kind of Core lambda, or a flag on lambda, that means (a) don't float out of this, (b) don't beta reduce

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): this. We already have (a), namely one-shot lambdas. I don't understand why (b) could possibly be good. Perhaps someone can give a from-scratch articulation of the problem and possible solutions, informed by this thread? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by michalt): * cc: michalt (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13080: Memory leak caused by nested monadic loops -------------------------------------+------------------------------------- Reporter: Feuerbach | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by saurabhnanda): I ''think'' I have been hit by this bug. Is the following going to leak memory due to this bug: {{{ worker :: (AppMonad m) => TChan MyType -> m () worker chan = do mItem <- tryReadTChanIO chan case mItem of Just item -> do processItem item worker chan Nothing -> pure () }}} Can it be fixed by using {{{whileJust_}}} from http://hackage.haskell.org/package/monad-loops-0.4.3/docs/src/Control- Monad-Loops.html#whileJust_ ? {{{ worker :: (AppMonad m) => TChan MyType -> m () worker chan = whileJust_ (tryReadTChanIO chan) processItem }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13080#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler