#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
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
