Opened 5 years ago

Last modified 4 years ago

#9617 new feature request

Implement `quot` and `rem` using `quotRem`; implement `div` and `mod` using `divMod`

Reported by: dfeuer Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.9
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

If I define

myquot x y = fst (quotRem x y)
myrem x y = snd (quotRem x y)

bob :: Int -> Int -> Int
bob x y = myquot x y + myrem x y

Then I get this beautiful thing with GHC 7.9 (I don't get anything beautiful in 7.8.3, so great work, compiler gurus!):

bob :: Int -> Int -> Int
bob =
  \ (w_sWx :: Int) (w1_sWy :: Int) ->
    case w_sWx of _ { I# ww1_sWB ->
    case w1_sWy of _ { I# ww3_sWF ->
    case ww3_sWF of wild_aSo {
      __DEFAULT ->
        case quotRemInt# ww1_sWB wild_aSo of _ { (# ipv_aSr, ipv1_aSs #) ->
        I# (+# ipv_aSr ipv1_aSs)
        };
      (-1) ->
        case ww1_sWB of wild1_aSu {
          __DEFAULT ->
            case quotRemInt# wild1_aSu (-1) of _ { (# ipv_aSx, ipv1_aSy #) ->
            I# (+# ipv_aSx ipv1_aSy)
            };
          (-9223372036854775808) -> case overflowError of wild2_00 { }
        };
      0 -> case divZeroError of wild1_00 { }
    }
    }
    }

However, if I write

jones :: Int -> Int -> Int
jones x y = quot x y + rem x y

I don't get anything nice.

What I'm thinking (perhaps out of ignorance) is that we might be able to use the myquot and myrem definitions if it's possible to get some sort of dead code elimination to recognize when one or the other is not used, at which point it can replace the quotRemInt# with quotInt# or remInt#. Then we can quit the silly quotRem dance in user code and just write what we actually mean. Of course, exactly the same thing applies to divMod.

Change History (4)

comment:1 Changed 5 years ago by dfeuer

I think the dead code elimination is probably pretty simple here. If we see

case quotRemInt# x y of _ { (# q, r #) -> expr }

and either q or r is not free in expr, replace that with

case quotInt# x y of _ { q -> expr }

or the other way around. I don't know where code to do such a thing would belong, however. It certainly would have to be post-CSE.


EDIT

I've been playing around with myquot and myrem a little more, and the CSE seems to work impressively well even in fairly complex situations. It doesn't work for unknown Integral types, but I don't think that's a big deal—specialization takes care of it pretty well. Obviously, if someone's doing something weird, they can always use quotRem directly, but I think doing this would be worth the trouble for the now-common cases where it does work. It's a lot easier to read and write code using quot and rem than quotRem, and it's a sad old story to have to tell beginners about this.

Last edited 5 years ago by dfeuer (previous) (diff)

comment:2 Changed 5 years ago by dfeuer

Summary: Try to replace `quot` and `rem` with `quotRem` when possibleImplement `quot` and `rem` using `quotRem`; implement `div` and `mod` using `divMod`

Good news:

It seems it may not even be necessary (for Int, at least) to find a way to turn the quotRemInt# back into quotInt# or remInt#—the performance difference there appears to be somewhere between tiny and nonexistent. It's not clear to me whether that will be the same for divMod, which adds a few more operations over div or mod (but fast ones).

More good news:

After bashing my head against it for a few hours, I managed to get divMod to do what I wanted. I had to swap the divide by zero test with the arithmetic overflow test. I don't understand why this made it work, but it seems to have done the job. It looks like this:

divZeroError# :: Void# -> (# Int#, Int# #)
divZeroError# a = error "Divide by zero"

overflowError# :: Void# -> Int#
overflowError# a = error "Arithmetic overflow: attempted to divide minBound by -1"

divModInt# :: Int# -> Int# -> (# Int#, Int# #)
x# `divModInt#` y#
 | isTrue# (y# ==# (-1#)) &&
     isTrue# (x# ==# (case minBound of I# mb -> mb))
       = (# overflowError# void#, 0# #)
 | isTrue# (y# ==# 0#) = divZeroError# void#
 | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
                                    case (x# -# 1#) `quotRemInt#` y# of
                                      (# q, r #) -> (# q -# 1#, r +# y# +# 1# #)
 | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
                                    case (x# +# 1#) `quotRemInt#` y# of
                                      (# q, r #) -> (# q -# 1#, r +# y# -# 1# #)
 | otherwise                                =
                                    x# `quotRemInt#` y#

divModInt :: Int -> Int -> (Int, Int)
(I# x) `divModInt` (I# y) = case x `divModInt#` y of
                            (# q, r #) -> (I# q, I# r)

div :: Int -> Int -> Int
{-# INLINE div #-}
div x y = fst (divModInt x y)
infixl 7 `div`

mod :: Int -> Int -> Int
{-# INLINE mod #-}
x `mod` y = snd (divModInt x y)
infixl 7 `mod`

Using these definitions, it seems things stay sufficiently similar long enough for CSE to do its job, so

divPlusMod :: Int -> Int -> Int
divPlusMod x y = div x y + mod x y

compiles into something very similar to what you'd get from

divPlusModStandard :: Int -> Int -> Int
divPlusModStandard x y = case divMod x y of
                           (q, r) -> q + r

but with the proposed definitions, I'm getting quite a bit less code duplication, which seems to be a small but good thing.

comment:3 Changed 5 years ago by dfeuer

Argh. It looks like I got that wrong. That's only working because it's too big to inline. divMod may just be hopeless.

comment:4 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug
Note: See TracTickets for help on using tickets.