C# compiler optimization?

[Leandro Oliveira]

Why does C# compiler generate code to func x()?

public class Test
{
private static void x(int b)
{
for (int i=0; i < b; i++)
{
int a = 0;
a = a;
}
}
public static void Main(string[] arg)
{
DateTime t;

t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
t = DateTime.Now;
x(int.Parse(arg[0]));
Console.WriteLine((DateTime.Now - t));
}
}

csc /optmize Test.cs

Test.exe 1000000000

Output:
00:00:04.2661770
00:00:04.2962205
00:00:04.3162495
00:00:04.2661770
00:00:04.2561625
00:00:04.5866410

Best Regards.

[Greg Ewing [MVP]]

Leandro, have you tried looking at the IL generated from your program? What
makes you think that it is generating code for x()?

--
Greg Ewing [MVP]
http://www.claritycon.com/

"Leandro Oliveira" <loli...@uolinc.com> wrote in message
news:eHun6SZkCHA.1664@tkmsftngp11...

[Leandro Oliveira]

This was generated:

.method private hidebysig static void x(int32 b) cil managed
{
// Code size 17 (0x11)
.maxstack 2
.locals init (int32 V_0,
int32 V_1)
IL_0000: ldc.i4.0
IL_0001: stloc.0
IL_0002: br.s IL_000c
IL_0004: ldc.i4.0
IL_0005: stloc.1
IL_0006: ldloc.1
IL_0007: stloc.1
IL_0008: ldloc.0
IL_0009: ldc.i4.1
IL_000a: add
IL_000b: stloc.0
IL_000c: ldloc.0
IL_000d: ldarg.0
IL_000e: blt.s IL_0004
IL_0010: ret
} // end of method Test::x

Best Regards
Leandro.

"Greg Ewing [MVP]" <gewing@_NO_SPAM_claritycon.com> wrote in message
news:uqtt0gakCHA.4120@tkmsftngp10...

[Eric Gunnerson [MS]]

Two questions:

1) Did you compile in release mode?
2) How did you look at the x86 code? If you have a debugger attached, JIT
will be in debug mode even if you compiled in release mode.

--
Visit the C# product team at http://www.gotdotnet.com/team/csharp

This posting is provided "AS IS" with no warranties, and confers no rights.

"Leandro Oliveira" <loli...@uolinc.com> wrote in message

news:uckESxakCHA.2432@tkmsftngp10...

[Leandro Oliveira]

1) Yes, I did.
2) I didn´t look the x86 code. The problem is: The program takes FOUR
SECONDS to run in release mode.

Best Regards.
Leandro.

"Eric Gunnerson [MS]" <eri...@online.microsoft.com> wrote in message
news:#85rqwekCHA.1784@tkmsftngp09...

[per larsen]

"Leandro Oliveira" <lea...@bol.com.br> wrote in message
news:#x5aAPkkCHA.1696@tkmsftngp12...

> 1) Yes, I did.
> 2) I didn´t look the x86 code. The problem is: The program takes FOUR
> SECONDS to run in release mode.

Confirmed. Unfortunately, current versions of both the C# compiler and
the JIT'er are lame as far as performance goes. Hopefully, it'll get
better in future releases.

- Per

[Eric Gunnerson [MS]]

The C# compiler doesn't do optimization (well, much, it does do a small
amount of dead code elimination), as the JIT handles optimization. That
means that looking at the IL isn't a good indication of how fast the
resulting program will be.

I did a comparison between the C# version of your program and a C++ version.
I had to modify the C++ version a bit, because in my initial version the C++
optimizer was able to get rid either all the loop, or all the calls after
the first call. Crafty optimizer.

I timed them both, and they both gave about 2.75 seconds. There was no
noticeable difference between the two in my timings using Visual Studio .NET
2002. I used /O2 for the C++ compile, and /optimize for the C# compile. This
was run on a 700 MHz PIII.

Here's the C# version:

using System;

public class Test
{
private static int x(int b)
{
int k = 0;

for (int i=0; i < b; i++)
{

k += i;
}
return k;
}
public static int Main(string[] arg)
{
DateTime start;

int j = 0;
int count = 1000000000;
for (int i = 0; i < 6; i++)
{
start = DateTime.Now;
j += x(count);
count++;
DateTime done = DateTime.Now;
Console.WriteLine("Done: {0}", done - start);
}
return j;
}
}

and the C++ version:

#include <stdio.h>

static int x(int b)
{
int k = 0;

for (int i=0; i < b; i++)
{

k += i;
}
return k;
}
static int main()
{
int j = 0;
int count = 1000000000;
for (int i = 0; i < 6; i++)
{
j += x(count);
count++;
printf("Done\n");
}
return j;
}

--
Visit the C# product team at http://www.gotdotnet.com/team/csharp

This posting is provided "AS IS" with no warranties, and confers no rights.

"Leandro Oliveira" <lea...@bol.com.br> wrote in message
news:#x5aAPkkCHA.1696@tkmsftngp12...

[per larsen]

Eric,

> The C# compiler doesn't do optimization

With add due respect, I don't think this is an entirely wise decision.
While I agree that the JIT compiler should be responsible for doing the
low-level optimizations that might exploit specific hardware quirks,
there are some kinds of high-level transformations that are both
complicated and relatively time consuming to do and are best done once
by the high-level compilers instead of every time the module is loaded
(if at all) by the JIT'er. Such optimizations would also cut down on the
size of images.

Obvious candidates I've seen over the last couple of days for simple
optimizations that could be done in the C# compiler are

- elimination of multiplications by literal 1,
- folding of multiple declaration of the 'same' local variable in a
method (same name and type),
- arithmetic strength reduction (replace x*2 with x+x, and so on) *
- loop induction variable detection
There any many others, I'm sure.

* these could also be done by the JIT'er, but the current one isn't very
good compared to contemporary optimizing compilers. E.g. it will convert
(uint) = (uint)*4 to (uint) = (uint) shl 2, but it will not convert
(uint) = (uint)*3 to (uint) = (uint) shl 1 + (uint).

High-level optimizations, like dead code elimination (as in the example
posted by Leandro) should definitely be optimized away by the high-level
compilers, IMHO. There's no point in distributing code and having it
JIT'ed by every user when it has no effect. Having the C# compiler
detect dead code would also let it emit a "code has no effect" warning.
Dead code is often a sign that something isn't quite right in the
source.

- Per

[Thomas Scheidegger [MVP] NETMaster]

IMHO:
It is a VERY wise decision to invest in the JIT optimizer first!

With every single improvement of JIT:

- the COMPLETE Framework gains speed.
- code from ALL languages runs faster.

Sure, compiler optimization could help, but it should
not have the highest priority.

And sometimes, it is fairly useful
if there is a near 1:1 match from a line of C# code
to a sequence of MSIL codes ...

--
Thomas Scheidegger - MVP .NET - 'NETMaster'
http://www.cetus-links.org/oo_dotnet.html - http://dnetmaster.net/

[Eric Gunnerson [MS]]

--
Visit the C# product team at http://www.gotdotnet.com/team/csharp

This posting is provided "AS IS" with no warranties, and confers no rights.

"per larsen" <perlATturbopowerDOTcom> wrote in message
news:O3bVqhukCHA.1988@tkmsftngp08...

> Eric,
>
> > The C# compiler doesn't do optimization
>
> With add due respect, I don't think this is an entirely wise decision.
> While I agree that the JIT compiler should be responsible for doing the
> low-level optimizations that might exploit specific hardware quirks,
> there are some kinds of high-level transformations that are both
> complicated and relatively time consuming to do and are best done once
> by the high-level compilers instead of every time the module is loaded
> (if at all) by the JIT'er. Such optimizations would also cut down on the
> size of images.

It's been a few years since I've been close to the optimization world, so my
opinions may be a bit dated.

As Thomas mentioned, localizing optimizations in the JIT means that all
languages benefit. That's a non-trivial benefit, especially since few
programmers are skilled both in parser construction and in optimization
strategies.

The second issue has to do with the format of the .NET IL. Because it's a
stack-based language, it doesn't present the same opportunities for
optimization at the compiler level as you have

>
> Obvious candidates I've seen over the last couple of days for simple
> optimizations that could be done in the C# compiler are
>
> - elimination of multiplications by literal 1,
> - folding of multiple declaration of the 'same' local variable in a
> method (same name and type),
> - arithmetic strength reduction (replace x*2 with x+x, and so on) *
> - loop induction variable detection
> There any many others, I'm sure.
>
> * these could also be done by the JIT'er, but the current one isn't very
> good compared to contemporary optimizing compilers. E.g. it will convert
> (uint) = (uint)*4 to (uint) = (uint) shl 2, but it will not convert
> (uint) = (uint)*3 to (uint) = (uint) shl 1 + (uint).

The current JIT is tuned to do a reasonably good job of optimization within
the time constraints that it has. If you want more optimization, you'll need
to spend more, which requires a scheme that identifies hot spots in code (so
you don't waste time optimizing all the code) and/or a fast way to say the
optimized code to disk (given current disk/cpu speed ratios, this isn't
always a win).

> High-level optimizations, like dead code elimination (as in the example
> posted by Leandro) should definitely be optimized away by the high-level
> compilers, IMHO. There's no point in distributing code and having it
> JIT'ed by every user when it has no effect. Having the C# compiler
> detect dead code would also let it emit a "code has no effect" warning.
> Dead code is often a sign that something isn't quite right in the
> source.

C# does do some dead code identification now, but it doesn't catch all
cases. I think it's a resource tradeoff question. Time spent doing more dead
code identification is time not spent coding new features, tuning the
compiler for smaller memory footprint or higher throughput, etc.

[per larsen]

"Thomas Scheidegger [MVP] NETMaster" <spam.ne...@swissonline.ch>
wrote in message news:OjoLWYxkCHA.4120@tkmsftngp10...

> IMHO:
> It is a VERY wise decision to invest in the JIT optimizer first!

No argument there.

- Per

[per larsen]

> As Thomas mentioned, localizing optimizations in the JIT means that
all
> languages benefit. That's a non-trivial benefit, especially since few
> programmers are skilled both in parser construction and in
optimization
> strategies.

True, but the current JIT'er clearly favors compilation speed over
target code efficiency. Of course, that makes a lot of sense. Having the
JIT'er produce code which is even close to the theoretical optimum is
unrealistic, IMHO. Attempting that could easily increase the JIT time by
orders of magnitude, and load times are already way above native apps.

Hopefully, we'll get some kind of highly optimizing NGen in a not too
distant future - one that doesn't suffer from the limitations of the
current NGen (e.g. lack of cross-module inline expansion).

- Per

[Leandro Oliveira]

While in java...

public class Test
{
public static void x(int b)

{
for (int i=0; i < b; i++)
{
int a = 0;
}
}

public static void main(String arg[])
{
long t;
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
t = System.currentTimeMillis();
x(Integer.parseInt(arg[0]));
System.out.println((System.currentTimeMillis() - t));
}
}

$ java Test 1000000000

Results using Blackdown 1.3:
4373
4373
2385 <- NOTE THIS!
2385 <- NOTE THIS!
2385 <- NOTE THIS!
2385 <- NOTE THIS!

using Sun JDK 1.3:
4373
4373
2385 <- NOTE THIS!
2385 <- NOTE THIS!
2385 <- NOTE THIS!
2385 <- NOTE THIS!

[ ]s
Leandro.

"per larsen" <perlATturbopowerDOTcom> wrote in message

news:uwCHmbkkCHA.2548@tkmsftngp11...

[Thomas Scheidegger [MVP] NETMaster]

I just checked the generated x86 code of x(b) :

for (int i=0; i < b; i++)
{
int a = 0;

a = a;
}

and I see:

Main():
.........
00000067 mov ecx,3B9ACA00h ;1000000000
0000006c call x()
.........

void x( b ) :
00000000 xor eax,eax ; i = 0
00000002 cmp ecx,0 ; b <= 0 ?
00000005 jle 0000000C ; no loop

00000007 inc eax ; i++ -------
00000008 cmp eax,ecx ; i < b
0000000a jl 00000007 ; for -------^

0000000c ret

So the JIT does eliminate the dead code {int a=0;a=a} inside the loop,
but the (empty!) loop itself is executed with 3 assembler OP-codes:
increment, compare, conditional-branch.

Maybe this sequence would be faster with e.g. the pentium 'LOOP' op-code?

With a billion loops this could need 'some' seconds,
if you don't have a 3GHz P4.
I have a PIII/933 and it needs 2.2 seconds.

Thus the only question is:

Should the JIT optimizer remove EMPTY loops?

As the programmer wrote one, this could be debatable...

[Leandro Oliveira]

> Thus the only question is:
>
> Should the JIT optimizer remove EMPTY loops?

Yes, visual C++ compiler does it.

Best Regards.
Leandro.

"Thomas Scheidegger [MVP] NETMaster" <spam.ne...@swissonline.ch> wrote

in message news:uuz575KlCHA.2260@tkmsftngp12...

[per larsen]

"Thomas Scheidegger [MVP] NETMaster" <spam.ne...@swissonline.ch>
wrote in message news:uuz575KlCHA.2260@tkmsftngp12...

...

> Thus the only question is:
>
> Should the JIT optimizer remove EMPTY loops?
>
> As the programmer wrote one, this could be debatable...

True, but since the programmer /probably/ meant for the loop to do some
actual work, the ideal, IMHO, would be for the C# compiler to emit a
warning. Something the JIT'er has no opportunity to do (AFAIK).

- Per