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

Question

我看过布兰登·罗德斯（Brandon Rhodes）关于Cython的谈话-“ EXE的日子即将到来”。

布兰登在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来对解释器进行剪切/将其代码化：

%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样式的float，因此在该函数PyNumber_InPlaceAdd中必须弄清楚这些对象（整数，float等）的真正含义，并将此调用分派给正确的函数，会做的工作。

在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风格的双打，不再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。

实际上，说调度+分配是瓶颈（因为消除它会导致速度几乎提高100倍）是一个谬论：解释器负责运行时间的50％以上（15毫秒），而分派和分配“仅” 10ms。

但是，除了性能之外，还有比“解释器”和动态调度更多的问题：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

因此，在具有解释器的版本中，注册/取消注册浮动消息最多需要7ms（大约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-integers，第二个是低级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-
integers的缓存丢失次数增加了8倍。部分原因是因为python整数需要超过8个字节（可能是32个字节，即因数4）的内存和（也许不是100％肯定的）内存，因为相邻的整数是彼此相继创建的，因此机会很高，则将它们彼此存储在内存中的某个位置，需要进一步研究），这是由于事实的原因，即它们的c整数在内存中未对齐bytearray。