Java can be significantly faster than C
Preface
When I wrote this article it was to comment on how writing the same algorithm implement a different way can make a major difference. I now believe this is not the point of the web site perhaps shouldn't be the point of this article either. I have written a follow up article.The importance of innovation
Overview
Whether you use Java or C is not always as important as the approach you use. By "approach" I mean; algorithms not specified in the requirements or "the how" to do something.You might not see this as a fair test of Java vs C, but in the real world human factors are matter. There is no point saying C is faster in theory but there isn't anyone available to make it so. Its like getting a very cheap price on an item which is not in stock. ;)
Benchmark Shootout
Java is temporarily the fastest for this particular knucleotide benchmark. It is quite likely that if the algorithm I used is translated to C it would be faster again. But for the moment Java is fastest because it uses a different approach in a number of key places.
Benchmark results at Wed 31st August 2011.
If anyone is interested in translating it to C, I would like to know how much faster it is. ;)
So your program uses a different algorithm and shouldn't be shown alongside those other programs on the benchmarks game.
ReplyDeleteSeems like you only contributed the program so you could indulge in some flame-baiting.
@Isaac Gouy, I am sorry if it come across that way.
ReplyDeleteI submitted it to make a point as stated. I believe that given any amount of time and resources C is in theory the fastest. That may change to a language like OpenCL given the right hardware.
Given a limited time and resources a higher level language can deliver the fastest solution. Something you can replace with a lower level solution in time as required.
Its a topic I have discussed at length before C++ or Java, which is faster for high frequency trading? but lacked a concrete and open example. (I have large bodies of closed source software from my experience but that is largely opinion)
Using a different approach the solve the same problem is in the nature of innovation and innovation can make more of a difference that just incrementally improving or re-writing what other people have already done.
IMHO, Some languages encourage more innovation e.g. by being more open source friendly. This is not a feature of the language as such but how it is actually used. I believe this is part of the reason that Java tends to be faster than C# in benchmarks even though C# is a superset of the features of Java.
Did your version get pulled?
ReplyDelete@Vyadh - Oh yeah!
ReplyDelete"Why don't you accept every program that gives the correct result? - We are trying to show the performance of various programming language implementations - so we ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result."
http://shootout.alioth.debian.org/help.php#contest
@Peter Lawrey - "I submitted it to make a point as stated."
ReplyDeleteYou didn't state that when you contributed your program. You gave a pretence - "I have read all the instructions now."
@Peter Lawrey - "Does my opinion challenge the assumption of this web site? That you can find the definitive fastest language?"
Your opinion about "the assumption of this web site" seems to have been achieved by not actually reading what's written on the website.
@Issac Gouy, Thank you for you reply. I understand the need to have a fair/meaningful basis of comparison. Obviously the fastest correct answer is cat correct-answer.txt ;)
ReplyDeleteI also believe that the judge's decision is final in this case and you should be free to run your web site the way you feel is best. You clearly put a lot of good work into it.
The way I read the requirements was sufficiently broad that you can follow the instructions and still make use of the best features of the language. (Which is a good thing)
An example (something I admit I didn't read the first time)
"programs are expected to either take a single command-line parameter or read text from stdin."
This doesn't say which functions must be used to do this and a "different approach" I thought made the benchmark faster was to memory map stdin. This is not typical behaviour for stdin (because in Java System.in is not used for performance, it used for terminal input, and then mostly for homework projects AFAIK) Memory mapping files is typical behaviour for high performance applications reading from a file. (which is what it is actually doing)
It was my view that how it reads from stdin is independent to the algorithm used. However it could be seen as violating the intent of the rule. Only you can judge that.
Another key decision was how the hashing algorithm was performed (something which is not mentioned in the instructions). Instead of writing a general purpose hashing, e.g. HashMap, I tuned it for this dataset (which should also perform well for a similar dataset) This could also be considered breaking the rules but very difficult to define what is possible/not possible. Again, you have to judge was is reasonable and what is not.
I was concerned that you may have taken exception to my comment "not always as important as the algorithm you use" which you quoted else where. I thought you might have seen as an attack on your objective to find "Which programming languages are fastest?" It was not intended as such, and I can see now this is not the reason for the rejection.
Another difference from the C implementation is that instead of maintain a single count of nucleotides, each thread maintained its own counts which are summed to get a final count at the end. A simplified Map-Reduce strategy. Doing this allows each thread to use a faster cache L1/L2 instead of using the shared lower cache, but incurs some extra work to sum the results.
ReplyDeleteMap-reduce is a very common strategy in multi-threaded applications. I didn't see anything which said it couldn't be used.
One more difference is that instead of having a main thread and a thread pool of 4 (as the machine has 4 cores), I had a main thread and a thread pool of 3. The main thread passed 3/4 of the work to the pool but did about 1/4 of the work itself. It avoided passing some work back and forth between threads and avoided the possibility that there are 5 threads trying to run on a 4 core machine.
ReplyDeleteThis appears to have a small improvement on the best times when run repeatedly, but appeared to reduce the variation in times significantly.
> An example (something I admit I didn't read the first time)
ReplyDeleteNow you exclude this from your /quotation/ - "(Look at what the other programs do.)"
> It is quite likely that if the algorithm I used is translated to C...
You've been very clear in this blog post that you think you used a different algorithm.
More than that, you intended to use a different algorithm - it's the essential point of this blog post.
> your objective to find "Which programming languages are fastest?"
As I've already said, you don't seem to have read what's actually written on the website.
The objectives are stated at the top of the Help page - 1,2,3.
> You've been very clear in this blog post that you think you used a different algorithm.
ReplyDeleteIt could sound like the benchmark was not rejected based on what it does or how it does it but what may have been in the mind of the developer at the time.
Some algorithms were specified and some algorithms were not. I full intended to comply with all the stated requirements but for algorithms not stated like how to read stdin, how hashing is done, how to count matches, provided a faster option.
In my earlier submission, I failed to use stdin which you picked me up on and I corrected.
> More than that, you intended to use a different algorithm - it's the essential point of this blog post.
Anyone who is trying to improve a previous result has to do something differently. If you are only doing "what the other programs do" how can it be any faster? How would such a process ever get stated?
I made a determination as to what the program has to do to meet the stated requirements and see if the approaches other had used could be do differently to improve performance.
I had assumed that the objective was to implement the fastest solution for a given language which did what was asked, but without having to translate an existing solution. I think this what I failed to understand.
> The objectives are stated at the top of the Help page - 1,2,3.
Reading this again is interesting, but I would have to think about how these relate to this discussion.
In my mind this raises a bigger question, how do to lay down standards without stifling innovation? Not sure I have a great answer to this.