[GHC] #10788: performance regression involving minimum (and maybe Vector)

23 Aug 2015

      #10788: performance regression involving minimum (and maybe Vector)
-------------------------------------+-------------------------------------
              Reporter:  rwbarton    |             Owner:
                  Type:  bug         |            Status:  new
              Priority:  normal      |         Milestone:
             Component:  Compiler    |           Version:  7.10.1
              Keywords:              |  Operating System:  Unknown/Multiple
          Architecture:              |   Type of failure:  Runtime
  Unknown/Multiple                   |  performance bug
             Test Case:              |        Blocked By:
              Blocking:              |   Related Tickets:
Differential Revisions:              |
-------------------------------------+-------------------------------------
 This program (taken from http://stackoverflow.com/questions/32158319
 /difference-in-performance-for-coin-change-between-haskell-and-c) runs
 about 50% slower when compiled with `ghc-7.10.1 -O` compared to `ghc-7.8.4
 -O`.
 {{{
 import Data.Vector.Unboxed as U ((!), constructN, length)

 coinchangev :: Int -> [Int] -> Int
 coinchangev n cs = v ! n
  where v = constructN (n+1) f
        f w = case U.length w of
              0 -> 0
              m -> 1 + minimum [w ! x | x <- map (m-) cs, x >= 0]

 main = print $ coinchangev 10000000 [1, 5, 10, 25, 100]
 }}}

 However if I change `minimum` to `sum`, while the runtime in 7.8.4 is
 unchanged, the runtime in 7.10.1 drops by a factor of 5! Allocations also
 decrease by a large factor. So my guess is that something has gone wrong
 with call arity analysis for `minimum` (and gone very right for `sum`).

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