[GHC] #13080: Memory leak caused by nested monadic loops

[GHC]

#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 rwbarton):

 So there are three issues here:

 1. The programs under discussion leak space.

 2. The space leak is hard to see and unintuitive. (I didn't understand
 what was going on until I saw Roman's answer on SO.)

 3. You can't even eliminate the space leak in a reliable way.

 Fixing 1 directly seems infeasible without breaking other programs,
 because of examples like Simon's in comment:14. Plus, the space leak does
 exist if you evaluate the program naively using lazy evaluation, despite
 2. (And there are parallel examples that don't involve IO.) But we should
 be able to do something about 3, and it would be useful in many settings
 besides this one (such as benchmarking).

 I like the idea that if the user wants FUNCTION_LIKE behavior, then they
 should write a function. It aligns well with the basic rule for sharing
 (an expression inside a lambda is shared for the lifetime of that call to
 the lambda) and we already know how to implement it (just compile with
 `-O0`). We just have to not stuff it up during optimization. This is
 basically the full laziness problem yet again.

 The problem is of course that writing a function isn't sufficient because
 GHC will probably just float the body out. Besides that there's a second
 danger: we could inline and then beta-reduce. I don't want to write it
 out, but if you imagine inlining `>>=` and `f` in Roman's latest example,
 and then if you allow beta-reducing `f`, the lambda in `f` would disappear
 and then presumably nothing would stop GHC from floating `poll a` out of
 the lambda in `>>=`. It's hard to see how the inlining could be to blame
 here, so I blame the beta-reduction. (Then perhaps if we are never going
 to be allowed to beta-reduce, we can also not bother inlining. Not sure.)

 So, it seems to me we need a new kind of Core lambda, or a flag on lambda,
 that means

 * don't float out of this,

 * don't beta reduce this.

 How to give the user access to this is another question. I haven't thought
 about this `ARITY` suggestion much yet. Another possibility would be a
 magic pattern synonym `_#`, which matches anything but turns the lambda
 into a beta blocker. So then we'd write Roman's example as something like
 {{{#!hs
 import GHC.Exts (pattern _#)
 poll a = r >>= f
   where
     f _# = poll a
 }}}

 See also #9520, #8457. #12656 is a bit different, but it is the ticket I
 was prompted to remember by Roman's SO post. #12620 has a proposed
 solution but I think tying the "no floating" annotation to a lambda rather
 than an expression within the lambda might be more robust and easier to
 understand.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13080#comment:18>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler