Why is a Fibonacci faster in Java than in C?

Question

Not exactly like this, but I noticed that when the function needs more time to compute Fibonacci, Java actually does better than C.

Here are the implementations:

C:

#include<stdio.h>

unsigned long fibo(long num) {
    if(num == 1 || num == 2)
        return 1;
    else
        return fibo(num - 1) + fibo(num - 2);
}

int main(int argc, char *argv[]) {
    int num = atoi(argv[1]);
    long result = fibo(num);
    printf("Result: %ld\n", result);
    return 0;
}

The C version was compiled with GCC 4.8.2 on Ubuntu Linux.

Java:

public class Fibonacci {
    static long fibo(long num) {
        if(num == 1 || num == 2)
             return 1;
        else
             return fibo(num - 1) + (num - 2);
    }

    public static void main(String[] args) {
        long num = Long.parseLong(args[0]);
        long result = fibo(num);
        System.out.println("Result: " + result);
    }
}

The Java version was compiled with JDK 8.

Fibonaci de 10:

Java = 0.048 seconds

C = 0,000 seconds (virtually nothing)

---

Fibonaci de 30.

Java = 0.180 seconds

C = 0.064 seconds

---

So far, no big deal.

Java = 38.006 seconds

C = 42.471 seconds

Java was 4 seconds faster than C. Which is at least sinister coming from a language that runs on a VM.

How such a thing is possible?

Answer 1

Real problem

The algorithms are completely different. So the more you run it the worse.

In C is calling

fibo(num - 1) + fibo(num - 2)

In Java is

fibo(num - 1) + (num - 2)

The first calls the same function twice. The second only calls one. In Java it doesn’t even give the right result. Therefore it is much worse than in C. Before an algorithm is faster it needs to be correct.

VM + Jitter X traditional compilation

Running on VM does not mean that the code is interpreted. On the contrary, it means that the code can be optimized quite aggressively at the time of execution. Through the Jitter it is possible to produce the best native code for that specific situation, for that specific platform. To be possible does not mean that it actually happens.

Java may be using some technique of memoization.

In C the compiler uses the lowest common denominator to be able to run anywhere. With little execution you may even be having a big time to execute the compilation just in time. As the execution of the algorithm becomes predominant this time pass be derisory.

Benchmark

You have not passed data that can be evaluated well.

• Information as compiled is missing. This can make a huge difference in C which is a language that the programmer needs to tell you how to do everything. It has tools to achieve maximum speed but if you do not use them correctly, the opposite may occur. There is a good chance that Java has transformed the recursive code into a repeat loop and that this did not occur in C. This makes a huge difference. This is probably the best explanation for there being a difference in this direction. Furthermore, Jitter can be more aggressive when it detects that the code is too executed. There are cases where maximum optimization in C worsens the result, so the compiler does not decide alone.

• You have not shown the environment in which this is running. This may possibly explain part of the difference in conjunction with other factors.

• We don’t know how time was measured. You may have used a wrong method. May have had external interference, may not have performed enough attempts to get a reliable result, may not have used something accurate to measure.

• We don’t even know how many numbers were tried in the last test. And we don’t know if something bigger would produce the same ratio.

Isn’t it weird that the C goes from 0 to 64 ms only tripling the execution? It’s strange that Java has more than tripled the time when it triples the exposure. The most normal is to have a reduction. These numbers make no sense even with the logical explanations. There may be an explanation as to why this is happening, but at the moment I can only say that I don’t know everything to assess whether it is correct. Surely there are extra factors hindering the evaluation.

One possible explanation is the use of Casts implicit. I did not test, but this confusion of calling the first time a int (this should not cause much trouble) and the others call with unsigned long something that awaits long as reentrant parameter can affect something as well. That is, the algorithms are not exactly equal.

Speculation

As much as it may seem that the code is the same you are not necessarily comparing it fairly. One language can perform better than another a code that fits like a glove to it and not as well in another. It is common for algorithms to have to be modified in another language to get the best result. This is just speculation, I’m not saying it’s the case, but it’s a possibility.

It doesn’t seem to be the case, but memory allocations can make a difference as well. As amazing as Garbage Collector can make a program get faster than another one with manually managed memory. Just the programmer does not know how to make the most of it. Manual management can be the fastest strategy. But only when you do it the right way. This can make a tremendous difference in many cases. Contrary to popular belief, GC often allocates memory more efficiently than individualized allocation. And many do not realize that there is no displacement until it is necessary to reclaim memory. GC is bad when it pauses the application to do the cleaning.

Nor does it seem to be the case, but there are cases that the actual execution performed by libraries written in C/C++, or even Assembly, by a very experienced programmer in that domain who will produce better code than yours. In the past I have seen in a website well-known of (bechmark a Java code that ran absurdly faster than the same code in C. Only the Java code called a library written in Assembly to do 99% of the work. So the comparison was C against Assembly and not Java.

In some cases a very small change like the reversal of the logic of a if can dramatically change to more or less in one language. And the opposite may occur in another. In this example the operator’s use or may not be the best option for one of them. In other cases the use of the if (branch is usually a very expensive operation in the processor) can be eliminated and make more difference in one language than another.

Completion

Read more about the java optimizations.

See how optimizations make a huge difference in C. And mainly note that the result of this test is not similar to yours, even if the code is essentially the same.

When testing, run multiple times, eliminate the best and worst results, average. Make sure that nothing on the machine can disrupt the test run. Use machine time measurement and not the clock. And remember to test things that don’t take almost anything to figure out which one is faster doesn’t help much. Everything that’s already fast enough doesn’t need to be fast enough.

Try testing with various levels of C optimization. Try forcing the inline function in C. Try turning off the check from the stack, it is easier to give security without checking, constant when the compiler knows when it is running and C doesn’t have that chance.

One thing this also shows is that I always talk. Recursion is overrated. Try getting the same result with a repetition algorithm.

Also try to do a pre-calculation in both cases. You can mount a table of lookup and get the results ready instead of calculating. You exchange a little extra memory consumption for better run time.

Answer 2

Java has an intelligent compiler called JIT, this compiler 'guesses' patterns in code and optimizes processes, in Fibonacci for example, is the same pattern in each for and if, compiler understands this and optimizes code.

Already in the c there is no intelligence, it is all bit by bit, so it depends on the processor and not the compiler