Python代码微优化之加快查找

501 查看

我将示范微优化（micro optimization）如何提升python代码5%的执行速度。5%！同时也会触怒任何维护你代码的人。

但实际上，这篇文章只是解释一下你偶尔会在标准库或者其他人的代码中碰到的代码。我们先看一个标准库的例子，collections.OrderedDict类：

def __setitem__(self, key, value, dict_setitem=dict.__setitem__):

if key not in self:

root = self.__root

last = root[0]

last[1] = root[0] = self.__map[key] = [last, root, key]

return dict_setitem(self, key, value)

注意最后一个参数：dict_setitem=dict.__setitem__。如果你仔细想就会感觉有道理。将值关联到键上，你只需要给__setitem__传递三个参数：要设置的键，与键关联的值，传递给内建dict类的__setitem__类方法。等会，好吧，也许最后一个参数没什么意义。

作用域查询

为了理解到底发生了什么，我们看下作用域。从一个简单问题开始：在一个python函数中，如果遇到了一个名为open的东西，python如何找出open的值？

# <GLOBAL: bunch of code here>

def myfunc():

# <LOCAL: bunch of code here>

with open('foo.txt', 'w') as f:

pass

简单作答：如果不知道GLOBAL和LOCAL的内容，你不可能确定open的值。概念上，python查找名称时会检查3个命名空间（简单起见忽略嵌套作用域）：

局部命名空间
全局命名空间
内建命名空间

所以在myfunc函数中，如果尝试查找open的值时，我们首先会检查本地命名空间，然后是全局命名空间，接着内建命名空间。如果在这3个命名空间中都找不到open的定义，就会引发NameError异常。

作用域查找的实现

上面的查找过程只是概念上的。这个查找过程的实现给予了我们探索实现的空间。

def foo():

a = 1

return a

def bar():

return a

def baz(a=1):

return a

我们看下每个函数的字节码：

>>> import dis

>>> dis.dis(foo)

2 0 LOAD_CONST 1 (1)

3 STORE_FAST 0 (a)

3 6 LOAD_FAST 0 (a)

9 RETURN_VALUE

>>> dis.dis(bar)

2 0 LOAD_GLOBAL 0 (a)

3 RETURN_VALUE

>>> dis.dis(baz)

2 0 LOAD_FAST 0 (a)

3 RETURN_VALUE

注意foo和bar的区别。我们立即就可以看到，在字节码层面，python已经判断了什么是局部变量、什么不是，因为foo使用LOAD_FAST，而bar使用LOAD_GLOBAL。

我们不会具体阐述python的编译器如何知道何时生成何种字节码（也许那是另一篇文章的范畴了），但足以理解，python在执行函数时已经知道进行何种类型的查找。

另一个容易混淆的是，LOAD_GLOBAL既可以用于全局，也可以用于内建命名空间的查找。忽略嵌套作用域的问题，你可以认为这是“非局部的”。对应的C代码大概是[1]：

case LOAD_GLOBAL:

v = PyObject_GetItem(f->f_globals, name);

if (v == NULL) {

v = PyObject_GetItem(f->f_builtins, name);

if (v == NULL) {

if (PyErr_ExceptionMatches(PyExc_KeyError))

format_exc_check_arg(

PyExc_NameError,

NAME_ERROR_MSG, name);

goto error;

}

PUSH(v);

即使你从来没有看过CPython的C代码，上面的代码已经相当直白了。首先，检查我们查找的键名是否在f->f_globals（全局字典）中，然后检查名称是否在f->f_builtins（内建字典）中，最后，如果上面两个位置都没找到，就会抛出NameError异常。

将常量绑定到局部作用域

现在我们再看最开始的代码例子，就会理解最后一个参数其实是将一个函数绑定到局部作用域中的一个函数上。具体是通过将dict.__setitem__赋值为参数的默认值。这里还有另一个例子：

def not_list_or_dict(value):

return not (isinstance(value, dict) or isinstance(value, list))

def not_list_or_dict(value, _isinstance=isinstance, _dict=dict, _list=list):

return not (_isinstance(value, _dict) or _isinstance(value, _list))

这里我们做同样的事情，把本来将会在内建命名空间中的对象绑定到局部作用域中去。因此，python将会使用LOCAL_FAST而不是LOAD_GLOBAL（全局查找）。那么这到底有多快呢？我们做个简单的测试：

$ python -m timeit -s 'def not_list_or_dict(value): return not (isinstance(value, dict) or isinstance(value, list))' 'not_list_or_dict(50)'

1000000 loops, best of 3: 0.48 usec per loop

$ python -m timeit -s 'def not_list_or_dict(value, _isinstance=isinstance, _dict=dict, _list=list): return not (_isinstance(value, _dict) or _isinstance(value, _list))' 'not_list_or_dict(50)'

1000000 loops, best of 3: 0.423 usec per loop

换句话说，大概有11.9%的提升 [2]。比我在文章开始处承诺的5%还多！

还有更多内涵

可以合理地认为，速度提升在于LOAD_FAST读取局部作用域，而LOAD_GLOBAL在检查内建作用域之前会先首先检查全局作用域。上面那个示例函数中，isinstance、dict、list都位于内建命名空间。

但是，还有更多。我们不仅可以使用LOAD_FAST跳过多余的查找，它也是一种不同类型的查找。

上面C代码片段给出了LOAD_GLOBAL的代码，下面是LOAD_FAST的：

case LOAD_FAST:

PyObject *value = fastlocal[oparg];

if (value == NULL) {

format_exc_check_arg(PyExc_UnboundLocalError,

UNBOUNDLOCAL_ERROR_MSG,

PyTuple_GetItem(co->co_varnames, oparg));

goto error;

}

Py_INCREF(value);

PUSH(value);

FAST_DISPATCH()

我们通过索引一个数组获取局部值。虽然没有直接出现，但是oparg只是那个数组的一个索引。

现在听起来才合理。我们第一个版本的not_list_or_dict要进行4个查询，每个名称都位于内建命名空间，它们只有在查找全局命名空间之后才会查询。这就是8个字典键的查询操作了。相比之下，not_list_or_dict的第二版中，直接索引C数组4次，底层全部使用LOAD_FAST。这就是为什么局部查询更快的原因。

总结

现在当下次你在其他人代码中看到这种例子，就会明白了。

最后，除非确实需要，请不要在具体应用中进行这类优化。而且大部分时间你都没必要做。但是如果时候到了，你需要挤出最后一点性能，就需要搞懂这点。

脚注

[1]注意，为了更易读，上面的代码中我去掉了一些性能优化。真正的代码稍微有点复杂。

[2]示例函数事实上没有做什么有价值的东西，也没进行IO操作，大部分是受python VM循环的限制。