|Python As Fast As Go and C++ The Queens Prove It|
|Written by Mike James|
|Monday, 20 January 2020|
Python is an attractive language with a good community for support and development, but is the price for this speed? Machine learning researchers at EPFL have put it to the test and found it not wanting.
The N-queens problem is a long standing exercise in algorithmic skill. All you have to do is place n queens on an n x n chessboard so that none of the queens is attacking another. The classical, and best known, solution is a recursive approach that positions each queen in turn taking into account the queens already placed. If at any point a queen cannot be placed then the function backtracks and tries a new position for an earlier queen.
The problem gives us an opportunity for comparisons, in particular Go vs Python.
Implementing the algorithmn in Python, Go and C++ quickly demonstrated that Python was slow, but included error checking that was missing from C++. To see if things could be improved, the same code was compiled using the Numba Python compiler. C++ was still the winner, with Go slower by 6% and Numba Python slower by 12%
The researchers argue that the Numba Python is fast enough to make it work in a research context because of the speed of prototyping code. Go is also attractive, but it is argued that it has many features that make it less easy to use when first experimenting with code. It is interesting to note that Julia is also in the "fast" group but this information is relegated to an appendix, where we find the comment:
"This make Julia a potentially attractive alternative to Python/Numba. Unfortunately, there are some significant obstacles to its adoption. First, it still is a new language. Some important features remain experimental and the number of third-party libraries is limited, whereas Python gives access to a wealth of powerful libraries, such as the deep learning ones that have become absolutely central to our research activities. Furthermore, it features some design choices that differentiate it from currently popular languages, such as 1-indexed arrays and multiple-dispatch instead of classes. Whether or not these choices are wise, they make it harder to switch from an established language like Python to Julia."
More realistically, for scientific use, the team then went on to compare parallel implementations which Numba made easier, even if standard Python cannot be used in this way. Two approaches to parallelizing the Python were tried - Para and Pool and these were compared against the original Numba code and Go and C++.
You can see that the automatic parallelization performed by Numba is in the same league as that done by Go and C++. However, you can see that the C++ is still faster but not by much.
The conclusion is:
"In this report, we use the well-known N-queens puzzle as a benchmark to show that once compiled using the Numba compiler it becomes competitive with C++ and Go in terms of execution speed while still allowing for very fast prototyping. This is true of both sequential and parallel programs. In most cases that arise in an academic environment, it therefore makes sense to develop in ordinary Python, identify computational bottlenecks, and use Numba to remove them."
So Python it is...
Comparing Python, Go, and C++ on the N-Queens Problem
Pascal Fua, and Krzysztof Lis
N Queens Completion Is NP Complete
How Fast Can You Number Crunch In Python
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Wednesday, 16 March 2022 )|