Why is Python much slower than c++?

In other words, why do people focus on GIL？ Here, the standard line of the main question is a press bit Single threaded processing DFS ah …… Hardly any GIL Is there room for play ……

This eight Queen's DFS, my C++ The code does not add some evaluative pruning to 15 Need to calculate 18s about （ open O2 about 8.6 second , Basically consistent with the description of the subject ）, But what's certain is that your solution uses loops and recursion . What needs to be analyzed next is Python Slow in which detail , And whether it can be improved .

Here are two pieces of code to test , First of all Python Of ：

class="highlight">

#!/usr/bin/env python3
​
import time
​
def calc(n, i=0, cols=0, diags=0, trans=0):
if i == n:
return 1
else:
rt = 0
for j in range(n):
col = 1 << j
diag = 1 << (i - j + n - 1)
tran = 1 << (i + j)
if (col & cols) == 0 and (diag & diags) == 0 and (tran & trans) == 0:
rt += calc(n, i+1, cols | col, diags | diag, trans | tran)
return rt
​
if __name__ == '__main__':
t = time.time()
print(calc(13))
print(time.time() - t)

as well as C++ Code ：

#include <chrono>
#include <iostream>
​
using namespace std;
​
long calc(int n, int i = 0, long cols = 0, long diags = 0, long trans = 0) {
if (i == n) {
return 1;
} else {
long rt = 0;
for (int j = 0; j < n; j++) {
long col = (1 << j);
long diag = (1 << (i - j + n - 1));
long tran = (1 << (i + j));
if (!(col & cols) && !(diag & diags) && !(tran & trans)) {
rt += calc(n, i + 1, col | cols, diag | diags, tran | trans);
}
}
return rt;
}
}
​
int main() {
auto t = chrono::system_clock::now();
cout << calc(13) << endl;
cout << (chrono::system_clock::now() - t).count() * 1e-6 << endl;
return 0;
}

there C++ The code didn't follow OOP To write , How simple, how to come ……

The test machine configuration is Core i7 4870HQ, Compiler uses Clang++ 8.1.0,Python The interpreter is CPython 3.6.0. No test 15 The amount of data is only tested 13, because 15 It takes too much time ……

Since multithreading is not involved at all , That's basically like GIL It doesn't matter for half a dime .

about n=13,C++ The code ran 0.48 second . To make sure the compiler didn't work quietly , I specially made it -O0（ In fact, I drive O2 Can I get to 0.2 About seconds ）.Python ran 24 second .

For this example , The most direct impact is actually ：Python It is explained and executed sentence by sentence ,C++ Is to compile it into local code first , There is also type checking at compile time , There is no dynamic type 、 Dynamic check , And compiler optimization .

After that, we should consider whether we can improve the efficiency a little ？

Then according to the general law ,Python The cycle is slow , We can consider expanding the list instead ：

def calc(n, i=0, cols=0, diags=0, trans=0):
if i == n:
return 1
else:
return sum(
[
calc(n, i + 1, cols | (1 << j), diags | (1 << (i - j + n - 1)), trans | (1 << (i + j)))
for j in range(n)
if (cols & (1 << j)) == 0 and (diags & (1 << (i - j + n - 1))) == 0 and (trans & (1 << (i + j))) == 0
]
)

It should be faster , Real time also verified ： In this way Python The code needs to run 18 About seconds . There are still orders of magnitude differences , Did not solve the fundamental problem , But it shows one thing ,CPython in for loop In fact, the realization of is not happy at all .

Then consider , If we use other interpreters , Especially including JIT Interpreter , It will try to compile the code into local binary code and execute , At the same time, it can give some additional optimization , Will it be much better ？

So just try PyPy3(5.8.0-beta, Python 3.5.3), How fast the code can be ？

actually , Simply replace the interpreter , Switch to PyPy To do it , Originally this 24s Of Python The source code only needs 1s Around the . Just one JIT Can improve performance by an order of magnitude , Fully explain the official CPython The performance of the interpreter is really bad ……

PyPy Of JIT It's simple and pure , Not very radical , But if the same code can use better JIT, And higher performance Libraries , It can reflect a completely different poor performance . for example , If you use llvm do JIT, At the same time, we can use some mature math libraries for optimization . We know NumPy In this way C Expansion can greatly improve Python The performance of numerical calculation , Similarly, we can also use Cython Or use it directly C Write Python Expand to enhance computing power . But people are lazy , Rewriting the code is a bit of a hassle . about Python For this ecologically powerful thing , If your calculation code only uses numpy Simple structure and Python Its own standard structure , Use numba Probably the easiest and quickest way .

#!/usr/bin/env python3
​
import time
​
​
from numba import jit
​
​
@jit
def calc(n, i=0, cols=0, diags=0, trans=0):
if i == n:
return 1
else:
rt = 0
for j in range(n):
col = 1 << j
diag = 1 << (i - j + n - 1)
tran = 1 << (i + j)
​
if (col & cols) == 0 and (diag & diags) == 0 and (tran & trans) == 0:
rt += calc(n, i+1, cols | col, diags | diag, trans | tran)
return rt
​
​
​
if __name__ == '__main__':
t = time.time()
print(calc(13))
print(time.time() - t)

Here is just a simple addition of two lines of code ： from numba Import jit, use jit Decorate our calculation function . The running time of this code is directly reduced to 0.4s, and C++ Version of O0 The speed of the compiled program is almost the same . This still takes into account JIT In case of preheating . This code , If calculation 15 The scale of , It only needs 6.5s about , Even better than driving O2 Of C++ edition .

The reason is ,JIT It's not just about turning code into local machine code at run time , It will also try to optimize . If you use cProfile Something like that. Analyze the operation process , You can clearly see the optimization process .

That's all for this sharing