tags:

views:

149

answers:

3

In a comment on this answer (which suggests using bit-shift operators over integer multiplication / division, for performance), I queried whether this would actually be faster. In the back of my mind is an idea that at some level, something will be clever enough to work out that >> 1 and / 2 are the same operation. However, I'm now wondering if this is in fact true, and if it is, at what level it occurs.

A test program produces the following comparative CIL (with optimize on) for two methods that respectively divide and shift their argument:

  IL_0000:  ldarg.0
  IL_0001:  ldc.i4.2
  IL_0002:  div
  IL_0003:  ret
} // end of method Program::Divider

versus

  IL_0000:  ldarg.0
  IL_0001:  ldc.i4.1
  IL_0002:  shr
  IL_0003:  ret
} // end of method Program::Shifter

So the C# compiler is emitting div or shr instructions, without being clever. I would now like to see the actual x86 assembler that the JITter produces, but I have no idea how to do this. Is it even possible?

edit to add

Findings

Thanks for answers, have accepted the one from nobugz because it contained the key information about that debugger option. What eventually worked for me is:

  • Switch to Release configuration
  • In Tools | Options | Debugger, switch off 'Suppress JIT optimization on module load' (ie we want to allow JIT optimization)
  • Same place, switch off 'Enable Just My Code' (ie we want to debug all code)
  • Put a Debugger.Break() statement somewhere
  • Build the assembly
  • Run the .exe, and when it breaks, debug using the existing VS instance
  • Now the Disassembly window shows you the actual x86 that's going to be executed

The results were enlightening to say the least - it turns out the JITter can actually do arithmetic! Here's edited samples from the Disassembly window. The various -Shifter methods divide by powers of two using >>; the various -Divider methods divide by integers using /

 Console.WriteLine(string.Format("
     {0} 
     shift-divided by 2: {1} 
     divide-divided by 2: {2}", 
     60, TwoShifter(60), TwoDivider(60)));

00000026  mov         dword ptr [edx+4],3Ch 
...
0000003b  mov         dword ptr [edx+4],1Eh 
...
00000057  mov         dword ptr [esi+4],1Eh

Both statically-divide-by-2 methods have not only been inlined, but the actual computations have been done by the JITter

Console.WriteLine(string.Format("
    {0} 
    divide-divided by 3: {1}", 
    60, ThreeDivider(60)));

00000085  mov         dword ptr [esi+4],3Ch 
...
000000a0  mov         dword ptr [esi+4],14h

Same with statically-divide-by-3.

Console.WriteLine(string.Format("
    {0} 
    shift-divided by 4: {1} 
    divide-divided by 4 {2}", 
    60, FourShifter(60), FourDivider(60)));

000000ce  mov         dword ptr [esi+4],3Ch 
...
000000e3  mov         dword ptr [edx+4],0Fh 
...
000000ff  mov         dword ptr [esi+4],0Fh

And statically-divide-by-4.

The best:

Console.WriteLine(string.Format("
    {0} 
    n-divided by 2: {1} 
    n-divided by 3: {2} 
    n-divided by 4: {3}", 
    60, Divider(60, 2), Divider(60, 3), Divider(60, 4)));

0000013e  mov         dword ptr [esi+4],3Ch 
...
0000015b  mov         dword ptr [esi+4],1Eh 
...
0000017b  mov         dword ptr [esi+4],14h 
...
0000019b  mov         dword ptr [edi+4],0Fh

It's inlined and then computed all these static divisions!

But what if the result isn't static? I added to code to read an integer from the Console. This is what it produces for the divisions on that:

Console.WriteLine(string.Format("
    {0} 
    shift-divided by 2:  {1} 
    divide-divided by 2: {2}", 
    i, TwoShifter(i), TwoDivider(i)));

00000211  sar         eax,1 
...
00000230  sar         eax,1

So despite the CIL being different, the JITter knows that dividing by 2 is right-shifting by 1.

Console.WriteLine(string.Format("
    {0} 
    divide-divided by 3: {1}", i, ThreeDivider(i)));

00000283 idiv eax,ecx

And it knows you have to divide to divide by 3.

Console.WriteLine(string.Format("
    {0} 
    shift-divided by 4: {1} 
    divide-divided by 4 {2}", 
    i, FourShifter(i), FourDivider(i)));

000002c5  sar         eax,2 
...
000002ec  sar         eax,2

And it knows that dividing by 4 is right-shifting by 2.

Finally (the best again!)

Console.WriteLine(string.Format("
    {0} 
    n-divided by 2: {1} 
    n-divided by 3: {2} 
    n-divided by 4: {3}", 
    i, Divider(i, 2), Divider(i, 3), Divider(i, 4)));

00000345  sar         eax,1 
...
00000370  idiv        eax,ecx 
...
00000395  sar         esi,2

It has inlined the method and worked out the best way to do things, based on the statically-available arguments. Nice.


So yes, somewhere in the stack between C# and x86, something is clever enough to work out that >> 1 and / 2 are the same. And all this has given even more weight in my mind to my opinion that adding together the C# compiler, the JITter, and the CLR makes a whole lot more clever than any little tricks we can try as humble applications programmers :)

+3  A: 

Yes. Visual Studio has a built in disassembler to do that. You have to add the command to your menu bar though. Go to Extras/Customize/Commands (I don't know if they are really called that way in the english version though) and add the command Dissassembly, which is unter Debugging, somewhere to your menu bar.

Then, set a breakpoint in your program and when it breaks, click on this Disassembly command. VS will show you the disassembled machine code.

Example output for a Divider-method:

public static int Divider(int intArg)
    {
00000000  push        ebp  
00000001  mov         ebp,esp 
00000003  push        edi  
00000004  push        esi  
00000005  push        ebx  
00000006  sub         esp,34h 
00000009  mov         esi,ecx 
0000000b  lea         edi,[ebp-38h] 
0000000e  mov         ecx,0Bh 
00000013  xor         eax,eax 
00000015  rep stos    dword ptr es:[edi] 
00000017  mov         ecx,esi 
00000019  xor         eax,eax 
0000001b  mov         dword ptr [ebp-1Ch],eax 
0000001e  mov         dword ptr [ebp-3Ch],ecx 
00000021  cmp         dword ptr ds:[00469240h],0 
00000028  je          0000002F 
0000002a  call        6BA09D91 
0000002f  xor         edx,edx 
00000031  mov         dword ptr [ebp-40h],edx 
00000034  nop              
    return intArg / 2;
00000035  mov         eax,dword ptr [ebp-3Ch] 
00000038  sar         eax,1 
0000003a  jns         0000003F 
0000003c  adc         eax,0 
0000003f  mov         dword ptr [ebp-40h],eax 
00000042  nop              
00000043  jmp         00000045 
    }
Maximilian Mayerl
No need to add that command to VS, it's on the Debug->Windows menu.
Lasse V. Karlsen
+2  A: 

While you're debugging (and only while you're debugging) just click at Debug - Windows - Disassembly or press the corresponding shortcut Ctrl+Alt+D.

Oliver
+4  A: 

You won't get meaningful results until you configure the debugger. Tools + Options, Debugging, General, turn off "Suppress JIT optimization on module load". Switch to the Release mode configuration. A sample snippet:

static void Main(string[] args) {
  int value = 4;
  int result = divideby2(value);
}

You are doing it right if the disassembly looks like this:

00000000  ret

You'll have to fool the JIT optimizer to force the expression to be evaluated. Using Console.WriteLine(variable) can help. Then you ought to see something like this:

0000000a  mov         edx,2 
0000000f  mov         eax,dword ptr [ecx] 
00000011  call        dword ptr [eax+000000BCh]

Yup, it evaluated the result at compile time. Works pretty well, doesn't it.

Hans Passant