Java vs C Runtime (REPOST)

Question

I just wrote a program that finds all the prime numbers with an upper bound.

The algorithm: Sieve of Eratosthenes.

Wrote it both in C and Java. The upper bound is 666014.

For some reason C gives the result in more than 2.5 seconds, while Java does it in like half a second.

Details:

The array in C is of type char
The array in Java is of type boolean

C IDE: CodeBlocks

Java IDE: IntellijIdea Community Edition

C code:

#include <stdio.h>

int main() {

    int n = 666013;
    int i;
    int k;

    char a[n];

    for (i = 2; i <= n; i++)
        a[i] = 0;

    for (i = 2; i <= n; i++)
         if ( a[i] == 0 )
         {
            printf("%d\n", i);
            for (k = i + i; k <= n; k += i)
                 a[k] = 1;
         }

    return 0;

}

Java code:

package primes;

public class Prime {

    public static void main(String[] args) {
        long starttime = System.nanoTime();
        final int MAXN = 666013;
        boolean a[] = new boolean[MAXN];

        for (int i = 2; i < a.length; i++)
            a[i] = true;

        for (int i = 2; i < a.length; i++)
            if (a[i])
            {
                System.out.println(i);
                System.out.printf("");
                for (int j = i + i; j < a.length; j += i) {
                    a[j] = false;
                }
            }

        System.out.println(System.nanoTime() - starttime);

    }
}

Last Edit: used System.nanoTime() Java gives 0.35 seconds

The C algorithm cannot be any faster. What is the reason Java is faster here?

Also, which optimization flags for the C compiler are you using? — ArthurChamz, Sep 03 '14 at 17:57
By the way, I think the ranges in the for loops for the C program are wrong by 1. They should be ` — ArthurChamz, Sep 03 '14 at 18:00
Do not repost questions. If your original question was placed on hold, edit the original to fix the original. — Raedwald, Sep 03 '14 at 18:08
I tried your code without output (> to file). C program works in milliseconds. — Ivan Ivanov, Sep 03 '14 at 18:10
remove the IO completely, and use a zero-initialized static array, and the runtime of the actual computation drops below the resolution of `GetSystemTimeAsFileTime()` on my Windows box — Christoph, Sep 03 '14 at 18:17

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

A few thoughts:

1. Compiler optimization

The C algorithm cannot be any faster.

The algorithm may not be something you can improve, but there are a lot of implementation details that can make this go faster. For example, Loop Unrolling could drastically reduce the number of branches that the CPU has to perform. Depending on the compiler flags that you have set, it's likely that the C compiler is not optimizing your code as well as the Java compiler/JIT are.

2. Benchmarking techniques

You're including I/O operations as part of your "algorithm." In fact, you're writing 54000+ lines of I/O. I/O takes orders of magnitude longer than calculations and memory operations do, so time spent in I/O is likely to be outweighing the actual duration of your algorithm. If the Java framework is even slightly faster than C's printf, it could easily account for a drastic difference in the performance of these programs.

Remove the output step from the part of the code that you're trying to measure performance for, and see what happens.

Also, I don't see any benchmarking code in your C example. Are you measuring the time it takes for the program to load into memory and start up, whereas the Java example is only measuring the time it takes to run through your code after start up?

score 0 · Accepted Answer · edited May 23 '17 at 12:12

0

The reason is probably the printf call which is not buffered by default. Have a look at this question. Also when the console is shown everything might be slowed up.

Try running the two programs without any output call and you will probably get similar results.

edited May 23 '17 at 12:12

Community

1
1

answered Sep 03 '14 at 18:10

ForguesR

3,443
1
15
36

Java vs C Runtime (REPOST)

2 Answers2

1. Compiler optimization

2. Benchmarking techniques