Artyom Kazak | 29 Jan 01:27 2013
Picon

quotRem and divMod

Hi!

I’ve always thought that `quotRem` is faster than `quot` + `rem`, since  
both `quot` and `rem` are just "wrappers" that compute both the quotient  
and the remainder and then just throw one out. However, today I looked  
into the implementation of `quotRem` for `Int32` and found out that it’s  
not true:

     quotRem x <at> (I32# x#) y <at> (I32# y#)
         | y == 0                     = divZeroError
         | x == minBound && y == (-1) = overflowError
         | otherwise                  = (I32# (narrow32Int# (x# `quotInt#`  
y#)),
                                         I32# (narrow32Int# (x# `remInt#`  
y#)))

Why? The `DIV` instruction computes both, doesn’t it? And yet it’s being  
performed twice here. Couldn’t one of the experts clarify this bit?

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Shachaf Ben-Kiki | 29 Jan 07:09 2013
Picon

Re: quotRem and divMod

On Mon, Jan 28, 2013 at 4:27 PM, Artyom Kazak <artyom.kazak <at> gmail.com> wrote:
> Hi!
>
> I’ve always thought that `quotRem` is faster than `quot` + `rem`, since both
> `quot` and `rem` are just "wrappers" that compute both the quotient and the
> remainder and then just throw one out. However, today I looked into the
> implementation of `quotRem` for `Int32` and found out that it’s not true:
>
>     quotRem x <at> (I32# x#) y <at> (I32# y#)
>         | y == 0                     = divZeroError
>         | x == minBound && y == (-1) = overflowError
>         | otherwise                  = (I32# (narrow32Int# (x# `quotInt#`
> y#)),
>                                         I32# (narrow32Int# (x# `remInt#`
> y#)))
>
> Why? The `DIV` instruction computes both, doesn’t it? And yet it’s being
> performed twice here. Couldn’t one of the experts clarify this bit?
>

That code is from base 4.5. Here's base 4.6:

    quotRem x <at> (I32# x#) y <at> (I32# y#)
        | y == 0                     = divZeroError
          -- Note [Order of tests]
        | y == (-1) && x == minBound = (overflowError, 0)
        | otherwise                  = case x# `quotRemInt#` y# of
                                       (# q, r #) ->
                                           (I32# (narrow32Int# q),
                                            I32# (narrow32Int# r))
(Continue reading)

Artyom Kazak | 29 Jan 13:26 2013
Picon

Re: quotRem and divMod

Shachaf Ben-Kiki <shachaf <at> gmail.com> писал(а) в своём письме Tue, 29 Jan  
2013 09:09:37 +0300:

> That code is from base 4.5. Here's base 4.6:
>
>     quotRem x <at> (I32# x#) y <at> (I32# y#)
>         | y == 0                     = divZeroError
>           -- Note [Order of tests]
>         | y == (-1) && x == minBound = (overflowError, 0)
>         | otherwise                  = case x# `quotRemInt#` y# of
>                                        (# q, r #) ->
>                                            (I32# (narrow32Int# q),
>                                             I32# (narrow32Int# r))
>
> So it looks like it was improved in GHC 7.6. In particular, by this
> commit:  
> http://www.haskell.org/pipermail/cvs-libraries/2012-February/014880.html
>
>     Shacha

Well, I’m glad to know that it has been fixed in the newer GHC (I’m still  
on 7.4). Thanks!

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Daniel Fischer | 29 Jan 12:39 2013

Re: quotRem and divMod

On Tuesday 29 January 2013, 03:27:41, Artyom Kazak wrote:
> Hi!
> 
> I’ve always thought that `quotRem` is faster than `quot` + `rem`, since
> both `quot` and `rem` are just "wrappers" that compute both the quotient
> and the remainder and then just throw one out. However, today I looked
> into the implementation of `quotRem` for `Int32` and found out that it’s
> not true:
> 
>      quotRem x <at> (I32# x#) y <at> (I32# y#)
> 
>          | y == 0                     = divZeroError
>          | x == minBound && y == (-1) = overflowError
>          | otherwise                  = (I32# (narrow32Int# (x# `quotInt#`
> 
> y#)),
>                                          I32# (narrow32Int# (x# `remInt#`
> y#)))
> 
> Why? The `DIV` instruction computes both, doesn’t it? And yet it’s being
> performed twice here. Couldn’t one of the experts clarify this bit?

It's not necessarily performed twice.

func a b = case a `quotRem` b of
             (q, r) -> q+r

produces

    idivq 8(%rbp)
(Continue reading)


Gmane