[GHC] #5161: Poor performance of division; unnecessary branching

[GHC]

#5161: Poor performance of division; unnecessary branching
------------------------------------------------------------+---------------
    Reporter:  rtvd                                         |        Owner:                         
        Type:  bug                                          |       Status:  patch                  
    Priority:  normal                                       |    Milestone:                         
   Component:  libraries/base                               |      Version:  7.0.3                  
    Keywords:  div quot rem mod performance slow branching  |     Testcase:                         
   Blockedby:                                               |   Difficulty:                         
          Os:  Unknown/Multiple                             |     Blocking:                         
Architecture:  Unknown/Multiple                             |      Failure:  Runtime performance bug
------------------------------------------------------------+---------------

Comment(by simonpj):

 Your changes replace the guard
 {{{
    | x == minBound && y == (-1) = overflowError
 }}}
 by
 {{{
    | y == (-1) && x == minBound = overflowError
 }}}
 At first I couldn't see how this would make any difference.   After all,
 if `y` is 2 (say), then the overflow case is statically inaccessible, so
 the test should vanish. Here's why it doesn't.  Initially we have
 something roughly like this:
 {{{
 quot x y = case x of
              -9223372036854775808 -> case y of
                                         -1 -> overflowError
                                         DEFAULT -> x `quot#` y
              DEFAULT -> x `quot#` y
 }}}
 (I'm omitting the unboxing etc.)

 Now if we have the call {{{(p `quot` 2)}}}, and we inline `quot` we get:
 {{{
   case p of
     -9223372036854775808 -> case 2 of
                               -1 -> overflowError
                               DEFAULT -> p `quot#` 2
     DEFAULT -> p `quot#` 2
 }}}
 The inner case simplifies, leaving
 {{{
   case p of
     -9223372036854775808 -> p `quot#` 2
     DEFAULT              -> p `quot#` 2
 }}}
 At this point I thought we'd just have a case with two identical branches,
 which is eliminated (assuming it doesn't affect strictness, which it
 doesn't in this case), leaving the desired {{{(p `quot#` 1)}}}.

 BUT in the `minBound` branch we know what `p` is, and GHC cleverly does
 the division at compile time, giving
 {{{
   case p of
     -9223372036854775808 -> -4611686018427387904
     DEFAULT              -> p `quot#` 2
 }}}
 Darn!  Now the branches aren't identical!

 By switching the order of tests you've stopped this happening.  But it'll
 happen instead if you have a constant '''numerator'''.  The term {{{(2
 `quot` q)}}} will turn into
 {{{
 case q of
   -1      -> 0
   DEFAULT -> 2 `quot#` q
 }}}
 Constant denominators are more common than constant numerators, so I think
 your patch is a good one -- Ian can you apply please?  ''But also can you
 add this Trac comment into the code with `Note [Ordering of tests]` or
 something, and point to it from the test sites?''

 I wish I could see a good way to make GHC generate the best code
 regardless of test ordering.  I can think of some un-satisfying solutions:
  * Delay constant folding until a later phase
  * Delay case-of-case until a later phase
 but neither are great. Phase ordering is very delicate and non-modular.

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