Why is this Java code 6x faster than the identical C# code?

Question

I have a few different solutions to Project Euler problem 5, but the execution time difference between the two languages/platforms in this particular implementation intrigues me. I didn't do any optimization with compiler flags, just plain javac (via commandline) and csc (via Visual Studio).

Here's the Java code. It finishes in 55ms.

public class Problem005b
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        int i = 20;
        while (true)
        {
            if (
                    (i % 19 == 0) &&
                    (i % 18 == 0) &&
                    (i % 17 == 0) &&
                    (i % 16 == 0) &&
                    (i % 15 == 0) &&
                    (i % 14 == 0) &&
                    (i % 13 == 0) &&
                    (i % 12 == 0) &&
                    (i % 11 == 0)
                )
            {
                break;
            }
            i += 20;
        }
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(end-begin + "ms");
    }   
}

Here is the identical C# code. It finishes in 320ms

using System;

namespace ProjectEuler05
{
    class Problem005
    {
        static void Main(String[] args)
        {
            DateTime begin = DateTime.Now;
            int i = 20;
            while (true)
            {
                if (
                        (i % 19 == 0) &&
                        (i % 18 == 0) &&
                        (i % 17 == 0) &&
                        (i % 16 == 0) &&
                        (i % 15 == 0) &&
                        (i % 14 == 0) &&
                        (i % 13 == 0) &&
                        (i % 12 == 0) &&
                        (i % 11 == 0)
                    )
                    {
                        break;
                    }
                i += 20;
            }
            DateTime end = DateTime.Now;
            TimeSpan elapsed = end - begin;
            Console.WriteLine(i);
            Console.WriteLine(elapsed.TotalMilliseconds + "ms");
        }
    }
}

Answer 1

1. To time code execution, you should use the StopWatch class.
2. Also, you have to account for the JIT, the runtime etc, so let the test run a sufficient amount of times (like 10,000, 100,000 times) and get some sort of average. It is important to run the code multiple times, not the program. So write a method, and loop in the main method to get your measurements.
3. remove all debugging stuff from the assemblies and let the code run stand-alone in a release build

Answer 2

There are a few optimizations possible. Maybe the Java JIT is performing them and the CLR is not.

Optimization #1:

(x % a == 0) && (x % b == 0) && ... && (x % z == 0)

is equivalent to

(x % lcm(a, b, ... z) == 0)

So in your example the comparison chain could be replaced by

if (i % 232792560 == 0) break;

(but of course if you've already calculated the LCM, there's little point in running the program in the first place!)

Optimization #2:

This is also equivalent:

if (i % (14549535 * 16)) == 0 break;

or

if ((i % 16 == 0) && (i % 14549535 == 0)) break;

The first division can be replaced with a mask and compare against zero:

if (((i & 15) == 0) && (i % 14549535 == 0)) break;

The second division can be replaced by a multiplication by the modular inverse:

final long LCM = 14549535;
final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64
final long MAX_QUOTIENT = Long.MAX_VALUE / LCM;
// ...
if (((i & 15) == 0) &&
    (0 <= (i>>4) * INV_LCM) &&
    ((i>>4) * INV_LCM < MAX_QUOTIENT)) {
    break;
}

It is somewhat unlikely that the JIT is employing this, but it is not as far-fetched as you might think - some C compilers implement pointer subtraction this way.

Answer 3

The key to making these two become closer is to ensure that the comparison is fair.

First of all ensuring that costs associated with running Debug builds, loading pdb symbols as you did.

Next you need to ensure that there are no init costs being counted. Obviously these are real costs, and may matter to some people, but in this instance we are interested in the loop itself.

Next you need to deal with the platform specific behaviour. If you are on a 64bit windows machine you may be running either in 32bit or 64bit mode. In 64bit mode the JIT is different in many respects, often altering the resulting code considerably. Specifically, and I would guess pertinently, you get access to twice as many general purpose registers.

In this case the inner section of the loop, when naively translated into machine code, would need to load into registers the constants used in the modulo tests. If there are insufficient to hold everything needed in the loop then it must push them in from memory. Even coming from level1 cache this would be a significant hit compared to keeping it all in registers.

In VS 2010 MS changed the default target from anycpu to x86. I have nothing like the resources or customer facing knowledge of MSFT so I won't try to second guess that. However anyone looking at anything like the performance analysis you are doing should certainly try both.

Once those disparities are ironed out the numbers seem far more reasonable. Any further differences likely require better than educated guesses, instead they would need investigation into the actual differences in the generated machine code.

There are several things about this I think would be interesting for an optimising compiler.

• The ones finnw already mentioned:
  • The lcm option interesting but I can't see a compiler writer bothering.
  • the reduction of division to multiplication and masking.
    • I don't know enough about this, but other people have tried note that they call out the divider on the more recent intel chips significantly better.
    • Perhaps you could even arrange something complex, with SSE2.
    • Certainly the modulo 16 operation is ripe for conversion into a mask or shift.
  • A compiler could spot that none of the tests have side effects.
    • it could speculatively try to evaluate several of them at once, on a super scalar processor this could pump things along quite a bit faster, but would depend heavily on how well the compilers layout interacted with the OO execution engine.
  • If register pressure was tight you could implement the constants as a single variable, set at the start of each loop then increment as you go along.

These are all utter guesses, and should be viewed as the idle meanderings. If you want to know disassemble it.

Answer 4

(Moved from OP)

Changing the target from x86 to anycpu has lowered the average execution time to 84ms per run, down from 282ms. Maybe I should split this off into a second thread?

UPDATE:
Thanks to Femaref below who pointed out some testing problems, and indeed, after following his suggestions, the times are lower, indicating that VM setup time was significant in Java, but probably not in C#. In C#, it was the debug symbols that were significant.

I updated my code to run each loop 10,000 times, and only output the average ms at the end. The only significant change I made was to the C# version where I switched to the [StopWatch class][3] for greater resolution. I stuck with milliseconds because it's good enough.

Results:
The testing changes don't explain why Java is (still) so much faster than C#. C# performance was better, but this can be explained entirely by removing the debug symbols. If you read [Mike Two][4] and I's exchange on the comments attached to this OP, you'll see I got ~280ms average in five runs of the C# code just by switching from Debug to Release.

Numbers:

• A 10,000 count loop of the unmodified Java code gave me an average of 45ms (down from 55ms)
• A 10,000 count loop of the C# code using the StopWatch class gave me an average of 282ms (down from 320ms)

All of this leaves the difference unexplained. In fact, the differential got worse. Java went from being ~5.8x faster to ~6.2x faster.

Answer 5

This is too short a task to do proper timing for. You need to run both at least 1000 times and see what happens. It kind of looks like you're running these from a command line, in which case you're possibly comparing the JIT compilers for both. Try putting both behind buttons in a simple GUI and have that button loop over this a few hundred times at least before returning the elapsed time. Even ignoring JIT compiling, the timing could be thrown off by the granularity of the OS scheduler.

Oh, and because of JIT... only count the SECOND result of a button press. :)

Answer 6

Perhaps because the construction of the DateTimeobjects is much more expensive than the System.currentTimeMillis.

Answer 7

In Java I would use System.nanoTime(). Any test which takes less than 2 seconds should be run for longer. It is worth noting that Java is pretty good at optimising inefficient code or code which does nothing. A more interesting test would be if you optimised the code.

You are trying to get a solution which you can determine without using a loop. i.e. a problem which would be done better another way.

You want the product of the factors of 11 to 20, which are 2,2,2,2,3,3,5,7,11,13,17,19. Multiply these together and you have the answer.