[GHC] #12150: Compile time performance degradation on code that uses undefined/error with CallStacks

[GHC]

#12150: Compile time performance degradation on code that uses undefined/error with
CallStacks
-------------------------------------+-------------------------------------
        Reporter:  thomie            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.0.2
       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:  #10844            |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by thomie):

 gridaphobe: I was investigating a report of some (other) compile time
 regression (I don't remember which ticket or which program). I tried to
 find a small reproducible example, deleting as much code as possible, and
 replacing function bodies with `undefined`.

 I then noticed something fishy was going on with `undefined` itself, and
 came up with the above example. So the above example doesn't look anything
 like the original program I was investigating.

 == Constant factor performance degradation ==

 The measurements presented in the description make it seem like 7.10.3
 took `O(1)` seconds to compile the program (where `n` is the number of
 guards), while 8.0.1 took `O(n)` seconds. This is not the case: **both
 versions of GHC need `O(n)` time.**

 Running the program from the description a bit longer:

 7.10.3:
 {{{
 N clauses : time (s)
 10        : 1.39
 20        : 0.28
 40        : 0.30
 80        : 0.28
 160       : 0.36
 320       : 0.39
 640       : 0.53
 1280      : 0.74
 2560      : 1.17
 5120      : 2.11
 10240     : 4.21
 20480     : 8.18
 40960     : 17.15
 }}}

 So we're should really just be looking at constant factor performance
 differences.

 == Timing results ==
 Time (s) to compile the program with 1000 `bool = f` clauses with
 different versions of undefined and error:
 ||= bool/f= =||= ghc-7.10.3 =||= ghc-8.0.1 =||
 || old undefined || 0.6 || 0.8 ||
 || new undefined || 0.6 || 18 ||
 || myUndef :: a; myUndef = old undefined || 2.0 || 2.1 ||
 || myUndef :: a; myUndef = new undefined || 2.0 || 4.2 ||
 || old error || 6 || 6.5 ||
 || new error || 6 || 5 ||


 === Quotes ===

 > the CallStack-free variant [`myUndef :: a`] behaves just like the old
 undefined
 No, it is still 5x slower (4.2 vs 0.8 seconds).

 > if I [..] use the *old* error instead of undefined, I get a similar
 behavior to the *new* undefined
 No. 8.0.1 still takes 3x longer to compile the (new) `undefined` than it
 is to compile the (old or new) `error` (18 vs 5-6 seconds).

 > When we remove the CallStacks from undefined, GHC manages to optimize
 away the entire set of guards!
 Hmm, maybe the whole example is flawed.

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