[Haskell-cafe] quotRem and divMod

[Artyom Kazak]

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@(I32# x#) y@(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
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Shachaf Ben-Kiki]

On Mon, Jan 28, 2013 at 4:27 PM, Artyom Kazak <artyom...@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@(I32# x#) y@(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@(I32# x#) y@(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

Shachaf

[Daniel Fischer]

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@(I32# x#) y@(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)
movq %rax,%rbx
movq $GHC.Int.I32#_con_info,-8(%r12)
movslq %edx,%rax
movslq %ebx,%rbx
addq %rax,%rbx

as the relevant part of the assembly, with only one idivq instruction.

I don't know whether you can rely on the code generator emitting only one
division instruction in all cases, but in simple cases, it does (on x86_64, at
least).

Cheers,
Daniel

[Artyom Kazak]

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

> That code is from base 4.5. Here's base 4.6:
>
> quotRem x@(I32# x#) y@(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!