[GHC] #12354: Word foldl' isn't optimized as well as Int foldl'

1 Jul 2016

      #12354: Word foldl' isn't optimized as well as Int foldl'
-------------------------------------+-------------------------------------
           Reporter:  kjslag         |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  Runtime
  Unknown/Multiple                   |  performance bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 {{{#!hs
 import Data.List

 test :: Int -> Int
 test n = foldl' (+) 0 [1..n]

 main :: IO ()
 main = do
   print $ test $ 10^8
 }}}

 GHC optimizes the above code to the point that the garbage collector
 doesn't even have to do anything:

 {{{
 $ ghc -rtsopts -O2 testInt && ./testInt +RTS -s
 [1 of 1] Compiling Main             ( testInt.hs, testInt.o )
 Linking testInt ...
 5000000050000000
           51,752 bytes allocated in the heap
            3,480 bytes copied during GC
           44,384 bytes maximum residency (1 sample(s))
           17,056 bytes maximum slop
                1 MB total memory in use (0 MB lost due to fragmentation)

                                      Tot time (elapsed)  Avg pause  Max
 pause
   Gen  0         0 colls,     0 par    0.000s   0.000s     0.0000s
 0.0000s
   Gen  1         1 colls,     0 par    0.000s   0.000s     0.0001s
 0.0001s

   INIT    time    0.000s  (  0.000s elapsed)
   MUT     time    0.101s  (  0.101s elapsed)
   GC      time    0.000s  (  0.000s elapsed)
   EXIT    time    0.000s  (  0.000s elapsed)
   Total   time    0.103s  (  0.102s elapsed)

   %GC     time       0.1%  (0.1% elapsed)

   Alloc rate    511,162 bytes per MUT second

   Productivity  99.8% of total user, 100.9% of total elapsed
 }}}

 However, if I change the type of {{{test}}} to {{{test :: Word -> Word}}},
 then a lot of garbage is produced and the code runs 40x slower:

 {{{
 ghc -rtsopts -O2 testWord && ./testWord +RTS -s
 [1 of 1] Compiling Main             ( testWord.hs, testWord.o )
 Linking testWord ...
 5000000050000000
   11,200,051,784 bytes allocated in the heap
        1,055,520 bytes copied during GC
           44,384 bytes maximum residency (2 sample(s))
           21,152 bytes maximum slop
                1 MB total memory in use (0 MB lost due to fragmentation)

                                      Tot time (elapsed)  Avg pause  Max
 pause
   Gen  0     21700 colls,     0 par    0.077s   0.073s     0.0000s
 0.0000s
   Gen  1         2 colls,     0 par    0.000s   0.000s     0.0001s
 0.0001s

   INIT    time    0.000s  (  0.000s elapsed)
   MUT     time    4.551s  (  4.556s elapsed)
   GC      time    0.077s  (  0.073s elapsed)
   EXIT    time    0.000s  (  0.000s elapsed)
   Total   time    4.630s  (  4.630s elapsed)

   %GC     time       1.7%  (1.6% elapsed)

   Alloc rate    2,460,957,186 bytes per MUT second

   Productivity  98.3% of total user, 98.3% of total elapsed
 }}}

 I expected the performance to be nearly identical.
 I'm using GHC version 8.0.1 on x86_64 Arch Linux.

 I asked about this on stackoverflow, and the issue appears to be related
 to rewrite rules:
 [http://stackoverflow.com/a/38113639/6531137]

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

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

tags

participants (1)