Re: [GHC] #13379: Space leak / quadratic behavior when inlining

6 Mar 2017

      #13379: Space leak / quadratic behavior when inlining
-------------------------------------+-------------------------------------
        Reporter:  jberryman         |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:
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 jberryman):
...
How did an example like this arise in practice?
In attempting to space profile some code where there seemed to be a
 constant small amount of allocation at each call site I tried creating a
 file like this one. I filed the bug because it seemed likely that this was
 evidence of performance issues in more realistic code.
...
I'm not too surprised this is a difficult case ... we end up
 (eventually) re-associating everything the other way
Ah, interesting! This does seem to be related to `(>>)` and not the code I
 marked `INLINE` in the Main file. The code compiles quickly with:

 {{{
 import Prelude hiding ((>>))
 import qualified Prelude as P

 infixr 1 >>
 {-# NOINLINE (>>) #-}
 (>>) = (P.>>)
 }}}

 The NOINLINE is necessary, and we see `f` get inlined everywhere.

 But my naive response, knowing nothing about how to implement an inliner,
 and looking at a 191kb core file with a bunch of nested:

 {{{
     of _ [Occ=Dead] { (# ipv, ipv1 #) ->
     case hPutStr2 stdout ipv1 True ipv
     of _ [Occ=Dead] { (# ipv2, ipv3 #) ->
     case hPutStr2 stdout ipv1 True ipv2
     of _ [Occ=Dead] { (# ipv4, ipv5 #) ->
     case hPutStr2 stdout ipv1 True ipv4
     of _ [Occ=Dead] { (# ipv6, ipv7 #) ->
     case hPutStr2 stdout ipv1 True ipv6
     ...
 }}}

 ...is that I could do this inlining case manually in milliseconds (vs ~40
 seconds for whatever number of lines I was just testing with) with vim,
 sed, a bash script, etc. and without GB of memory for my working set. And
 so I am inclined to believe that there is a space leak here. Who knows if
 real code will benefit from fixing it though.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:3
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler