[GHC] #3116: missed opportunity for call-pattern specialisation

[GHC]

#3116: missed opportunity for call-pattern specialisation
--------------------------------------+-------------------------------------
 Reporter:  duncan                    |          Owner:                  
     Type:  run-time performance bug  |         Status:  new             
 Priority:  normal                    |      Milestone:                  
Component:  Compiler                  |        Version:  6.10.1          
 Severity:  normal                    |     Resolution:                  
 Keywords:                            |       Testcase:                  
       Os:  Unknown/Multiple          |   Architecture:  Unknown/Multiple
--------------------------------------+-------------------------------------
Comment (by duncan):

 It's not directly related to the missing transformation, but we could
 actually do slightly better in the call-pattern specialisation in the
 above example, even in the case where it already works.

 As I understand it, for call-pattern specialisation we start with:
 {{{
 go !n bs = case bs of
   Empty                -> n
   Chunk p fpc o l bs'  ->
     go (n+1)
        (case l of
           1  -> bs'
           _  -> Chunk p fpc (o+1) (l-1) bs')
 }}}

 And we decide that it's profitable to specialise on the second argument
 for `Empty` and `Chunk _ _ _ _ _` patterns. We then define:

 {{{
 go_empty n                = go n Empty
 go_chunk n p fpc o l bs'  = go n (Chunk p fpc o l bs')
 }}}

 But, and this is the point, we leave the original `go` definition as it
 is. Of course later we apply the specialisation rules in the body of the
 original `go`.

 However, here is a potential improvement. We could redefine the original
 `go` in terms of its specialisations:

 {{{
 go n bs
   = case bs of
       Empty                -> go_empty n
       Chunk p fpc o l bs'  -> go_chunk b p fpc o l bs'
 }}}

 Now we can leave it up to the heuristics of the inliner to decide if it is
 actually profitable to inline `go_chunk` here or if it is better to leave
 it as a call. If we decide not to inline it then we would get:

 {{{
 go n bs
   = case bs of
       Empty                -> n
       Chunk p fpc o l bs'  -> go_chunk b p fpc o l bs'

 go_chunk n p fpc o l bs'
   = case l of
       1  -> go        (n+1) bs'
       _  -> go_chunk  (n+1) p fpc (o+1) (l-1) bs'
 }}}

 It seems to me there is little benefit here from inlining `go_chunk` into
 `go`. I've not benchmarked the two so I can't say for sure but this looks
 like it is the perfect code given the original definitions (though with
 the obvious unboxing). Indeed in this simple case it may not even be
 necessary to export the `go_chunk` specialisation rule because it is
 implicit in the new definition of `go` (though this would not be true if
 the inliner decided to inline `go_chunk` into the body of `go`).

 Anyway, the point is, there may be such cases and by redefining the
 original body in terms of the specialisation we give the inliner the
 opportunity to make that choice. I don't see any downsides to giving it
 the choice. I may be missing something of course.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3116#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler