Yet Another Language Speed Test – Counting Primes(bjpelc.wordpress.com)
bjpelc.wordpress.com
Yet Another Language Speed Test – Counting Primes
https://bjpelc.wordpress.com/2015/01/10/yet-another-language-speed-test-counting-primes-c-c-java-javascript-php-python-and-ruby-2/
18 comments
Merely including <iostream> results in std::cout/std::cerr/std::cin being constructed on startup even if they're never used (as in this case). This doesn't take very long, but when the actual work being tested takes under a millisecond...
Based on the graph available in the post, the only difference I see between C and C++ performance is on low n. At higher values of n, they have the same performance (as expected). That discrepancy is easily explained by considering start-up time, which C++ could certainly suffer from. Combine that with the consideration that the values for n where the two differ result in a computation time < ~10ms, which is about the range where startup time is going to significantly impact results.
This is also easy to see by looking at the second derivative of the graphs. When n is large enough to outweigh startup time, the graph should be linear. The areas where the second derivative is non-zero indicate that start-up time is affecting results.
You can see that all the languages have some kind of startup time impacting results. Java in particular has the same performance as C/C++ under this test, but has a significantly larger startup time.
Really experiments like this should split the results to explicitly show these two aspects of performance. Measure startup time and measure the time running the actual test code separately. Though that might be more challenging on JIT'd languages.
This is also easy to see by looking at the second derivative of the graphs. When n is large enough to outweigh startup time, the graph should be linear. The areas where the second derivative is non-zero indicate that start-up time is affecting results.
You can see that all the languages have some kind of startup time impacting results. Java in particular has the same performance as C/C++ under this test, but has a significantly larger startup time.
Really experiments like this should split the results to explicitly show these two aspects of performance. Measure startup time and measure the time running the actual test code separately. Though that might be more challenging on JIT'd languages.
The differences at the low end of the chart are the startup costs, which get amortised out at the high end.
You could only return bools in the flags for static functions that don't have their address taken, because this would break the established API. It'd also generally only be useful if the function result is immediately used in a test.
You could only return bools in the flags for static functions that don't have their address taken, because this would break the established API. It'd also generally only be useful if the function result is immediately used in a test.
The difference between C and C++ might have to do with that: http://www.cplusplus.com/reference/ios/ios_base/sync_with_st...
Probably some library initializaion takes enough time to affect the results. I wonder what is taking time in this case.
I'm pretty sure I remember Delphi using the carry flag to return boolean values.
Here's an update that includes Go and Haskell:
https://bjpelc.wordpress.com/2015/01/13/yet-another-language...
https://bjpelc.wordpress.com/2015/01/13/yet-another-language...
Notably, it should be mentioned that writing idiomatic
Python and Ruby results in much slower code than that
used here. Ranges bad. While loops good.
But unless you're doing computationally expensive operations, I don't see the benefit of these speed tests except to provide ammunition for flame wars. What good is it for your code to run 50% faster if you spend 300% more time creating, debugging, and maintaining it?
I'm glad you brought this up, because I was thinking about it but felt like my relative unfamiliarity with C(++) and a handful of other languages in this "shoot-out" made my understanding here flawed (or at least partially naive). I'm also going to piggyback a bit because another thought I had seems related.
There's also the issue that among languages like Python, standard libraries (like multiprocessing[0]) make parallelizing code trivial (even with/despite the dreaded global interpreter lock). I rewrote some of the code the author uses and on a smaller number (6710886 instead of 67108864) I'm seeing ~1/3 the time to run compared to his baseline with 4 worker processes (27.469517s vs 1:25.373176). I haven't looked into what might be keeping it from being a full 4x faster, but my hunch is that it's a combination of other things going on in my laptop and the undeniable difference in execution speed in cPython (specifically, cPython3.4).
One might make the argument that this is a wildly unfair comparison, but my bigger-picture argument is that a language that abstracts things like parallelization to the point that one can invoke such features in a line or two of added & changed code is probably worth factoring into an analysis, if we're even interested in analyzing languages in this way.
If we're going to write C-like code and run it as Python, should we be surprised when it doesn't live up to those expectations?
[0]: https://docs.python.org/3.4/library/multiprocessing.html
There's also the issue that among languages like Python, standard libraries (like multiprocessing[0]) make parallelizing code trivial (even with/despite the dreaded global interpreter lock). I rewrote some of the code the author uses and on a smaller number (6710886 instead of 67108864) I'm seeing ~1/3 the time to run compared to his baseline with 4 worker processes (27.469517s vs 1:25.373176). I haven't looked into what might be keeping it from being a full 4x faster, but my hunch is that it's a combination of other things going on in my laptop and the undeniable difference in execution speed in cPython (specifically, cPython3.4).
One might make the argument that this is a wildly unfair comparison, but my bigger-picture argument is that a language that abstracts things like parallelization to the point that one can invoke such features in a line or two of added & changed code is probably worth factoring into an analysis, if we're even interested in analyzing languages in this way.
If we're going to write C-like code and run it as Python, should we be surprised when it doesn't live up to those expectations?
[0]: https://docs.python.org/3.4/library/multiprocessing.html
Maybe too low chunksize value for map_async call?
[deleted]
I assume you only measured JRuby at low n, where the startup and warmup time would overshadow overall performance. JRuby is usually significantly faster than C Ruby. In this case, it's nearly twice as fast:
[] ~/projects/jruby $ time jruby primes.rb
Number of primes in the interval [0,67108864]: 3957809
real 6m26.536s
user 6m43.472s
sys 0m4.967s
[] ~/projects/jruby $ time rvm ruby-2.2 do ruby primes.rb
Number of primes in the interval [0,67108864]: 3957809
real 11m17.610s
user 11m16.564s
sys 0m0.738sWorth pointing out that there's no dynamic allocation or dispatch in any of the examples (afaict), so all languages that use a GC get around having to do any reference tracking or collection. Which explains how Go/Java/C++ can track C performance so closely. I wouldn't be surprised if they'd all run almost the same machine code in the end.
The benchmark (perhaps intentionally) doesn't test the most important thing when we want to compare "language speed": the efficiency of abstractions. The benchmark has no abstractions at all other than a simple, single-target, function call that most compilers (whether AOT or JIT) would inline. Interesting language comparisons test the languages' core abstractions like as virtual dispatch/pattern matching.
It tests one other thing - a recursive function call that is amenable to tail-call optimisation.
I know the point of this blog post is to benchmark languages with a naive use case, but for those interested, there are many faster algorithms designed for deterministically or probabilistically checking the primality of a number, and even faster ones for computing the number of primes up to n. Recently a modified Lagarias-Odlyzko method was used to compute the number of primes up to 10^25, although I believe it requires the Riemann Hypothesis.
Approximations to this computation are even more fun: Asymptotically, this function tends to x/ln(x), or more accurately to the integral 1/ln(x) dx from x=2 to n, whose asymptotic expansion is x/ln(x) + 1!x/(ln(x))^2 + 2!x/(ln(x))^3 + ...
Approximations to this computation are even more fun: Asymptotically, this function tends to x/ln(x), or more accurately to the integral 1/ln(x) dx from x=2 to n, whose asymptotic expansion is x/ln(x) + 1!x/(ln(x))^2 + 2!x/(ln(x))^3 + ...
This test is rather misleading. For instance, I decided to rewrite this same procedure in Swift. I was stunned to find out that at first the speed was almost 4 times slower. The C program took 34 seconds to run to 67108864 while Swift took 2:11 minutes.
However, after swapping out the Float only capable square root from Swift Foundation for the C sqrt function, leaving the rest of the code identical, the execution time on the Swift code went down to 35 seconds, basically identical.
I have to wonder if Python, Ruby, and PHP just have a Float only capable square root function, or handle numbers with much higher precision than necessary by the test.
However, after swapping out the Float only capable square root from Swift Foundation for the C sqrt function, leaving the rest of the code identical, the execution time on the Swift code went down to 35 seconds, basically identical.
I have to wonder if Python, Ruby, and PHP just have a Float only capable square root function, or handle numbers with much higher precision than necessary by the test.
It's important to note that some languages (particularly Java) don't ramp up to their full speed until they are properly warmed up. It also sounds like the author included startup time in the measurements, which will skew results for the lower values of n.
Overall, be very careful of micro-benchmarks like these. The conclusions that you can draw from them are tenuous at best, and usually have little bearing on the performance of an actual program.
Overall, be very careful of micro-benchmarks like these. The conclusions that you can draw from them are tenuous at best, and usually have little bearing on the performance of an actual program.
The note about the idiomatic Ruby version of this (each on a range) being slower than the tested version (while loop) is very interesting.
This looks like an opportunity for the Ruby interpreter to optimise: if the range is excessively large, it could decide itself to loop over the bounds rather than instantiating the entire range.
This looks like an opportunity for the Ruby interpreter to optimise: if the range is excessively large, it could decide itself to loop over the bounds rather than instantiating the entire range.
It doesn't. A range just knows if it's exclusive, and its beginning and end value. That line is also not really idiomatic. It's just trying to be.
What is interesting here is how Javascript is fastest of all non-compiled languages, even PyPy. It shows to me, that simple language with well thought out features can do wonders, even when it is interpreted.
I have no illusion that this is definite test of speed of languages.
I have no illusion that this is definite test of speed of languages.
JavaScript is not simple, its features are not well thought out, and it is definitely not being interpreted. The only reason JavaScript performs well here is that multiple megacorporations have devoted tons of resources into fast JavaScript implementations.
It's the JIT for JavaScript that does the magic here, the code isn't interpreted all the time.
I would like to see the numbers of the Python code compiled without modifications with Cython.
Without modifications it yields between 20 to 30% increase in performance. However Cythons strength is in the type annotations. With those it should get close to C speed.
I would love the Cython team to work on the performance without modifications. Maybe they could make use of the standardized type hints of Python 3.5.
I could see myself compile with Cython here and there if the performance gains would be meaningful but I do not want to write Cython.
I could see myself compile with Cython here and there if the performance gains would be meaningful but I do not want to write Cython.
Considering that Python 3 remains slower than Python 2 on many benchmarks, what you're suggesting would be an interesting feature for Cython/Python 3 -- "Compile your Python 3 code with Cython and get 100%* speedup (*on average)".
However, as I understand, Py3's type hints are derived from a previously available module (which I think also worked with Py2). So why would they add compatibility for that now? Why not just write your own parser that reads types annotations and then outputs Cython-equivalent variables declartions?
There are also some Cython specific types that you won't find, for example the functions can be either cdef or cpdef, depending if you plan to use them from C only, or C and Python.
I still see value in learning Cython as a complement to Python, for the cases where you need to get "closer to the metal". It's not so much more, and it helps a lot in performance.
However, as I understand, Py3's type hints are derived from a previously available module (which I think also worked with Py2). So why would they add compatibility for that now? Why not just write your own parser that reads types annotations and then outputs Cython-equivalent variables declartions?
There are also some Cython specific types that you won't find, for example the functions can be either cdef or cpdef, depending if you plan to use them from C only, or C and Python.
I still see value in learning Cython as a complement to Python, for the cases where you need to get "closer to the metal". It's not so much more, and it helps a lot in performance.
So I can't edit my previous response anymore, but going over Ian Ozsvalds talks, I found this particular snippet (about 1 minute), in which he describes ShedSkin as pretty much what you want ;)
The link: https://www.youtube.com/watch?v=4LlCqlMJr3E&t=18m50s
The whole talk is valuable, of course, but it might not be your thing if you're not into numerical coding.
The link: https://www.youtube.com/watch?v=4LlCqlMJr3E&t=18m50s
The whole talk is valuable, of course, but it might not be your thing if you're not into numerical coding.
It would be nice to see the numbers, in addition to the graph.
I did a straight port of C to lua, and ran it with luajit.
The C code ran in 49.901s.
The luajit code ran in 14m16.547s.
C code was compiled with -02 -std=c11 -lm (version 4.8.1, mingw).
luajit.exe was 2.0.3, static build, using VS2012 x64
I did a straight port of C to lua, and ran it with luajit.
The C code ran in 49.901s.
The luajit code ran in 14m16.547s.
C code was compiled with -02 -std=c11 -lm (version 4.8.1, mingw).
luajit.exe was 2.0.3, static build, using VS2012 x64
It would also be nice to express numbers in the same base too. :-)
"The luajit code ran in 856.547s."
The graph is log-log which can be a bit tricky to read but that puts it in the same ballpark as Ruby and PHP (assuming the same factor of difference between the two, after scaling your C vs luajit results to match the given C value of ~40s, luajit becomes 687s.)
"The luajit code ran in 856.547s."
The graph is log-log which can be a bit tricky to read but that puts it in the same ballpark as Ruby and PHP (assuming the same factor of difference between the two, after scaling your C vs luajit results to match the given C value of ~40s, luajit becomes 687s.)
Did you turn off the JIT? My LuaJIT ran 2.16x slower versus 8x for Lua 5.1, 9.35x 5.2, 10.33 5.3. (I didn't localize the math.sqrt but I know LuaJIT wouldn't care.)
* Oops, I had cheated and used a for loop instead of while. The LuaJIT time was the same but the others are 10.5x, 12.58x, 15.63x.
* Oops, I had cheated and used a for loop instead of while. The LuaJIT time was the same but the others are 10.5x, 12.58x, 15.63x.
On OSX 10.1 with luajit 2.1.0 alpha, a straight translation of the C code gets me 59 seconds on my machine which is close to the C speed on it (38 seconds compiled with O3)
Edit: fixed luajit version
Edit: fixed luajit version
I've placed my port here:
https://gist.github.com/anonymous/ce176d7ab4f6b7b1ba91
If you see anything wrong with it, or odd, feel free to share.
I'm still investigating what is happening to make the run so slow, so if you can find something wrong in my code, that would help.
If you see anything wrong with it, or odd, feel free to share.
I'm still investigating what is happening to make the run so slow, so if you can find something wrong in my code, that would help.
Lua is global by default. Declare all the variables as local and you'll see significant improvement. Also, there is a boolean type so you can use true and false directly instead of comparing numbers.
I tried using locals, and there was no change to the time.
Using a boolean return value for isPrime shaved off two seconds.
As Go and Haskell have already been added, it would be nice to benchmark Rust, Hack (vs. PHP), and perhaps LUA and Clojure, too.
$ math
In[1]:= AbsoluteTiming[PrimePi[67108864]]
Out[1]= {0.009661, 3957809}
why even bother with prime numbers? just have the program count from 1 to 2^n and the results will have about as much meaning as these do.
Why many programmers have a tendency to generate performance numbers and extrapolate conclusions without understanding the bottlenecks?
on the other hand:
combining the first 2 ifs into if (n <= 2) { if (n < 2) return 0; else return 1}, would eliminate an unnecessary if statement check that will be false for most values.
>If n < two: return false.
> If number is equal to two: return true.
> If n (>2) is even: return false
on the other hand:
combining the first 2 ifs into if (n <= 2) { if (n < 2) return 0; else return 1}, would eliminate an unnecessary if statement check that will be false for most values.
>If n < two: return false.
> If number is equal to two: return true.
> If n (>2) is even: return false
Why do many Hacker news commenters criticize posts without understanding what the writer is trying to do? The purpose is to benchmark the language, not to come up with the most efficient algorithm.
Further, your suggested optimization is terrible. Even if it turns out that's slightly faster (which I'm not convinced it is: did you actually compile that code and look at the generated assembly or profile it?) there are much bigger wins to be had by using a better overall algorithm, such as the sieve of Eratosthenes, which was mentioned in the article if you had read it.
I know I'm being a grumpy old man here, but if you decide to comment on articles you either didn't read or didn't understand, you've only yourself to blame.
Further, your suggested optimization is terrible. Even if it turns out that's slightly faster (which I'm not convinced it is: did you actually compile that code and look at the generated assembly or profile it?) there are much bigger wins to be had by using a better overall algorithm, such as the sieve of Eratosthenes, which was mentioned in the article if you had read it.
I know I'm being a grumpy old man here, but if you decide to comment on articles you either didn't read or didn't understand, you've only yourself to blame.
I did read the article, and to find my suggestion terrible indicates that you don't know how CPU instruction pipelines work. My suggestion will give you a big win because of branch prediction optimization. Without it, the CPU pipeline will be processing less instructions in parallel because the condition will be false in most cases.
When you benchmark, it's important to know what you are doing or you'll arrive to the wrong conclusions because of unknowns you aren't aware of.
Writing some code to generate performance numbers and jumping to conclusions without understanding what influenced the numbers is unproductive to say the least. These conclusions influence a lot of code that will be written in the future.
If you cannot tell me where the bottleneck is (what's saturated), then you are better off not doing anything.
When you benchmark, it's important to know what you are doing or you'll arrive to the wrong conclusions because of unknowns you aren't aware of.
Writing some code to generate performance numbers and jumping to conclusions without understanding what influenced the numbers is unproductive to say the least. These conclusions influence a lot of code that will be written in the future.
If you cannot tell me where the bottleneck is (what's saturated), then you are better off not doing anything.
> I did read the article, and to find my suggestion terrible indicates that you don't know how CPU instruction pipelines work. My suggestion will give you a big win because of branch prediction optimization. Without it, the CPU pipeline will be processing less instructions in parallel because the condition will be false in most cases.
Thank you, Captain Obvious, for that very simplified explanation of junior undergrad systems architecture. That would all be very important if branch prediction misses were your biggest problem. Maybe look up the Sieve of Eratosthenes people keep mentioning because hey, people keep mentioning it for a reason!
Arguing about branch misses in this algorithm is like arguing about branch misses in a bogosort implementation. The correct optimization isn't to remove branch misses, it's to stop using bogosort and use a reasonable sorting algorithm.
I'll charitably believe that you read the article, but if you're still complaining that the code is unoptimized when the author clearly said it was unoptimized then you didn't understand the article. The article isn't about code optimization, it's about gathering performance metrics for naively-written code. It's profiling the language, not the code.
> If you cannot tell me where the bottleneck is (what's saturated), then you are better off not doing anything.
I'll tell you one thing for sure: the bottleneck isn't branch prediction misses.
EDIT: Just to tack on more reasons you're wrong here: 1) You don't actually know that what you did removed any possible branch prediction misses without looking at the generated assembly, and 2) you could probably eliminate more branches using a switch-case statement (although again you'd have to look at the generated assembly to see if that's the case).
Thank you, Captain Obvious, for that very simplified explanation of junior undergrad systems architecture. That would all be very important if branch prediction misses were your biggest problem. Maybe look up the Sieve of Eratosthenes people keep mentioning because hey, people keep mentioning it for a reason!
Arguing about branch misses in this algorithm is like arguing about branch misses in a bogosort implementation. The correct optimization isn't to remove branch misses, it's to stop using bogosort and use a reasonable sorting algorithm.
I'll charitably believe that you read the article, but if you're still complaining that the code is unoptimized when the author clearly said it was unoptimized then you didn't understand the article. The article isn't about code optimization, it's about gathering performance metrics for naively-written code. It's profiling the language, not the code.
> If you cannot tell me where the bottleneck is (what's saturated), then you are better off not doing anything.
I'll tell you one thing for sure: the bottleneck isn't branch prediction misses.
EDIT: Just to tack on more reasons you're wrong here: 1) You don't actually know that what you did removed any possible branch prediction misses without looking at the generated assembly, and 2) you could probably eliminate more branches using a switch-case statement (although again you'd have to look at the generated assembly to see if that's the case).
[deleted]
This is completely and totally meaningless.
It's excluding compiler time, and it's only outputting a single number. As such, there's nothing preventing any of the optimizing compilers from optimizing the entire program to essentially print("pi<num> = <num>"). Ditto, time to load interpreters is included, whereas time to load compilers is excluded.
Also, note that the output is different in format for the different languages.
On a different note: he mentions PyPy in passing but doesn't post benchmark numbers. It'd be interesting to see how PyPy fares, especially with the slower-in-Python idiomatic version.
It's excluding compiler time, and it's only outputting a single number. As such, there's nothing preventing any of the optimizing compilers from optimizing the entire program to essentially print("pi<num> = <num>"). Ditto, time to load interpreters is included, whereas time to load compilers is excluded.
Also, note that the output is different in format for the different languages.
On a different note: he mentions PyPy in passing but doesn't post benchmark numbers. It'd be interesting to see how PyPy fares, especially with the slower-in-Python idiomatic version.
As such, there's nothing preventing any of the optimizing compilers from optimizing the entire program to essentially print("pi<num> = <num>").
That has clearly not happened here. If it did, you would see a flat line regardless of n. Nevertheless it is a good idea to make it e.g. take n as a commandline parameter, even if only to make testing different values easier.
Ditto, time to load interpreters is included, whereas time to load compilers is excluded.
You don't have to load the compiler every single time you run the program, whereas that isn't the case with an interpreter.
Also, note that the output is different in format for the different languages.
It's performing a single output operation at the very end of the computation. Any difference in that would be completely lost in the noise as n increases and the computation time dominates.
On a different note: he mentions PyPy in passing but doesn't post benchmark numbers
PyPy is there between JavaScript and Ruby:
https://bjpelc.files.wordpress.com/2015/01/graph3.png
That has clearly not happened here. If it did, you would see a flat line regardless of n. Nevertheless it is a good idea to make it e.g. take n as a commandline parameter, even if only to make testing different values easier.
Ditto, time to load interpreters is included, whereas time to load compilers is excluded.
You don't have to load the compiler every single time you run the program, whereas that isn't the case with an interpreter.
Also, note that the output is different in format for the different languages.
It's performing a single output operation at the very end of the computation. Any difference in that would be completely lost in the noise as n increases and the computation time dominates.
On a different note: he mentions PyPy in passing but doesn't post benchmark numbers
PyPy is there between JavaScript and Ruby:
https://bjpelc.files.wordpress.com/2015/01/graph3.png
[deleted](1)
> It's excluding compiler time, and it's only outputting a single number. As such, there's nothing preventing any of the optimizing compilers from optimizing the entire program to essentially print("pi<num> = <num>"). Ditto, time to load interpreters is included, whereas time to load compilers is excluded.
Who cares?
This covers real world cases. If an optimizing compiler could actually figure out to optimize those programs to a printf() call, that would be an impressive level of optimization and I'd want to know about it (note that no optimizing compiler achieved that level of optimization). Likewise, I don't know about you, but when I run interpreted code, I often start by loading an interpreter.
If you want to profile a different use case, do it, but that doesn't mean profiling these cases is "completely and totally meaningless".
Who cares?
This covers real world cases. If an optimizing compiler could actually figure out to optimize those programs to a printf() call, that would be an impressive level of optimization and I'd want to know about it (note that no optimizing compiler achieved that level of optimization). Likewise, I don't know about you, but when I run interpreted code, I often start by loading an interpreter.
If you want to profile a different use case, do it, but that doesn't mean profiling these cases is "completely and totally meaningless".
PyPy is on the graph (dotted mustard line between Javascript and Ruby).
It seems to have been added after I made the comment.
There's no C++ features really being used here besides true/false (which basically gets treated as 1 and 0 in most compilers[1]) so there shouldn't be any difference between the two - even the generated code should be identical. The C++ code even uses printf instead of cout, which is one area where I would expect a difference. Thus I'm surprised by the large difference between C and C++ at the low end.
[1] On x86 and other ISAs with flags, booleans can be returned in them, which is an optimisation that I haven't seen compilers do (yet) on x86. It's common on embedded ISAs like 8051 though.