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?
On Mon, Jan 28, 2013 at 4:27 PM, 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?
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
Shachaf Ben-Kiki
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!
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
participants (3)
-
Artyom Kazak -
Daniel Fischer -
Shachaf Ben-Kiki