Why is C# much slower than Java and C++ in my prime number testing [closed]

Question

(bear with me, there's a lot of explanation before my question)

As a few of you may be aware over the last few days I have posted a fair few questions relating to performance of C++. Being a Java programmer I wanted to know was C++ worth the extra effort to specialise in, or is Java good enough for performance programming.

Anyway, I decided to write a basic (non-efficient algorithm) prime numbers program- no object creation, and to see how the 3 language compared time-wise. I wont post the code up, only for the reason that the code was exactly the same in the algorithm (except I used int instead of boolean in C++). Only the code for timing differed (and this was obviously outside the algorithm).

In summary, to calculate the first 10000 prime numbers and looped this 40 times (to exaggerate differences in speed) it took:

Java: 190.5 seconds

C++: 189 seconds

C#: 242 seconds

To calculate the first 100000 primes (one run) it took:

Java: 591 seconds

C++: 588 seconds

C#: 771 seconds

So my question, why is C# much slower than the other 2? I thought Java and C# would be very close timings. Here is the C# algorithm (I am aware there are quicker ways of finding prime numbers):

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 stopwatch. Datetime is not reliable for code timing.

Second, are you sure you are executing it in release mode with visual studio closed? If visual studio is open or you are launching with F5 the JIT will not optimize the code!

So... use stopwatch and close all instances of visual studio. You have to change project options, you should have a combobox, in the top toolbar, where you can read "Debug", just click on it and select "Release" or go to right click on your project, properties, and change it to release mode. Then to avoid every kind of problems, close all instances of visual studio and launch with double click on the executable.

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

CTRL+F5 don't compile in release mode, it just launch the executable in selected compilation mode without attacching the process for debugging, so if it was compiled in debug, it will launch the executable compiled in debug mode without debugging it.

Then i would suggest to you to avoid the use of the boolean variable, each branch condition can slow down the CPU, you can do it using an integer. This is valid for all languages, not only 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 however since input parameters are constants C++ compiler is smart enough to perform some of the computation at compile time (the power of modern C++ compilers!). This magic is usually used with templates too, STL (standard template library) for example is very, very slow in debug mode but very fast in release mode.

In this case the compiler is totally ruling out your function because the output of your function is not used. Try to make it return an integer, the number of found primes, 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, take a look at the template metaprogramming for example, there exists a formal proof that C++ compiler is turing complete. As wikipedia quotes "In addition, templates are a compile time mechanism in C++ that is Turing-complete, meaning that any computation expressible by a computer program can be computed, in some form, by a template metaprogram prior to runtime." http://en.wikipedia.org/wiki/C%2B%2B

However I really hope you are using this algorithm only to try to understand how the three different compilers\systems behave, because, of course, this is the worst algorithm you can use to find prime numbers, as pointed out in other answers :)