#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