[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:                    |
-------------------------------------+-------------------------------------
Changes (by thomie):

 * priority:  normal => high
 * milestone:   => 8.0.2


@@ -192,1 +192,2 @@
-         subprocess.call(['ghc-8.0.1', '-v0', '-O', tempfile])
+         subprocess.call(['ghc-8.0.1', '-fforce-recomp', '-v0', '-O',
+ tempfile])

New description:

 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', '-fforce-recomp', '-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#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler