Does the JIT optimize ^2 int divides as bit shifts?

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Colin Reid - 04 May 2005 18:06 GMT

I'm doing a bunch of x/2 calculations in a tight loop where x is an int. Does
that automatically get optimized as >>1? Is there a difference between /2 and

>>1 when working with ints?

I prefer the readability of /2 but will use >>1 if it's slightly faster.

Reply to this Message

Jon Skeet [C# MVP] - 04 May 2005 19:02 GMT

> I'm doing a bunch of x/2 calculations in a tight loop where x is an int. Does
> that automatically get optimized as >>1? Is there a difference between /2 and
> >>1 when working with ints?
>
> I prefer the readability of /2 but will use >>1 if it's slightly faster.

Is this actually in a performance critical section of code? If it's
not, go with the more readable code.

As for whether or not they're equivalent - only for positive integers.

-3 / 2 == -1
-3 >> 1 == -2

Signature

Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

Reply to this Message

Colin Reid - 04 May 2005 19:38 GMT

Hi Jon -

It's a piece of math intensive code we're trying to speed up as much as
possible.

I checked the performance with a couple of tests on .NET 2, it's kind of
interesting:

int q = 10;
for (int i = 0; i < 1000000000; i++)
q /= 2;

runs in 2.8 seconds for a billion divides. The same thing with q >>= 1 runs
in 2.4 seconds. Out of curiousity I unwound the loop eight times and got 8.3
and 3.8 seconds respectively for a billion loops.

So to answer my own question, I guess (i) there's no optimization, and (ii)
man it really doesn't matter if a simple for-loop has that much relative
overhead.

Colin

> > I'm doing a bunch of x/2 calculations in a tight loop where x is an int. Does
> > that automatically get optimized as >>1? Is there a difference between /2 and
[quoted text clipped - 9 lines]
> -3 / 2 == -1
> -3 >> 1 == -2

Reply to this Message

Colin Reid - 04 May 2005 19:50 GMT

Incidently there seems to be the same ~3:1 difference for uint operations
(x/2 vs x>>1). Maybe this is a reasonable optimization for the compiler team
when people are dividing unsigned ints by constant power-of-two denominators.

> Hi Jon -
>
[quoted text clipped - 31 lines]
> > -3 / 2 == -1
> > -3 >> 1 == -2

Reply to this Message

Chris Taylor - 01 Jun 2005 23:43 GMT

Hi Colin,

The JIT does optimize the integer divide to use a shift. More specifically
it is optimized to perform an arithmetic shift (sar)
which maintains the sign bit. The C# >> operator is ultimately also JITted
to the sar instruction.

C#: i = i >> 1;
JIT: sar ebx, 1

C#: i = i / 2;
JIT: mov eax, edi
sar eax, 1 -- Optimized to shift
jns skip
adc eax, 0
skip: mov edi, eax

As you can see the divide carries with it additional overhead of adjusting
for the sign to ensure mathematical correctness and in this case there is
also register selection overheads. This optimization is for all divisors
which are a multiple of 2.

Signature

Chris Taylor
http://dotnetjunkies.com/weblog/chris.taylor

> Incidently there seems to be the same ~3:1 difference for uint operations
> (x/2 vs x>>1). Maybe this is a reasonable optimization for the compiler team
[quoted text clipped - 35 lines]
> > > -3 / 2 == -1
> > > -3 >> 1 == -2

Reply to this Message

Does the JIT optimize ^2 int divides as bit shifts?

Free Magazines