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/

by MrBra • 11 years ago

30 52 11 years ago

bjpelc.wordpress.com

TheLoneWolfling2• 11 years ago

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.

gilgoomesh• 11 years ago

PyPy is on the graph (dotted mustard line between Javascript and Ruby).

TheLoneWolfling2• 11 years ago

It seems to have been added after I made the comment.

userbinator3• 11 years ago

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

copsarebastards3• 11 years ago

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".

halayli2• 11 years ago

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

copsarebastards3• 11 years ago

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.

halayli2• 11 years ago

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.

userbinator3• 11 years ago

C is the fastest, with C++ approximately the same

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.

nine_k• 11 years ago

Probably some library initializaion takes enough time to affect the results. I wonder what is taking time in this case.

pbsd• 11 years ago

I'm pretty sure I remember Delphi using the carry flag to return boolean values.

plorkyeran• 11 years ago

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...

caf4• 11 years ago

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.

fpgaminer• 11 years ago

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.

epsylon• 11 years ago

The difference between C and C++ might have to do with that: http://www.cplusplus.com/reference/ios/ios_base/sync_with_st...

allendoerfer2• 11 years ago

I would like to see the numbers of the Python code compiled without modifications with Cython.

dr_zoidberg3• 11 years ago

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.

allendoerfer2• 11 years ago

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.

ryanmk4• 11 years ago

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

userbinator3• 11 years ago

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.)

letitgo12345• 11 years ago

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

ryanmk4• 11 years ago

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.

whoopdedo3• 11 years ago

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.

throwaway232• 11 years ago

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.

RobAtticus• 11 years ago

Here's an update that includes Go and Haskell:

https://bjpelc.wordpress.com/2015/01/13/yet-another-language...

pron• 11 years ago

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.

caf4• 11 years ago

It tests one other thing - a recursive function call that is amenable to tail-call optimisation.

caf4• 11 years ago

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.

cremno• 11 years ago

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.

whoopdedo3• 11 years ago

    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.

I get 33% shorter times when I change the while loops to for-in-range and a list comprehension.

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?

alialkhatib• 11 years ago

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

stelund• 11 years ago

Maybe too low chunksize value for map_async call?

jkrems• 11 years ago

Worth 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.

vortico2• 11 years ago

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 + ...

RandomBK• 11 years ago

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.

x00542• 11 years ago

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.

caf4• 11 years ago

The C sqrt function is

  double sqrt(double)

x00542• 11 years ago

Hmm, I can see that too now, though I am passing into it a CInt, and getting back a CInt. Is it just converting the Int to Double internally and shooting back a Double which is converted to CInt? If so, why do you think it's so much faster?

desireco42• 11 years ago

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.

jmgao• 11 years ago

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.

acqq• 11 years ago

It's the JIT for JavaScript that does the magic here, the code isn't interpreted all the time.

vortico2• 11 years ago

    $ math
    
    In[1]:= AbsoluteTiming[PrimePi[67108864]]
    Out[1]= {0.009661, 3957809}

:^)

aruggirello• 11 years ago

As Go and Haskell have already been added, it would be nice to benchmark Rust, Hack (vs. PHP), and perhaps LUA and Clojure, too.

headius• 11 years ago

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.738s

Yet Another Language Speed Test – Counting Primes

Related Stories