[GHC] #11095: -O0 -g slows GHC down on list literals (compared to -O0 without -g)

[GHC]

#11095: -O0 -g slows GHC down on list literals (compared to -O0 without -g)
-------------------------------------+-------------------------------------
        Reporter:  slyfox            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.10.2
      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):  phab:D3001
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by niteria):

 I suspect (I have yet to read the paper!) that the resulting term has
 quadratic size.

 We're building:
 {{{
 () : () : () : () : () : () : () : []
 }}}
 which becomes:
 {{{
 a = () : []
 b = () : a
 c = () : b
 d = () : c
 e = () : d
 f = () : e
 g = () : f
 }}}

 We then construct ticks for each of `a..g`:
 {{{
 ticks(a) = SrcLoc(a)
 ticks(b) = ticks(a) ++ SrcLoc(b)
 ticks(c) = ticks(b) ++ SrcLoc(c)
 ticks(d) = ticks(c) ++ SrcLoc(d)
 ticks(e) = ticks(d) ++ SrcLoc(e)
 ticks(f) = ticks(e) ++ SrcLoc(f)
 ticks(g) = ticks(f) ++ SrcLoc(g)
 -- the order of arguments here is important,
 -- we end up doing an equivalent of appending one element to a list
 -- we do that over all the expressions, for each SrcLoc
 }}}

 The reason my patch helped is this part of `mkTick'`:
 {{{
     -- For annotations this is where we make sure to not introduce
     -- redundant ticks.
       | tickishContains t t2              -> mkTick' top rest e
       | tickishContains t2 t              -> orig_expr
       | otherwise                         -> mkTick' top (rest . Tick t2)
 e
 }}}
 We almost always reach the `otherwise` case because the source locations
 are disjoint, so `tickishContains` is quite hot.

 Not only the result is quadratic, the function `wrapTicks` is quadratic as
 well:

 {{{
 wrapTicks (Floats flag floats0) expr = (Floats flag floats1, expr')
   where (floats1, expr') = foldrOL go (nilOL, expr) floats0
         -- ^ iterate over floats0
         go (FloatTick t) (fs, e) = ASSERT(tickishPlace t == PlaceNonLam)
                                    (mapOL (wrap t) fs, mkTick t e)
                                    -- ^ map over fs, proportional in size
 to floats0
         go other         (fs, e) = (other `consOL` fs, e)
         -- ^ fs can grow proportional in size to floats0
         wrap t (FloatLet bind)    = FloatLet (wrapBind t bind)
         wrap t (FloatCase b r ok) = FloatCase b (mkTick t r) ok
         wrap _ other              = pprPanic "wrapTicks: unexpected
 float!"
                                              (ppr other)
         wrapBind t (NonRec binder rhs) = NonRec binder (mkTick t rhs)
         wrapBind t (Rec pairs)         = Rec (mapSnd (mkTick t) pairs)
 }}}

 Sorry I can't explain it better, the important point I believe is that the
 result has quadratic size.

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