Re: optimize div to right shift (NOT!)

Re: optimize div to right shift (NOT!)

[Jonathan Kimmitt]

> A C compiler would optimize this to a right shift. Changing that to 'Int64.shift_right n 1' speeds
> up the code.

Sorry to be a pedant, but this is not correct. The optimisation is only possible when the arguments
are unsigned integers which I don't think is specifiable when working in OCAML

# Int64.shift_right (-2L) 1;;
- : int64 = -1L (So far, so good)
# Int64.div (-1L) 2L;;
- : int64 = 0L (Good)
# Int64.shift_right (-1L) 1;;
- : int64 = -1L (Duh)

Re: [Caml-list] Re: optimize div to right shift (NOT!)

[Török Edwin]

On Mon, 13 Dec 2010 12:33:33 +0000
Jonathan Kimmitt <jonathan@kimmitt.co.uk> wrote:

> 
> > A C compiler would optimize this to a right shift. Changing that to
> > 'Int64.shift_right n 1' speeds up the code.
> 
> Sorry to be a pedant, but this is not correct. The optimisation is
> only possible when the arguments are unsigned integers 

That particular program never used negative integers.

> which I don't
> think is specifiable when working in OCAML

You are right, there is no way to tell ocaml that.

> 
> # Int64.shift_right (-2L) 1;;
> - : int64 = -1L (So far, so good)
> # Int64.div (-1L) 2L;;
> - : int64 = 0L (Good)
> # Int64.shift_right (-1L) 1;;
> - : int64 = -1L (Duh)

It is still possible to avoid the division, gcc generates this:
	movq	%rdi, %rax
	shrq	$63, %rax
	addq	%rdi, %rax
	sarq	%rax

Or a better example with division by 8:
	leaq	7(%rdi), %rax
	testq	%rdi, %rdi
	cmovns	%rdi, %rax
	sarq	$3, %rax

And division by non-power of two integers can optimized by replacing it
with multiplication with its inverse (which gcc and llvm don't do for
signed divisions, only for unsigned ones):
http://www.hackersdelight.org/HDcode/magic.c.txt
http://www.hackersdelight.org/HDcode/magicu.c.txt

Best regards,
--Edwin

Re: [Caml-list] Re: optimize div to right shift (NOT!)

[Benedikt Meurer]

On Dec 13, 2010, at 13:58 , Török Edwin wrote:

> It is still possible to avoid the division, gcc generates this:
> 	movq	%rdi, %rax
> 	shrq	$63, %rax
> 	addq	%rdi, %rax
> 	sarq	%rax
> 
> Or a better example with division by 8:
> 	leaq	7(%rdi), %rax
> 	testq	%rdi, %rdi
> 	cmovns	%rdi, %rax
> 	sarq	$3, %rax

ocamlopt does exactly this, atleast for x86-64.

> And division by non-power of two integers can optimized by replacing it
> with multiplication with its inverse (which gcc and llvm don't do for
> signed divisions, only for unsigned ones):
> http://www.hackersdelight.org/HDcode/magic.c.txt
> http://www.hackersdelight.org/HDcode/magicu.c.txt

The AMD64 optimization guide gives additional pointers here, i.e. it also lists replacement sequences for multiplication by constant.

> Best regards,
> --Edwin

greets,
Benedikt

RE: [Caml-list] Re: optimize div to right shift (NOT!)

[Jon Harrop]

Edwin wrote:
> http://www.hackersdelight.org/HDcode/magic.c.txt
> http://www.hackersdelight.org/HDcode/magicu.c.txt

Nice! :-)

Cheers,
Jon.