JIT & loop optimization

Question

using System; 

namespace ConsoleApplication1
{ 
    class TestMath
    {  
        static void Main()
        {
            double res = 0.0;

            for(int i =0;i<1000000;++i)
                res +=  System.Math.Sqrt(2.0);

            Console.WriteLine(res);

            Console.ReadKey();  
        }
    }
}

By benchmarking this code against the c++ version, I discover than performance are 10 times slower than c++ version. I have no problem with that , but that lead me to the following question :

It seems (after a few search) that JIT compiler can't optimize this code as c++ compiler can do, namely just call sqrt once and apply *1000000 on it.

Is there a way to force JIT to do it ?

Answer 1

I repro, I clock the C++ version at 1.2 msec, the C# version at 12.2 msec. The reason is readily visible if you take a look at the machine code the C++ code generator and optimizer emits. It rewrites the loop like this (using the C# equivalent):

double temp = Math.Sqrt(2.0);
for (int i = 0; i < 1000000; ++i) {
    res += temp;
}

That's a combination of two optimizations, called "invariant code motion" and "loop hoisting". In other words, the C++ compiler knows enough about the sqrt() function to know that its return value is not affected by the surrounding code so can be moved at will. And that it is then worth-while to move that code outside of the loop and create an extra local variable to store the result. And that calculating sqrt() is slower than adding. Sounds obvious but that's a rule that has to built into the optimizer and has to be considered, one of many, many rules.

And yes, the jitter optimizer misses that one. It is guilty of not being able to spent the same amount of time as the C++ optimizer, it operates under heavy time constraints. Because if it takes too long then the program takes too much time getting started.

Tongue in cheek: a C# programmer needs to be a bit smarter than the code generator and recognize these optimization opportunities himself. This is a fairly obvious one. Well, now that you know about it anyway :)

Answer 2

To do the optimization you want, the compiler has to assure that the function Sqrt() will always return the same value for a certain input.

The compiler can do all kinds of checks that the function isn't using any other "outer" variables to see if it's stateless. But that also doesn't always mean that it can't be affected by side affects.

When a function is called in a loop it should be called in each iteration (think of a multithreaded environment to see why this is important). So usually it's up to the user to take constant stuff out of the loop if he wants that kind of optimization.

Back to the C++ compiler - the compiler might have certain optimization for its library functions. A lot of compilers try to optimize important libraries like the math library, so that might be compiler specific.

Another big difference is in C++ you usually include that kinda stuff from a header file. This means the compiler may have all the information it needs to decide if the function call doesn't change between calls.

The .Net compiler (at compile time - Visual Studio) doesn't always have all the code to parse. Most of the library functions are already compiled (into IL - first stage). And so might not be able to do deep optimizations considering 3rd party dlls. And at the JIT (runtime) compilation it will probably be too costly to do these kind of optimizations across assemblies.

Answer 3

It might help the JIT (or even the C# compiler) if Math.Sqrt was annotated as [Pure]. Then, assuming the arguments to the function are constant as they are in your example, the calculation of the value could be lifted outside the loop.

What's more, such a loop could reasonably be converted into the code:

double res = 1000000 * Math.Sqrt(2.0);

In theory the compiler or JIT could perform this automatically. However I suspect that it would be optimising for a pattern that happens rarely in actual code.

I opened a feature request for ReSharper, suggesting that the design-time tool suggests such a refactoring.