Why is C # much slower than Java and C ++ when testing prime numbers

Question

(bear with me, there are many explanations in front of my question)

As some of you may be aware of over the past few days, I have posted several questions regarding C ++ performance. As a Java programmer, I wanted to know that C ++ is worth the extra effort for specialization, or Java is good enough for programming performance.

In any case, I decided to write a basic (inefficient algorithm) program of primes - creating an object and see how 3 languages ​​compare in time. I will not put the code up, just for the reason that the code was exactly the same in the algorithm (except that I used int instead of boolean in C ++). Only the code for synchronization was different (and this, obviously, outside the algorithm).

So, to calculate the first 10,000 primes and loop it 40 times (to exaggerate the differences in speed), it took:

Java: 190.5 seconds

C ++: 189 seconds

C #: 242 seconds

To calculate the first 100,000 primes (one run) it took:

Java: 591 seconds

C ++: 588 seconds

C #: 771 seconds

So my question is, why is C # much slower than the other 2? I thought Java and C # would be very close. Here is the C # algorithm (I know there are faster ways to search for primes):

static void Main(string[] args) { int NumberOfPrimesToFind = 100000; int NumberOfRuns = 1; DateTime start = DateTime.Now; for (int k = 0; k < NumberOfRuns; k++) { FindPrimes(NumberOfPrimesToFind); } DateTime finish = DateTime.Now; Console.Out.WriteLine(finish-start); Console.In.Read(); } static void FindPrimes(int NumberOfPrimesToFind) { int NumberOfPrimes = 0; int CurrentPossible = 2; Boolean IsPrime ; while (NumberOfPrimes < NumberOfPrimesToFind) { IsPrime = true; for (int j = 2; j < CurrentPossible; j++) { if (CurrentPossible % j == 0) { IsPrime = false; break; } } if (IsPrime) { NumberOfPrimes++; } CurrentPossible++; } } 

C ++

 int main() { int NumberOfPrimesToFind = 100000; int NumberOfRuns = 1; int temp; double dif; time_t start,end; time (&start); for (int k = 0; k < NumberOfRuns; k++) { FindPrimes(NumberOfPrimesToFind); } time (&end); //Number of seconds dif = difftime (end,start); cout << (dif); cin >> temp; } void FindPrimes(int NumberOfPrimesToFind) { int NumberOfPrimes = 0; int CurrentPossible = 2; int IsPrime ; while (NumberOfPrimes < NumberOfPrimesToFind) { IsPrime = 1; for (int j = 2; j < CurrentPossible; j++) { if (CurrentPossible % j == 0) { IsPrime = 0; break; } } if (IsPrime==1) { NumberOfPrimes++; } CurrentPossible++; } } 

Java:

 public static void main(String[] args) { int NumberOfPrimesToFind = 100000; int NumberOfRuns = 1; long start = System.currentTimeMillis(); for (int k = 0; k < NumberOfRuns; k++) { FindPrimes(NumberOfPrimesToFind); } long finish = System.currentTimeMillis(); System.out.println((finish-start)); } static void FindPrimes(int NumberOfPrimesToFind) { int NumberOfPrimes = 0; int CurrentPossible = 2; Boolean IsPrime ; while (NumberOfPrimes < NumberOfPrimesToFind) { IsPrime = true; for (int j = 2; j < CurrentPossible; j++) { if (CurrentPossible % j == 0) { IsPrime = false; break; } } if (IsPrime) { NumberOfPrimes++; } CurrentPossible++; } } 

Answer 1

About C #:

First of all, instead of datetime you should use a stopwatch. Datetime is not reliable for code synchronization.

Secondly, are you sure that you are performing it in release mode with a closed visual studio? If the visual studio is open or you start with F5, JIT will not optimize the code!

So ... use a stopwatch and close all instances of the visual studio. You have to change the project parameters, you have to have a combobox, on the top toolbar where you can read “Debug”, just click on it and select “Release” or go to the right click on your project, properties and change it to release. Then, to avoid any problems, close all instances of the visual studio and double-click on the executable file.

See http://msdn.microsoft.com/en-us/library/wx0123s5.aspx

CTRL + F5 does not compile in release mode, it simply launches the executable file in the selected compilation mode without attracting the debugging process, so if it was compiled in debugging, it will run the executable compiled in debugging mode without debugging.

Then I would suggest that you avoid using a boolean variable, each branch condition can slow down the processor, you can do this using an integer. This is valid for all languages, not just C #.

 static void Main() { const int NumberOfPrimesToFind = 100000; const int NumberOfRuns = 1; System.Diagnostic.Stopwatch sw = new System.Diagnostic.Stopwatch(); sw.Start(); for (int k = 0; k < NumberOfRuns; k++) { FindPrimes(NumberOfPrimesToFind); } sw.Stop(); Console.WriteLine(sw.Elapsed.TotalMilliseconds); Console.ReadLine(); } static void FindPrimes(int NumberOfPrimesToFind) { int NumberOfPrimes = 0; int CurrentPossible = 2; while (NumberOfPrimes < NumberOfPrimesToFind) { int IsPrime = 1; for (int j = 2; j < CurrentPossible; j++) { if (CurrentPossible % j == 0) { IsPrime = 0; break; } } NumberOfPrimes += IsPrime; CurrentPossible++; } } 

When you compile it with C ++ in release mode, since the input parameters are constants, the C ++ compiler is smart enough to perform some calculations at compile time (the power of modern C ++ compilers!). This magic is commonly used with templates, for example, STL (standard template library) is very slow in debug mode, but very fast in release mode.

In this case, the compiler completely excludes your function, because the output of your function is not used. Try to return an integer, the number of primes found and print it.

 int FindPrimes(int NumberOfPrimesToFind) { int NumberOfPrimes = 0; int CurrentPossible = 2; while (NumberOfPrimes < NumberOfPrimesToFind) { int IsPrime = 1; for (int j = 2; j < CurrentPossible; j++) { if (CurrentPossible % j == 0) { IsPrime = 0; break; } } NumberOfPrimes += IsPrime; CurrentPossible++; } return NumberOfPrimes ; } 

If you are curious about this aspect of the C ++ compiler, look, for example, at metaprogramming a template, there is formal evidence that the C ++ compiler is complete. As the Wikipedia quote quotes, “In addition, templates are a C ++ compile-time mechanism that completes Turing, which means that any computation expressed by a computer program can be computed in some form by a template metaphone before runtime.” http://en.wikipedia.org/wiki/C%2B%2B

However, I really hope that you use this algorithm only to understand how three different compilers / systems behave, because, of course, this is the worst algorithm that you can use to search for prime numbers, as indicated in other answers :)

Answer 2

The C ++ and C # algorithms seem extremely similar, if not identical. Since there is no obvious difference in code that takes performance into account, I would suggest that there may be differences in locality or optimizer. The only way to know for sure is to profile two different versions and see where they work in different ways.

Answer 3

When comparing languages, you should first try to optimize the code. Otherwise, you can compare how well it executes inefficient code, which may not be very significant. For example, in all the tests I saw where Java is superior to C ++ significantly, these are the ones that do not bring anything useful .;)

For a longer test that searches for 100,000 primes in 40 runs.

 public static void main(String... args) { int numberOfPrimesToFind = 100000; int numberOfRuns = 40; long start = System.currentTimeMillis(); for (int k = 0; k < numberOfRuns; k++) findPrimes(numberOfPrimesToFind); long finish = System.currentTimeMillis() - start; System.out.printf("Took %.2f seconds to loop %,d times%n", finish/1e3, numberOfRuns); } static void findPrimes(int numberOfPrimesToFind) { int numberOfPrimes = 0; int currentPossible = 2; while (numberOfPrimes < numberOfPrimesToFind) { boolean isPrime = isPrime(currentPossible); if (isPrime) { numberOfPrimes++; } currentPossible++; } } private static boolean isPrime(int currentPossible) { if ((currentPossible & 1) == 0) return false; for (int j = 3; j * j <= currentPossible; j += 2) if (currentPossible % j == 0) return false; return true; } 

prints

 Took 9.26 seconds to loop 40 times 

The moral of the story is that the algorithm you use is often more important than the language you use.