9 ms·

C++ Is 9.4 Times Faster Than Python in Prime Number Test

9 points by joebaf 6y ago

Bostonian 6y ago
Why is this noteworthy? That C++ is faster than pure Python is well known.
- estebarb 6y ago
  Maybe a lot of people is developing in Python, Ruby, PHP and others traditionally interpreted languages and aren't aware of it. Using C or C++ for some domains would be painful, but regarding speed, memory usage or energy usage those languages tend to be the best. If only Rust would be less C++ like (I prefer "RISC" like languages)
  - nicoburns 6y ago
    True, although Python and Ruby are extreme cases here. PHP is JIT'd these days, and can be quite a bit faster on this kind of numerical code. JavaScript even more so. I've seen posts on r/rust asking why their Rust port wasn't faster than the JS version, and it turned out not to be lack of optimisation, it was just simple numerical code (doesn't require allocation) which is already super-optimised by modern JS engines.
    - igouy 6y ago
      MJIT https://www.ruby-lang.org/en/news/2020/12/25/ruby-3-0-0-released/ https://www.ruby-lang.org/en/news/2020/12/25/ruby-3-0-0-rele... (Also pypy)
      - Rochus 6y ago
        The performance gain of the MRI Ruby JIT is not really impressive, see e.g. http://software.rochus-keller.info/are-we-fast-yet_crystal_ruby_2_3_lua_node_i386_results_2020-12-23.pdf http://software.rochus-keller.info/are-we-fast-yet_crystal_r.... Actually also the factor 4 PyPy speed-up in geomean is not that much overall (e.g. compared to V8).
        igouy 6y ago
        But it's existence is sufficient to add Ruby to the "is JIT'd these days" list.
- arithma 6y ago
  C++ expression-power has increased considerably since C++11, and I believe, semantically, Prime Number generation in both C++ and Python could be python-line for c++-(line[s]) translated. C++ approaching the comfort and ease of use of Python is a worthy goal to reach. The flip side is well appreciated too (Cython, where Python can converge to C++ performance is noteworthy as well).
- hawski 6y ago
  Maybe, because it's only a one order of magnitude faster? I would expect for it to be something between 10x and 100x faster.
adsharma 6y ago
How long did it take you to write C++ vs python? What if you could write python and generate C++?
Farmadupe 6y ago
I think this feels like an underestimate of the performance difference? I generally keep in my head that C/CPP is roughly 100x faster than python, and the computer language benchmarks game seems to support this (I admit that the solutions on there are uncharacteristic of idiomatic code in many cases but hopefully the python and CPP solutions are equally horrible there). https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/gpp-python3.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... I wonder how you can characterize the difference in speed between the two languages. I think I read somewhere that in the reference implementation of ruby, calling a method in the general case can require several hash table lookups to find the implementation associated with the name of the method. Is that mostly the same in python as well?
- steerablesafe 6y ago
  I expect a lot of time being wasted in `sqrt`, which is probably similar in the two languages.
  - contravariant 6y ago
    Yeah it's probably better to use something like k*k < n as a stopping condition. Though that one uses requires some additional calculation per step. I've once tried to fix that part by using the (usually discarded) result of `n div k` to determine when k < sqrt(n). I couldn't get it to work (faster) but it was fun to try.
    - steerablesafe 6y ago
      Interesting. In principle that idea does look better, but the data dependency on the loop condition could be the bottleneck. CPUs probably have plenty of pipelining capacity to calculate `k*k` parallel to `n div k`, so effectively free as it's much faster than division.
- Rochus 6y ago
  > I generally keep in my head that C/CPP is roughly 100x faster than python Right; here is a recent scientific publication which confirms about factor 50 speed-down from C++ to Python for the given micro benchmarks: https://authors.elsevier.com/a/1cP%7ELc7X4-XPM; https://authors.elsevier.com/a/1cP%7ELc7X4-XPM; see table 4. The more time Python spends in native procedures, the more favorable the ratio is for Python; this is probably the reason why only around factor ten was measured here.
DoofusOfDeath 6y ago
I have serious reservations about headlines like this, but perhaps I'm being pedantic without realizing. My concern is that a particular mathematical function can be expressed in many different ways using Python and using C++. And practically speaking, it's impossible to be sure that you've created the fastest-possible implementation of that function in either language. And even then some implementations' performances are dependent on the compiler, supporting libraries, and underlying processor architecture. So AFAIK a headline like this leaves out way too many details to be generally true. Am I missing something?
- Farmadupe 6y ago
  I think given the naive algorithm of both implementations, and the fact the python and cpp are near transliterations of each other, the article isn't really trying to make the literal statement of the words of its title. Of course the relationship between language semantics and actual raw performance on real hardware is probably a neverending topic. I guess the article is more trying to make a statement along the lines of "here's how you benefit if you know python and pretend that means you know CPP too", (which seems like a fairly valid way to suck people into learning CPP to me)
  - adsharma 6y ago
    shameless plug: https://github.com/adsharma/py2many https://github.com/adsharma/py2many I didn't write the python -> C++ transpiler, but added a few features to common and added basic support in 6 other languages. It should be possible to generate the C++ from python.
    - Rochus 6y ago
      Interesting. Do you have performance data (e.g. all CLBG Python benchmarks transpiled to C++ and run)? What's the speed-up?
      - adsharma 6y ago
        I haven't focused on performance yet. Thanks for the pointer! Gives me a concrete target to go after. https://github.com/adsharma/py2many/tree/main/tests/expected https://github.com/adsharma/py2many/tree/main/tests/expected is a good place to understand what types of code this system can transpile. Most languages are using templates/generics/auto etc. I added some type inference capabilities to common code and updated dart to take advantage of it. Should be possible for other languages as well. btrees python -> C++/rust seems feasible as a point of comparison. Hard problem: translating library calls from one language to another. I'm thinking of some type of a plugin system that app developers can provide mappings.
contravariant 6y ago
Although python does have from sympy import primepi primepi(1e6) which returns instantly.
- joshka 6y ago
  This is the real answer, although the algorithm used seems to use a sieve rather than a naive check for (x & i == 0) https://github.com/sympy/sympy/blob/219993505f88a8d6f825db1deaad939a28cbb78c/sympy/ntheory/generate.py#L417-L528 https://github.com/sympy/sympy/blob/219993505f88a8d6f825db1d...
  - igouy 6y ago
    No, this is the real answer: https://web.archive.org/web/20010606131022/http://www.bagley.org/~doug/shootout/bench/sieve/ https://web.archive.org/web/20010606131022/http://www.bagley...
fdomingues 6y ago
C++ Is NOT 9.4 Times Faster Than Python in Prime Number Test I added 3 lines to the Python code and got it 10x faster: (venv) $ python prime.py Number of primes between 0 to 1000000 = 78498 Elapsed time: 6.502481937408447 (venv) $ python prime.py Number of primes between 0 to 1000000 = 78498 Elapsed time: 0.6258630752563477 Diff: 3c3,5 < --- > import numba > > @numba.njit 14a17 > @numba.njit

9 points by joebaf 6y ago

Bostonian 6y ago

Why is this noteworthy? That C++ is faster than pure Python is well known.

estebarb 6y ago
Maybe a lot of people is developing in Python, Ruby, PHP and others traditionally interpreted languages and aren't aware of it. Using C or C++ for some domains would be painful, but regarding speed, memory usage or energy usage those languages tend to be the best. If only Rust would be less C++ like (I prefer "RISC" like languages)
- nicoburns 6y ago
  True, although Python and Ruby are extreme cases here. PHP is JIT'd these days, and can be quite a bit faster on this kind of numerical code. JavaScript even more so. I've seen posts on r/rust asking why their Rust port wasn't faster than the JS version, and it turned out not to be lack of optimisation, it was just simple numerical code (doesn't require allocation) which is already super-optimised by modern JS engines.
  - igouy 6y ago
    MJIT https://www.ruby-lang.org/en/news/2020/12/25/ruby-3-0-0-released/ https://www.ruby-lang.org/en/news/2020/12/25/ruby-3-0-0-rele... (Also pypy)
    - Rochus 6y ago
      The performance gain of the MRI Ruby JIT is not really impressive, see e.g. http://software.rochus-keller.info/are-we-fast-yet_crystal_ruby_2_3_lua_node_i386_results_2020-12-23.pdf http://software.rochus-keller.info/are-we-fast-yet_crystal_r.... Actually also the factor 4 PyPy speed-up in geomean is not that much overall (e.g. compared to V8).
      - igouy 6y ago
        But it's existence is sufficient to add Ruby to the "is JIT'd these days" list.
arithma 6y ago
C++ expression-power has increased considerably since C++11, and I believe, semantically, Prime Number generation in both C++ and Python could be python-line for c++-(line[s]) translated. C++ approaching the comfort and ease of use of Python is a worthy goal to reach. The flip side is well appreciated too (Cython, where Python can converge to C++ performance is noteworthy as well).
hawski 6y ago
Maybe, because it's only a one order of magnitude faster? I would expect for it to be something between 10x and 100x faster.

adsharma 6y ago

How long did it take you to write C++ vs python? What if you could write python and generate C++?

Farmadupe 6y ago

I think this feels like an underestimate of the performance difference? I generally keep in my head that C/CPP is roughly 100x faster than python, and the computer language benchmarks game seems to support this (I admit that the solutions on there are uncharacteristic of idiomatic code in many cases but hopefully the python and CPP solutions are equally horrible there). https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/gpp-python3.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... I wonder how you can characterize the difference in speed between the two languages. I think I read somewhere that in the reference implementation of ruby, calling a method in the general case can require several hash table lookups to find the implementation associated with the name of the method. Is that mostly the same in python as well?

steerablesafe 6y ago
I expect a lot of time being wasted in `sqrt`, which is probably similar in the two languages.
- contravariant 6y ago
  Yeah it's probably better to use something like k*k < n as a stopping condition. Though that one uses requires some additional calculation per step. I've once tried to fix that part by using the (usually discarded) result of `n div k` to determine when k < sqrt(n). I couldn't get it to work (faster) but it was fun to try.
  - steerablesafe 6y ago
    Interesting. In principle that idea does look better, but the data dependency on the loop condition could be the bottleneck. CPUs probably have plenty of pipelining capacity to calculate `k*k` parallel to `n div k`, so effectively free as it's much faster than division.
Rochus 6y ago
> I generally keep in my head that C/CPP is roughly 100x faster than python Right; here is a recent scientific publication which confirms about factor 50 speed-down from C++ to Python for the given micro benchmarks: https://authors.elsevier.com/a/1cP%7ELc7X4-XPM; https://authors.elsevier.com/a/1cP%7ELc7X4-XPM; see table 4. The more time Python spends in native procedures, the more favorable the ratio is for Python; this is probably the reason why only around factor ten was measured here.

DoofusOfDeath 6y ago

I have serious reservations about headlines like this, but perhaps I'm being pedantic without realizing. My concern is that a particular mathematical function can be expressed in many different ways using Python and using C++. And practically speaking, it's impossible to be sure that you've created the fastest-possible implementation of that function in either language. And even then some implementations' performances are dependent on the compiler, supporting libraries, and underlying processor architecture. So AFAIK a headline like this leaves out way too many details to be generally true. Am I missing something?

Farmadupe 6y ago
I think given the naive algorithm of both implementations, and the fact the python and cpp are near transliterations of each other, the article isn't really trying to make the literal statement of the words of its title. Of course the relationship between language semantics and actual raw performance on real hardware is probably a neverending topic. I guess the article is more trying to make a statement along the lines of "here's how you benefit if you know python and pretend that means you know CPP too", (which seems like a fairly valid way to suck people into learning CPP to me)
- adsharma 6y ago
  shameless plug: https://github.com/adsharma/py2many https://github.com/adsharma/py2many I didn't write the python -> C++ transpiler, but added a few features to common and added basic support in 6 other languages. It should be possible to generate the C++ from python.
  - Rochus 6y ago
    Interesting. Do you have performance data (e.g. all CLBG Python benchmarks transpiled to C++ and run)? What's the speed-up?
    - adsharma 6y ago
      I haven't focused on performance yet. Thanks for the pointer! Gives me a concrete target to go after. https://github.com/adsharma/py2many/tree/main/tests/expected https://github.com/adsharma/py2many/tree/main/tests/expected is a good place to understand what types of code this system can transpile. Most languages are using templates/generics/auto etc. I added some type inference capabilities to common code and updated dart to take advantage of it. Should be possible for other languages as well. btrees python -> C++/rust seems feasible as a point of comparison. Hard problem: translating library calls from one language to another. I'm thinking of some type of a plugin system that app developers can provide mappings.

contravariant 6y ago

Although python does have from sympy import primepi primepi(1e6) which returns instantly.

joshka 6y ago
This is the real answer, although the algorithm used seems to use a sieve rather than a naive check for (x & i == 0) https://github.com/sympy/sympy/blob/219993505f88a8d6f825db1deaad939a28cbb78c/sympy/ntheory/generate.py#L417-L528 https://github.com/sympy/sympy/blob/219993505f88a8d6f825db1d...
- igouy 6y ago
  No, this is the real answer: https://web.archive.org/web/20010606131022/http://www.bagley.org/~doug/shootout/bench/sieve/ https://web.archive.org/web/20010606131022/http://www.bagley...

fdomingues 6y ago

C++ Is NOT 9.4 Times Faster Than Python in Prime Number Test I added 3 lines to the Python code and got it 10x faster: (venv) $ python prime.py Number of primes between 0 to 1000000 = 78498 Elapsed time: 6.502481937408447 (venv) $ python prime.py Number of primes between 0 to 1000000 = 78498 Elapsed time: 0.6258630752563477 Diff: 3c3,5 < --- > import numba > > @numba.njit 14a17 > @numba.njit