Comparing c and java programs

Question

Today I had an interview, we were asked a programming question, and I was asked to solve it using c / C ++ / Java, I solved it in java, and its execution time was 3 seconds (the test was more than 16,000 lines and accompanying us said the running time was reasonable), another person there solved it in c, and the lead time was 0.25 s, so I wondered if the coefficient of 12 is normal?

Edit: As I said, I don’t think that there really were a lot of possibilities for changing the algorithm, with the possible exception of one little thing, in any case, there was this protocol that we had to implement: A (client) and B (server ) exchange data in accordance with some protocol p, before messages are delivered, their validation is checked, the protocol is determined by its state and text messages that can be sent when it is in a certain state, in all states Only one valid message has been compiled, except for one state in which 10 messages were sent, there are 5 states, and the state transition is also determined by the protocol. so what I did with the state from which 10 different messages can be sent is to store their string value in an ArrayList container, and then when I need to check the correctness of the message in the corresponding state, I checked if arrayList.contains (sentMessageStr ); I think this complexity of the operation is O (n), although I think java has a built-in optimization for this operation, although now that I think about it, maybe I should have used a HashSet container. I assume that an implementation of c would store these predefined lexical strings lexicographically in an array and implement a binary search function.

thanks

Answer 1

I would suggest that probably jvm took a significant portion of these 3 seconds to load. Try running the Java version on the same machine 5 times in a row. Or try running both datasets 500 times larger. I suspect you will see a significant constant delay for the Java version, which will become negligible when the run time goes in minutes.

Answer 2

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

One of the first measurement rules is to establish a sufficient number of samples and obtain an average number of samples for comparison. Even several runs of the same program are not enough. You need to steer the machine enough to get samples whose values ​​can be compared. That is why test beds need to be warmed up, so there are few or no variables in the game, with the exception of the observed system.

And, of course, you also have different people implementing the same requirements / algorithms in different ways. It is important. Period. If the implementation of the algorithms has not been “normalized,” obtaining samples and comparing them is the same as comparing apples and watermelons.

I do not think that I need to expand the fact that the test stands could be of different configurations or under different loads.

Answer 3

It is almost impossible to say without seeing the code - you may have a better algorithm, for example, that scales better for larger input, but has a lot of overhead for small input sizes.

Having said that this difference is 12 times roughly what I would expect if you encoded the solution using higher-level constructs such as ArrayLists / boxed objects, and the C solution mostly used optimized low-level pointer arithmetic in the pre-allocated areas of memory.

I would prefer to support a higher level solution, but there are times when only low level manual code will be executed .....

Another potential explanation is that the JIT has not yet warmed up over your code. In general, you need to achieve a “steady state” (usually several thousand iterations of each code path) before you see maximum performance in JIT-compiled code.

Answer 4

Performance is implementation dependent. Not knowing exactly what you are coding and what your competitor has done, it is very difficult to say exactly what happened.

But let's say that it isntance that you used objects such as vectors or something else to solve the problem, and C-pairs used arrays [], its implementation will be faster than yours.

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

Answer 5

It will be difficult for you to find something that can be executed faster in Java than in C. Its true that the order of magnitude is a big difference, but in general, C is more efficient.

On the other hand, you can quickly solve the problem with the given problem in Java (especially considering the richness of the libraries).

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

Answer 6

It depends on the algorithm. Java, of course, is usually slower than C / C ++, since it is a virtual machine, but for most common applications its speed is sufficient. I would not call the coefficient 12 normal for normal applications.

It would be nice if you put the C and Java codes for comparison.

Answer 7

A factor of 12 may be normal. So it can be a factor of 1 or 1/2. As some commentators noted, a lot has to do with how you encoded your solution.

Do not forget that java programs should run in jvm (unless you are compiling your own machine code), so any tests should take this into account.

You can use google for "java and c speed comparisons" for some analysis

Answer 8

Most likely, the algorithm used in the implementation was different.

For example, if you want to add the number N, M, the number of times that one implementation can 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 may be simple:

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

Both will work mainly in Java and C (you don’t even have to change the code), and yet one implementation will work much faster than the other.

Answer 9

In the days when I said that with your Java code there is nothing wrong with 12 times slower. But for now, I would say that guy C implemented it more efficiently. Obviously, I'm wrong, but are you sure you are using the correct data structures and have encoded it well well?

Also did you measure memory usage? This may seem silly, but last year uni we had a programming problem, I really don’t remember what it was, but we had to solve the graph problem in any language we wanted - I performed two implementations of my algorithm in C and one in Java, one Java was 1.5-2 times slower, BUT, for example, I knew that I did not need to worry about memory management (I knew exactly how great the input would be and how many test samples would be run from the teacher) , so I just did not free the memory (which took too much time in the prog a frame that ran for ~ 1-2 seconds on a graph with nodes ~ 15 thousand or was it 150 thousand?), so my Java code was better than memory but it was slower. I also analyzed the input myself in C (did not do it in Java), which actually saved me MUCH time (~ 20-25% boost, I was struck by myself). I would say that 1.5-2x is more realistic than 12x.