[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:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           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:
-------------------------------------+-------------------------------------
 GHC 8 has a lot of trouble compiling the following program:

 {{{#!hs
 module Serialize where

 data Result a = Success a | Error String

 {- 80 guards

    ghc-7.10.3 -O :  0.3s
    ghc-8.0.1 -O  :  1.8s
 -}

 instance Functor Result where
     {-# INLINE fmap #-}
     fmap | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f
          | bool = f

       where
         bool = undefined
         f = undefined
 }}}

 Here are some timing results, depending on the number of `| bool = f`
 clauses:
 {{{
 * ghc-8.0.1

 N clauses : time (s)
 10        : 0.61
 20        : 0.78
 40        : 1.03
 80        : 1.64
 160       : 2.83
 320       : 5.16
 640       : 10.37
 1280      : 21.16

 * ghc-7.10.3

 N clauses : time (s)
 10        : 0.33
 20        : 0.29
 40        : 0.34
 80        : 0.30
 160       : 0.32
 320       : 0.35
 640       : 0.48
 1280      : 0.80
 }}}


 I think this compile time difference is caused by the `CallStack` changes
 introduced in GHC 8.0. When I use a version of `undefined` that doesn't
 have a CallStack, there is no difference in compile time when using GHC
 7.10 or GHC 8.0.

 This is my implementation of `undefined` without `CallStack`:

 {{{
 import GHC.Exception (errorCallException)
 import GHC.Prim (raise#)
 import Prelude (Char)

 error :: [Char] -> a
 error s = raise# (errorCallException s)

 undefined :: a
 undefined = error "undefined without callstack"
 }}}

 This is the quick and dirty Python script I used to generate those timing
 results (ghc version is hardcoded):
 {{{#!py
 import os
 import tempfile
 import time
 import subprocess

 def src(n):
     return '''
 module Test where

 data Result a = Success a | Error String

 instance Functor Result where
     {{-# INLINE fmap #-}}
     fmap {0}
       where
         bool = undefined
         f = undefined

 '''.format('\n        | bool = f' * n)


 tempfile = tempfile.mktemp('.hs')
 print('tempfile = {0}'.format(tempfile))

 print('N clauses : time (s)')
 for i in range(8):
     n = 10 * 2 ** i
     with open(tempfile, 'w') as f:
         f.write(src(n))
         f.flush()

         t0 = time.time()
         subprocess.call(['ghc-8.0.1', '-v0', '-O', tempfile])
         t1 = time.time()

         print(str(n).ljust(10) + ': %.2f' % (t1 - t0))

 os.remove(tempfile)
 }}}

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