Re: [Haskell-cafe] quotRem and divMod

2013-01-29 Thread 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

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] quotRem and divMod

2013-01-29 Thread Artyom Kazak 
Shachaf Ben-Kiki shac...@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!


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] quotRem and divMod

2013-01-28 Thread 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] quotRem and divMod

2013-01-28 Thread Shachaf Ben-Kiki 
On Mon, Jan 28, 2013 at 4:27 PM, Artyom Kazak artyom.ka...@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

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe