Comparing Python, Go, and C++ on the $N$-Queens Problem

Python currently is the dominant language in the field of Machine Learning and gives easy access to powerful Deep Learning packages such as TensorFlow and PyTorch. However, it is known to be slow to perform some operations such as loops, which are not always easy to vectorize away. In such situations, one might consider switching to another language, such as C++ or the more recent Go language whose similarity to Python makes them potentially attractive replacements. In this note, we will argue that this may be necessary only rarely because the Numba python compiler [8] delivers performance close to those of C++ while preserving the compactness and ease of development that make Python such a powerful prototyping tool. Furthermore, it is easy to use. Once a set of Python functions has been identified as computationally intensive, one simply adds Numba decorators before their definitions to instruct Python to compile them while leaving the rest of the code largely unchanged.

To demonstrate this, we use the well known $N$-queens puzzle [1] as a benchmark. It involves placing $N$ chess queens on an $N\times N$ chessboard so that no two queens threaten each other. Fig. 1 depicts three solutions on a standard $8\times 8$ board and one on a larger $10\times 10$ one. We will focus on finding the number of solutions as a function of $N$. This is easy for small values of $N$ but quickly becomes computationally intractable for larger ones because the complexity of our algorithm is exponential with respect to $N$. There is no known formula for the exact number of solutions and, to date, $27$ is the larger value of $N$ for which the answer has been computed [12].

All our benchmarking code available is available online.¹¹1https://github.com/cvlab-epfl/n-queens-benchmark We welcome comments and suggestions for potential improvements. The article is also on ArXiv²²2https://arxiv.org/abs/2001.02491 and if you find it useful you can cite it. Thanks.

We started from the recursive algorithm described in [15] to compute one single solution of the 8-queens problem and translated it to Python. Our implementation relies on the fact that for two queens at board locations $(i_1,j_1)$ and $(i_2,j_2)$ not to be in conflict with each other, they must not be on the same row, on the same same column, or on the same diagonal. The first two mean that $i_1\ne i_2$ and $j_1\ne j_2$. The third holds if $i_1+i_2\ne j_1+j_2$ and $i_1-i_2\ne j_1-j_2$. In other words, the two diagonals going through any $(i,j)$ location are completely characterized by $i+j$ and $i-j$.

To exploit this, the function allQueensRec of Tab. 1 allocates boolean arrays col, dg1, and dg2 to keep track on which columns and diagonals are still available to place a new queen on an $n\times n$ board. It then invokes the recursive function allQueensRecursive. At recursion level $i$, for each $j$, it adds a queen at location $(i,j)$ if it is available, marks the column $j$ and the diagonals $i+j$ and $i-j$ as unavailable for additional queens, and calls itself for row $i+1$. The recursion ends in one of two ways. Either $i$ reaches $n$, meaning that all rows have been successfully filled, or no more queen can be added. If the first case, a counter is incremented. In the second case, nothing happens. In both cases, the program backtracks, undoes it earlier marking, and continues until all solutions have been found. This process could be sped up by exploiting the symmetries of the $N$-queens problems. However, this is not required for benchmarking purposes an we chose not to do it to keep the code simple. We also chose to use the C++ and Go naming convention for functions and variables, that is, we use allQueensRec instead of the more typical all_queens_rec, so that we can use the same names in all versions of the code we present.

In Fig. 2(a), the red curves depicts the computation time on a 2.9 GHz Quad-Core Intel Core i7 Mac running the Catalina operating system. In the top part of the figure, we plot the wall-clock time as as function of the board size $n$ using a standard scale. In the bottom part of the figure, we plot the same computation times using a log-scale instead, which results in an almost straight curve. This serves as a sanity check because the computational complexity grows exponentially with $n$. As allQueensRecursive performs loops, our vanilla Python implementation is inefficient. To remedy this, we used the Numba python compiler [8] as shown in Tab. 2. The code is almost unchanged except for adding a couple of Numba decorators and making the array types Numba compatible. Yet, as depicted by the green curve in Fig. 2(a), these minor modifications deliver a 33-fold increase in average computing speed of allQueensNmb over allQueensRec.

The Numba decorator njit() that appears in Tab. 2 is short for jit(nopython=True). It ensures that if the code compile without errors it will not invoke python while running and will therefore be fast. Additionally, we could have used jit(nopython=True,nogil=True) to instruct Numba to release the Python Global Interpreter Lock [3] while executing the function, thus allowing several versions to run simultaneously on threads of a single process, something that standard Python code cannot do because of the aforementioned lock. This does not have any significant impact on performance in a sequential execution scenario.

To further assess how effective the Python/Numba combination is, we rewrote the code in Go and C++, as shown in Tabs. 6 and 3. The short variable declarations make the Go code very similar to the Python code while being statically typed. The C++ code is slightly more verbose and one must remember to deallocate what has been allocated because there is no garbage collector. As shown in Fig. 4, this can be remedied by using more sophisticated containers such as the standard vector of C++ that are automatically deallocated at the end of the scope of their definition. Note that we used vector<uint8_t> as the type for our boolean arrays instead of the apparently more natural vector<bool>. We did this because the latter packs the bits densely and has to perform binary arithmetic to extract the requested bit for each access because memory can only be addressed down to whole bytes. In other words, it reduces memory usage at the expense of increased computation. As we are interested in speed, it is therefore more effective to explicitly use bytes (uint8_t) for our purpose. Nevertheless, we have verified that even when using byte vectors, the implementation of Fig. 4 incurs a small, but noticeable, performance decrease with respect to that of Tab. 3 and we therefore chose to stick with it, even though it is less elegant. In short, unlike Go, C++ gives the programmer great freedom to carry out tasks in many different ways but it takes a lot expertise to exploit it effectively and to avoid the many lurking pitfalls.

For example, unlike Python and Go, C++ does not automatically check that one does not write beyond the bounds of arrays. As a result, the buggy code of Tab. 5 runs but returns nonsensical values. We unintentionally made this mistake while translating the code from Python and, even though this is a short program, it took us a while to spot it. Of course, we could have used a tool such as valgrind, which would have detected the error, but this is far less convenient than being given a runtime warning. By default Numba does not perform bounds checks but they can be enabled using the decorator njit(boundscheck=True), which can be useful while debugging.

The cyan and purple curves of Fig. 2(a) depict the corresponding runtimes. The Numba, Go, and C++ curves are almost superposed. Closer examination of the raw numbers give in Tab. 15 in appendix show that C++ wins. Go in slower by about $6\%$ and Numba by $12\%$. Numba is slower mostly for low values of $n$, which suggests that the algorithm itself runs just as fast but that calling the Numba function from Python involves an overhead. While the observed differences are statistically significant based on the variances of the different runs, in our daily research practice, they are rarely large enough to justify giving up the development speed that Python provides and to contend with potential bugs such as the one discussed above.

However, there are optimizations that require the low-level control that C++ or Go can provide. For example, in all versions of the code presented here, the memory for the col, dg1, and dg2 arrays is allocated dynamically on the heap. The array sizes are decided at runtime and this code could in theory handle the $N$-queens problem for any value of $n$. However the computational cost is exponential and any value of $n>32$ is wildly impractical. If we accept to limit ourselves to $n<=32$, we can use fixed-sized arrays allocated on the stack by declaring them as var col[32]bool in Go or std::array<bool, 32> in C++. Unlike in the case discussed above, using bool instead uint8_t has no adverse effect. We have checked that the C++ code modified in this manner delivers a $20\%$ gain over Numba, instead of the earlier $12\%$. Potential explanations are that putting the arrays on the stack works better for the CPU cache or that the optimizer has an easier time reasoning about fixed-size stack arrays. In any event, this shows that C++, and Go, being closer to the hardware may be useful to fine-tune code under some circumstances.

Go can therefore be considered a promising alternative to both Python and C++ because its run-time checks make bugs such as the one of Fig. 5 easy to detect and correct. Furthermore, it is almost as concise as a Python and a little faster than Numba. However, some of its design features make it unwieldy in the prototyping role. For example, insisting that all variables and packages declared in a file be used makes sense for production code but is unhelpful when groping for a solution to a research problem: Commenting out a particular line of code, can mean many modifications in the file, which are unnecessary until a final solution has been found. Similarly not providing a full-fledged class-system can be understood as a way to discourage the writing of hard-to-maintain spaghetti code, which is commendable in production mode but unnecessarily rigid in prototyping mode.

Nearly every modern computer, including the one we used, has a multicore CPU and we can speed things up by running independent parts of the computation simultaneously on separate cores. In Go and C++, this can be done using multiple threads. Standard Python cannot do this due to the Global Interpreter Lock (GIL) [3] that we have already encountered in the previous section. Fortunately, there are several workarounds and we explored two of them:

1. Using Numba’s automatic parallelization [10]. Numba implements the ability to run loops in parallel as in Open Multi-Processing (OpenMP). The loop’s body is scheduled in separate threads and the system automatically takes care of data privatization and reduction.

2. Using a pool of processes. The pool distributes the computation into separate processes and tasks are sent to the available processors using a FIFO scheduling. Each process has its own interpreter and GIL, so they do not interfere. The price to pay is that objects need to be serialized and sent to the processes.

To test these two approaches, we parallelized the allQueensRec in a simple way. As shown in Tab. 7, we defined a new function allQueensCol that puts a queen in column $j$ of the first row and then invokes the function allQueensNumba defined in Tab. 2 starting at the second row instead of the first, as in allQueensRec. Summing the results for all possible values of $j$ yields the same results by performing $n$ independent computations. In Tab. 8, we integrate this code into two functions that spread the tasks across separate cores: allQueensPara uses the first method described above while allQueensPool uses the second. We will refer to them as para and pool respectively. Note how short the code is. Numba can take parallelization even further and produce functions that exploit the GPU. However, we did not explore this aspect in this study because our problem is not conducive to GPU processing.

In Fig. 2(b), we compare runtimes of the sequential Numba-compiled code of the previous section with our two parallelized versions. As before, the sequential code is depicted by the green curve while the two parallel versions are depicted by the red and blue curves, labeled para and pool respectively. para clearly delivers a significant improvement. However, for smaller values of $n$, we noted that para does not always fully use the 8 cores of our machines, which impacts its performance. For values of $n$ up to 13, the overhead involved in spawning new processes dominates the computational cost of pool and makes it uncompetitive. However, for $n>13$, this overhead becomes negligible with respect to the rest of the computation and pool starts dominating, albeit only by a small margin for large values of $n$, as can be seen in Tab. 15.

To again compare against Go and C++, we rewrote the code in these two languages using their built-in multi-threading capabilities, as shown in Tabs 9 and 10. Note that we used the template function std::async function to make the C++ version compact. The syntax is complex but gives access to the full power of lambda functions. The corresponding performance measurements are depicted by the cyan and purple curves of Fig. 2(b). As before for small values of $n$, para and pool are uncompetitive because the initial overhead is too large. However, for larger values of $n$ they catch up and eventually do better than Go and almost as well as C++. In short, there are corner cases in which it might pay to switch from Python to C++ or go but it is not clear how pervasive they are in our research practice.

In the two previous sections, we have argued that Numba is a powerful tool to painlessly compile potentially slow Python code so that it runs almost as fast as Go and C++. However, it also has limitations: Only a subset of Python [11] and NumPy [9] features are available inside compiled functions. Numba has a compilation mode that generates code able to handle all values as Python objects and uses the Python C API to perform all operations on such objects. Unfortunately, relying on this mode results in almost no performance gain over non-compiled code. This is why we used the njit() decorator in all our examples. It yields much faster code but requires that the native types of all values in the function can be inferred, which is not necessarily true in standard Python. Otherwise, the compilation fails.

In practice, this imposes an additional workload on the programmer who has to figure out what parts of the code are computationally expensive, encapsulate them in separate functions, and make sure that these functions can be compiled using the no-python mode that njit() enforces. This is probably why there are ongoing efforts to optimize whole Python programs such as PyPy [13]. Unfortunately, the results are not always compatible with libraries utilizing the C API, such as those routinely used in the field of scientific computing. As discussed in appendix, Julia is a potential alternative to Python/Numba that supports both high performance scientific computing and fast prototyping, is compiled, and could eventually address this problem.

As Computer Vision and Machine Learning researchers, we primarily need a language that allows us to test and refine ideas quickly while giving us access to as many mathematical, image processing, and machine learning libraries as possible. The latter spares us the need to reinvent the wheel every time we want to try something new. Maintainability and ability to work in large teams are secondary considerations as our code often stops evolving once the PhD student or post-doctoral researcher who wrote it leaves our lab. Before that happens, we typically make it publicly available to demonstrate that the ideas we published in conference and journals truly work and, in the end, that is often its main function.

Python fits that bill perfectly at the cost of being slow when performing operations such as loops. Fortunately, as we showed in this report, this shortcoming can be largely overcome by using the Numba compiler that delivers performance comparable to that of C++, which itself tends to be faster than Go. This suggests that a perfectly valid workflow is to first write and debug a program in ordinary Python; identify the computational bottlenecks; and use Numba to eliminate them. This will work most of the time. In the rare cases where it does not, we can rewrite the relevant section of the code in C++ and call it from Python, which can be achieved using Cython [2] or pybind11 [4]. Interestingly, this approach harkens to the standard way one used to work in the much older Common Lisp language, as discussed in the appendix.