python - Python 中的解释与动态调度惩罚

Question

我观看了 Brandon Rhodes 关于 Cython 的演讲 - “EXE 之日来临”。

Brandon 在 09:30 提到，对于一段特定的短代码，跳过解释提供了 40% 的加速，而跳过分配和调度则提供了 574% 的加速(10:10)。

我的问题是 - 这是如何针对特定代码段进行测量的？是否需要手动提取底层的 c 命令，然后以某种方式让运行时运行它们？

这是一个非常有趣的观察，但我如何重新创建实验？

Answer 1

我们来看看这个python函数:

def py_fun(i,N,step):
     res=0.0
     while i<N:
        res+=i
        i+=step
     return res

并使用 ipython-magic 计时:

In [11]: %timeit py_fun(0.0,1.0e5,1.0)
10 loops, best of 3: 25.4 ms per loop

解释器将运行生成的字节码并解释它。但是，我们可以通过使用 cython for/cythonizing 完全相同的代码来删除解释器:

%load_ext Cython
%%cython
def cy_fun(i,N,step):
     res=0.0
     while i<N:
        res+=i
        i+=step
     return res

我们将它的速度提高了 50%:

In [13]: %timeit cy_fun(0.0,1.0e5,1.0)
100 loops, best of 3: 10.9 ms per loop

当我们查看生成的 c 代码时，我们看到直接调用正确的函数而无需解释/调用 ceval ，在剥离样板代码之后:

static PyObject *__pyx_pf_4test_cy_fun(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_i, PyObject *__pyx_v_N, PyObject *__pyx_v_step) {
  ...
  while (1) {
    __pyx_t_1 = PyObject_RichCompare(__pyx_v_i, __pyx_v_N, Py_LT); 
    ...
    __pyx_t_2 = __Pyx_PyObject_IsTrue(__pyx_t_1);
    ...
    if (!__pyx_t_2) break;
    ...
    __pyx_t_1 = PyNumber_InPlaceAdd(__pyx_v_res, __pyx_v_i);
    ...
    __pyx_t_1 = PyNumber_InPlaceAdd(__pyx_v_i, __pyx_v_step); 
  }
  ...
  return __pyx_r;
}

然而，这个 cython 函数处理 python 对象而不是 c 样式的浮点数，所以在函数 PyNumber_InPlaceAdd 中有必要弄清楚这些对象(整数、浮点数、其他什么？)到底是什么，并将这个调用分派(dispatch)给正确的函数来完成这项工作。

在 cython 的帮助下，我们还可以消除这种调度的需要，并直接调用浮点数的乘法:

 %%cython
 def c_fun(double i,double N, double step):
      cdef double res=0.0
      while i<N:
         res+=i
         i+=step
      return res

在这个版本中， i , N , step和 res是 c 风格的 double ，不再是 python 对象。所以不再需要调用像 PyNumber_InPlaceAdd 这样的调度函数但我们可以直接调用 + -运算符(operator)为 double :

static PyObject *__pyx_pf_4test_c_fun(CYTHON_UNUSED PyObject *__pyx_self, double __pyx_v_i, double __pyx_v_N, double __pyx_v_step) {
  ...
  __pyx_v_res = 0.0;  
  ... 
  while (1) {
    __pyx_t_1 = ((__pyx_v_i < __pyx_v_N) != 0);
    if (!__pyx_t_1) break;
    __pyx_v_res = (__pyx_v_res + __pyx_v_i);
    __pyx_v_i = (__pyx_v_i + __pyx_v_step);
  }
  ...
  return __pyx_r;
}

结果是:

In [15]: %timeit c_fun(0.0,1.0e5,1.0)
10000 loops, best of 3: 148 µs per loop

现在，与没有解释器但有调度的版本相比，这速度提高了近 100。

实际上，说 dispatch+allocation 是这里的瓶颈(因为消除它会导致几乎 100 倍的加速)是一个谬论:解释器负责超过 50% 的运行时间(15 毫秒)和分派(dispatch)和分配“仅”持续 10 毫秒。

但是，性能上比“解释器”和动态调度存在更多问题:Float 是不可变的，因此每次更改时都必须在垃圾收集器中创建和注册/注销新对象。

我们可以引入可变浮点数，它们就地改变并且不需要注册/取消注册:

%%cython
cdef class MutableFloat: 
 cdef double x      
 def __cinit__(self, x):
    self.x=x         
 def __iadd__(self, MutableFloat other):
    self.x=self.x+other.x
    return self
 def __lt__(MutableFloat self,  MutableFloat other):
    return self.x<other.x
 def __gt__(MutableFloat self, MutableFloat other):
    return self.x>other.x
 def __repr__(self):
    return str(self.x)

时间(现在我使用不同的机器，所以时间有点不同):

def py_fun(i,N,step,acc):
        while i<N:
             acc+=i
             i+=step
        return acc

%timeit py_fun(1.0, 5e5,1.0,0.0)
30.2 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each 
%timeit cy_fun(1.0, 5e5,1.0,0.0)
16.9 ms ± 612 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit i,N,step,acc=MutableFloat(1.0),MutableFloat(5e5),MutableFloat(1
    ...: .0),MutableFloat(0.0); py_fun(i,N,step,acc)
23 ms ± 254 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit i,N,step,acc=MutableFloat(1.0),MutableFloat(5e5),MutableFloat(1
...: .0),MutableFloat(0.0); cy_fun(i,N,step,acc)
11 ms ± 66.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

不要忘记重新初始化 i因为它是可变的!结果

            immutable       mutable
 py_fun       30ms           23ms
 cy_fun       17ms           11ms

因此，在有解释器的版本中注册/取消注册浮点数(我不确定没有其他东西在起作用)需要多达 7 毫秒(约 20%)，而在没有解释器的版本中则需要超过 33%。

现在的样子:

40% (13/30) 的时间被解释器使用

高达 33% 的时间用于动态调度

多达 20% 的时间用于创建/删除临时对象

约 1% 用于算术运算

另一个问题是数据的局部性，这对于内存带宽限制问题变得很明显:如果数据在一个接一个连续的内存地址线性处理，现代缓存可以很好地工作。这适用于循环 std::vector<> (或 array.array )，但不适用于循环遍历 python 列表，因为该列表由可以指向内存中任何位置的指针组成。

考虑以下 python 脚本:

#list.py
N=int(1e7)
lst=[0]*int(N)
for i in range(N):
  lst[i]=i
print(sum(lst)) 

和

#byte
N=int(1e7)
b=bytearray(8*N)
m=memoryview(b).cast('L') #reinterpret as an array of unsigned longs
for i in range(N):
  m[i]=i
print(sum(m))

他们都创建了 1e7整数，第一个版本 Python 整数，第二个版本是连续放置在内存中的低级 c-int。

有趣的部分是，这些脚本产生了多少缓存未命中 (D):

valgrind --tool=cachegrind python list.py 
...
D1  misses:        33,964,276  (   27,473,138 rd   +     6,491,138 wr)

相对

valgrind --tool=cachegrind python bytearray.py 
...
D1  misses:         4,796,626  (    2,140,357 rd   +     2,656,269 wr)

这意味着 python 整数的缓存未命中次数增加了 8 倍。部分原因是，python 整数需要超过 8 个字节(可能是 32 个字节，即因子 4)的内存和(也许不是 100% 确定，因为相邻的整数是在彼此之后创建的，所以机会很高，它们在内存中的某个地方一个接一个地存储，需要进一步调查)有些原因是它们在内存中没有对齐，因为 bytearray 的 c 整数就是这种情况。 .