Comparing c and java programs runtime

I had a job interview today, we were given a programming question, and were asked to solve it using c/c++/Java, I solved it in java and its runtime was 3 sec (the test was more 16000 lines, and the person accompanying us said the running time was reasonable), another person there solved i开发者_如何学编程t in c and the runtime was 0.25 sec, so I was wondering, is a factor of 12 normal?

Edit: As I said, I don't think there was really much room for algorithm variation except maybe in one little thing, anyway, there was this protocol that we had to implement: A (client) and B (server) communicate according to some protocol p, before the messages are delivered their validity is checked, the protocol is defined by its state and the text messages that can be sent when it is in a certain state, in all states there was only one valid message that could be sent, except in one state where there was like 10 messages that can be sent, there are 5 states and the states transition is defined by the protocol too. so what I did with the state from which 10 different messages can be sent was storing their string value in an ArrayList container, then when I needed to check the message validity in the corresponding state i checked if arrayList.contains(sentMessageStr); I would think that this operation's complexity is O(n) although I think java has some built-in optimization for this operation, although now that I am thinking about it, maybe I should've used a HashSet container.I suppose the c implementation would have been storing those predefined legal strings lexicographically in an array and implementing a binary search function.

thanks

I would guess that it's likely the jvm took a significant portion of that 3 seconds just to load. Try running your java version on the same machine 5 times in a row. Or try running both on a dataset 500 times as large. I suspect you'll see a significant constant latency for the Java version that will become insignificant when runtimes go into the minutes.

Sounds more like a case of insufficient samples and unequal implementations (and possibly unequal test beds).

One of the first rules in measurement is to establish enough samples and obtain the mean of the samples for comparison. Even a couple of runs of the same program is not sufficient. You need to tax the machine enough to obtain samples whose values can be compared. That's why test-beds need to be warmed up, so that there are little or no variables at play, except for the system under observation.

And of course, you also have different people implementing the same requirement/algorithm in different manners. It counts. Period. Unless the algorithm implementations have been "normalized", obtaining samples and comparing them are the same as comparing apples and watermelons.

I don't think I need to expand on the fact that the testbeds could have been of varying configurations, or under varying loads.

It's almost impossible to say without seeing the code - you may have a better algorithm for example that scales up much better for larger input but has a greater overhead for small input sizes.

Having said that, this kind of 12x difference is roughly what I would expect if you coded the solution using "higher level" constructs such as ArrayLists / boxed objects and the C solution was basically using optimised, low level pointer arithmetic into a pre-allocated memory region.

I'd rather maintain the higher level solution, but there are times when only hand-optimised low level code will do.....

Another potential explanation is that the JIT had not yet warmed up on your code. In general, you need to reach "steady state" (typically a few thousand iterations of every code path) before you will see top performance in JIT-compiled code.

Performance depends on implementation. Without knowing exactly what you code and what your competitor did, it's very difficult to tell exactly what happened.

But let's say for isntance, that you used objects like vectors or whatever to solve the problem and the C guy used arrays[], his implementation is going to be faster than yours for sure.

C code can be translated very efficiently into assembly instructions, while Java on the other hand, relies on a bunch of stuff (like the JVM) that might make the bytecode of your program fatter and probably a little bit slower.

You will be hard pressed to find something that can execute faster in Java than in C. Its true that an order of magnitude is a big difference but in general C is more performant.

On the other hand you can produce a solution to any given problem much quicker in Java (especially taking into account the richness of the libraries).

So at the end of the day, if there is a choice at all, it comes down as a dilemma between performance and productivity.

That depends on the algorithm. Java is of course generally slower than C/C++ as it's a virtual machine but for most common applications its speed is sufficient. I would not call a factor of 12 normal for common applications.

Would be nice if you posted the C and Java codes for comparison.

A factor of 12 can be normal. So could a factor of 1 or 1/2. As some commentators mentioned, a lot has to do with how you coded your solution.

Dont forget that java programs have to run in a jvm (unless you compile to native machine code), so any benchmarks should take that into account.

You can google for 'java and c speed comparisons' for some analysis

Back in the days I'd say that there's nothing wrong with your Java code being 12 times slower. But nowadays I'd rather say that the C guy implemented it more efficiently. Obviously I might be wrong, but are you sure you used proper data structures and well simply coded it well?

Also did you measure the memory usage? This might sound silly, but last year at the uni we had a programming challenge, don't really remember what it was but we had to solve a graph problem in whatever language we wanted - I did two implementations of my algorithm one in C and one in Java, the Java one was ~1,5-2x slower, BUT for instance I knew I didn't have to worry about memory management (I knew exactly how big the input will be and how many test samples will be run from the teacher) so I simply didn't free any memory (which took way too much time in a programme that run for ~1-2seconds on a graph with ~15k nodes, or was it 150k?) so my Java code was better memory wise but it was slower. I also parsed the input myself in C (didn't do that in Java) which saved me really A LOT of time (~20-25% boost, I was amazed myself). I'd say 1,5-2x is more realistic than 12x.

Most likely the algorithm used in the implementation was different.

For instance ( an over simplification ) if you want to add a number N , M number of times one implementation could be:

 long addTimes( long n, long m ) {
    long r = 0;
    long i;
    for( i = 0; i < m ; i++ ) {
       r += n;
    }
    return r;
 }

And another implementation could simply be:

 long addTimes( long n, long m ) {
      return n * m;
  }

Both, will run mostly the same in Java and C (you don't even have to change the code ) and still, one implementation will run way lot faster than the other.