继承对属性访问速度的影响

在华蟒用户组中有人发问道：

网上看到文章介绍“Method Resolution Order”，说是Python访问对象成员是，先检查当前类的__dict__，查看成员是否存在，如果当前不存在，则查找父类的__dict__。有点类似javascript的原型链查找。这么一来岂不是，一旦对象继承链比较长，访问基类的成员性能会很差？

测试属性访问速度

那么先来测试一下速度吧。

class Base(object):
    def get_x(self):
        return 10

    def get_y(self):
        return 100
    
    def test(self):
        return 0

# 一个很大的属性字典
from string import ascii_lowercase
import itertools
d = {}
for c in itertools.product(ascii_lowercase, ascii_lowercase):
    d["".join(c)] = c

# 继承1000次，所有创建的子类都复制一份属性字典
classes = [Base]
for i in xrange(1000):
    classes.append(type("C%d"%i, (classes[-1],), d.copy()))

c0 = Base
c1 = classes[-1]

上面的程序先创建一个基类Base，然后通过循环调用type()创建1000层子类。下面我们查看c1.mro()的长度，c1的确是第1001层子类。

len(c1.mro())

1002

下面我们测试通过基类c0和最底层子类c1访问get_x的速度：

%timeit c0.get_x
%timeit c1.get_x

10000000 loops, best of 3: 171 ns per loop
10000000 loops, best of 3: 175 ns per loop

令人感到吃惊的是，通过子类几乎看不到任何速度损失，Python一定做了什么优化。于是我又做了下面的测试：

%timeit c0.get_x, c0.get_y
%timeit c1.get_x, c1.get_y

1000000 loops, best of 3: 715 ns per loop
1000 loops, best of 3: 283 us per loop

如果交替访问get_x和get_y，子类的访问速度一下子就降下来了。是不是Python会保存最近访问的那次属性呢？于是又做了如下测试：

%timeit c0.get_x, c0.test
%timeit c1.get_x, c1.test

1000000 loops, best of 3: 388 ns per loop
1000000 loops, best of 3: 406 ns per loop

我又随便测试了其它一些属性组合，只有get_x和get_y一起访问时，会降低访问速度，那么get_x和get_y有什么特殊的地方呢？

hash("get_x"), hash("get_y")

(1461240580, 1461240581)

我们看到二者的hash值只相差1，这也许就是它们一起访问速度慢的原因吧。至于具体原因何在，只有查看Python的源代码了。

源码分析

关于从object继承的新类的代码，可以在typeobject.c中找到。在该文件的开头就可以看到有关属性缓存的说明和代码：

/* Support type attribute cache */

/* The cache can keep references to the names alive for longer than
   they normally would.  This is why the maximum size is limited to
   MCACHE_MAX_ATTR_SIZE, since it might be a problem if very large
   strings are used as attribute names. */
#define MCACHE_MAX_ATTR_SIZE    100
#define MCACHE_SIZE_EXP         10
#define MCACHE_HASH(version, name_hash)                                 \
        (((unsigned int)(version) * (unsigned int)(name_hash))          \
         >> (8*sizeof(unsigned int) - MCACHE_SIZE_EXP))
#define MCACHE_HASH_METHOD(type, name)                                  \
        MCACHE_HASH((type)->tp_version_tag,                     \
                    ((PyStringObject *)(name))->ob_shash)
#define MCACHE_CACHEABLE_NAME(name)                                     \
        PyString_CheckExact(name) &&                            \
        PyString_GET_SIZE(name) <= MCACHE_MAX_ATTR_SIZE

struct method_cache_entry {
    unsigned int version;
    PyObject *name;             /* reference to exactly a str or None */
    PyObject *value;            /* borrowed */
};

static struct method_cache_entry method_cache[1 << MCACHE_SIZE_EXP];
static unsigned int next_version_tag = 0;

由上面的代码不难看出，Python使用全局数组method_cache对 1<<10=1024 条属性进行缓存。而在接下来的_PyType_Lookup()中我们可以看到如何使用改数组进行缓存查询：

PyObject *
_PyType_Lookup(PyTypeObject *type, PyObject *name)
{
    Py_ssize_t i, n;
    PyObject *mro, *res, *base, *dict;
    unsigned int h;

    if (MCACHE_CACHEABLE_NAME(name) &&
        PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG)) {
        /* fast path */
        h = MCACHE_HASH_METHOD(type, name);
        if (method_cache[h].version == type->tp_version_tag &&
            method_cache[h].name == name)
            return method_cache[h].value;
    }

它通过MCACHE_HASH_METHOD从类和属性名计算出一个下标h，然后检测method_cache[h]中缓存的内容是否和要查询类和属性名的一致，如果一致的话就直接返回属性值，而无须通过继承树往上层搜索属性。下面让我们再一次查看MCACHE_HASH_METHOD的代码：

 #define MCACHE_HASH(version, name_hash)                                 \
            (((unsigned int)(version) * (unsigned int)(name_hash))       \
             >> (8*sizeof(unsigned int) - MCACHE_SIZE_EXP))
 #define MCACHE_HASH_METHOD(type, name)                                  \
            MCACHE_HASH((type)->tp_version_tag,                          \
                        ((PyStringObject *)(name))->ob_shash)

它计算下标的方式就是取类的版本标签tp_version_tag与属性名的hash值的乘积的高10位bit。当类相同，hash值只相差1时，通过MCACHE_HASH计算出来的下标相同，于是前面的测试中，c1.get_x和c1.get_y被缓存到同一位置，交替访问它们只能每次都通过继承树搜索属性，从而降低了属性的访问速度。

为什么取高位

对于get_x和get_y来说，如果取低位作为下标就不会出现下标冲突问题了。那么Python是基于何种考虑取高位作为下标呢？在讨论组中Xidorn Quan给出了如下线索：

现在 Python 代码中使用的是这一个版本的 PyPy 的 hash 函数：。这个提交将类似于我改的那个版本的 hash 函数替换为了现在我们看到的那个 hash 函数：

-        MASK = (1 << space.config.objspace.std.methodcachesizeexp) - 1
-        #method_hash = (id(version_tag) ^ position_hash ^ hash(name)) & MASK
-        method_hash = ((id(version_tag) >> 3) ^ hash(name)) & MASK
+        SHIFT = r_uint.BITS - space.config.objspace.std.methodcachesizeexp
+        method_hash = r_uint(intmask(id(version_tag) * hash(name))) >> SHIFT

理由是：Improve the hash function used by the method cache.Seems to give good speed-ups on some of our benchmarks.

当然我们无从得知这个 benchmark 到底是什么，不过它是这么说的……，PyPy 里面现在版本的 hash 算法也已经和这个不一样了，或许可以考虑测试一下。

结束语

Python的确需要通过继承树搜索属性，但是它会缓存最近的1024个搜索结果，如果没有下标冲突问题，这样做能极大提高循环中对某几个属性的访问。但是如果存在下标冲突，则访问速度又降回到无缓存的情况，会有一定的速度损失。如果你真的很在乎属性访问速度，那么可以在进行大量循环之前，将所有要访问的属性用局域变量进行缓存，这应该是最快捷的方案了。