为什么 Python 中的子类化会减慢速度？
Why does subclassing in Python slow things down so much?
我正在开发一个扩展 dict 的简单 class，我意识到 pickle 的键查找和使用 非常 慢。
我认为这是我的 class 的问题，所以我做了一些简单的基准测试：
(venv) marco@buzz:~/sources/python-frozendict/test$ python --version
Python 3.9.0a0
(venv) marco@buzz:~/sources/python-frozendict/test$ sudo pyperf system tune --affinity 3
[sudo] password for marco:
Tune the system configuration to run benchmarks
Actions
=======
CPU Frequency: Minimum frequency of CPU 3 set to the maximum frequency
System state
============
CPU: use 1 logical CPUs: 3
Perf event: Maximum sample rate: 1 per second
ASLR: Full randomization
Linux scheduler: No CPU is isolated
CPU Frequency: 0-3=min=max=2600 MHz
CPU scaling governor (intel_pstate): performance
Turbo Boost (intel_pstate): Turbo Boost disabled
IRQ affinity: irqbalance service: inactive
IRQ affinity: Default IRQ affinity: CPU 0-2
IRQ affinity: IRQ affinity: IRQ 0,2=CPU 0-3; IRQ 1,3-17,51,67,120-131=CPU 0-2
Power supply: the power cable is plugged
Advices
=======
Linux scheduler: Use isolcpus=<cpu list> kernel parameter to isolate CPUs
Linux scheduler: Use rcu_nocbs=<cpu list> kernel parameter (with isolcpus) to not schedule RCU on isolated CPUs
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
x = {0:0, 1:1, 2:2, 3:3, 4:4}
' 'x[4]'
.........................................
Mean +- std dev: 35.2 ns +- 1.8 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
class A(dict):
pass
x = A({0:0, 1:1, 2:2, 3:3, 4:4})
' 'x[4]'
.........................................
Mean +- std dev: 60.1 ns +- 2.5 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
x = {0:0, 1:1, 2:2, 3:3, 4:4}
' '5 in x'
.........................................
Mean +- std dev: 31.9 ns +- 1.4 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
class A(dict):
pass
x = A({0:0, 1:1, 2:2, 3:3, 4:4})
' '5 in x'
.........................................
Mean +- std dev: 64.7 ns +- 5.4 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python
Python 3.9.0a0 (heads/master-dirty:d8ca2354ed, Oct 30 2019, 20:25:01)
[GCC 9.2.1 20190909] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> class A(dict):
... def __reduce__(self):
... return (A, (dict(self), ))
...
>>> timeit("dumps(x)", """
... from pickle import dumps
... x = {0:0, 1:1, 2:2, 3:3, 4:4}
... """, number=10000000)
6.70694484282285
>>> timeit("dumps(x)", """
... from pickle import dumps
... x = A({0:0, 1:1, 2:2, 3:3, 4:4})
... """, number=10000000, globals={"A": A})
31.277778962627053
>>> timeit("loads(x)", """
... from pickle import dumps, loads
... x = dumps({0:0, 1:1, 2:2, 3:3, 4:4})
... """, number=10000000)
5.767975459806621
>>> timeit("loads(x)", """
... from pickle import dumps, loads
... x = dumps(A({0:0, 1:1, 2:2, 3:3, 4:4}))
... """, number=10000000, globals={"A": A})
22.611666693352163
结果真是出乎意料。虽然密钥查找速度慢 2 倍，但 pickle 速度 5x。
怎么会这样？其他方法，如 get()、__eq__() 和 __init__()，以及 keys()、values() 和 items() 的迭代速度与 dict.
EDIT: 我看了一下Python 3.9的源代码，在Objects/dictobject.c中似乎是__getitem__()方法由 dict_subscript() 实施。并且 dict_subscript() 只有在密钥丢失时才会减慢 subclasses，因为 subclass 可以实现 __missing__() 并且它会尝试查看它是否存在。但是基准测试使用的是现有密钥。
但我注意到一些事情：__getitem__() 是用标志 METH_COEXIST 定义的。还有 __contains__()，另一种慢 2 倍的方法，具有相同的标志。来自 official documentation:
The method will be loaded in place of existing definitions. Without
METH_COEXIST, the default is to skip repeated definitions. Since slot
wrappers are loaded before the method table, the existence of a
sq_contains slot, for example, would generate a wrapped method named
contains() and preclude the loading of a corresponding PyCFunction with the same name. With the flag defined, the PyCFunction will be
loaded in place of the wrapper object and will co-exist with the slot.
This is helpful because calls to PyCFunctions are optimized more than
wrapper object calls.
所以如果我没理解错的话，理论上METH_COEXIST应该会加快速度，但似乎适得其反。为什么？
编辑 2：我发现了更多东西。
__getitem__() 和 __contains()__ 被标记为 METH_COEXIST，因为它们在 PyDict_Type 两次 中被声明。
它们都出现在插槽 tp_methods 中一次，它们被明确声明为 __getitem__() 和 __contains()__。但是 official documentation 说 tp_methods 是 而不是 由 subclasses.
继承
所以dict的子class不调用__getitem__()，而是调用子槽mp_subscript。实际上，mp_subscript 包含在插槽 tp_as_mapping 中，它允许子 class 继承其子插槽。
问题是__getitem__()和mp_subscript都使用了相同的函数，dict_subscript。有没有可能只是它的遗传方式减慢了它的速度？
索引和 in 在 dict subclasses 中较慢，因为 dict 优化与逻辑 subclasses 之间的交互不良用于继承 C 插槽。这应该是可以修复的，但不是从你这边开始的。
CPython 实现有两组用于运算符重载的钩子。有 Python 级别的方法，如 __contains__ 和 __getitem__，但在类型对象的内存布局中也有一组单独的 C 函数指针槽。通常，Python 方法将是 C 实现的包装器，或者 C 插槽将包含一个搜索和调用 Python 方法的函数。 C槽直接实现操作效率更高，因为C槽是Python实际访问的
用 C 编写的映射实现了 C 插槽 sq_contains 和 mp_subscript 以提供 in 和索引。通常，Python 级别的 __contains__ 和 __getitem__ 方法将自动生成为 C 函数的包装器，但 dict class 具有 explicit implementations __contains__ 和 __getitem__，因为显式实现比生成的包装器快一点：
static PyMethodDef mapp_methods[] = {
DICT___CONTAINS___METHODDEF
{"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
getitem__doc__},
...
（实际上，显式 __getitem__ 实现与 mp_subscript 实现具有相同的功能，只是使用了不同类型的包装器。）
通常，subclass 会继承其父级的 C 级钩子实现，如 sq_contains 和 mp_subscript，而 subclass 将同样快作为超级class。但是，update_one_slot 中的逻辑通过尝试通过 MRO 搜索查找生成的包装器方法来查找父实现。
dict 没有 为 sq_contains 和 mp_subscript 生成包装器，因为它提供了明确的 __contains__ 和 __getitem__ 实现。
不是继承sq_contains和mp_subscript，update_one_slot最终给出了子class sq_contains和mp_subscript实现MRO 搜索 __contains__ 和 __getitem__ 并调用它们。这比直接继承 C 插槽效率低得多。
解决此问题需要更改 update_one_slot 实施。
除了我上面描述的之外，dict_subscript 还会查找 __missing__ for dict subclasses，所以修复插槽继承问题不会使 subclass 在查找速度方面完全与 dict 本身相当，但它应该使它们更接近。
至于 pickling，在 dumps 方面，pickle 实现有一个 dedicated fast path 用于字典，而字典 subclass 通过 object.__reduce_ex__ 和 save_reduce.
在 loads 方面，时间差异主要来自额外的操作码和查找以检索和实例化 __main__.A class，而字典有一个专用的 pickle 操作码制作一个新的字典。如果我们比较泡菜的反汇编：
In [26]: pickletools.dis(pickle.dumps({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}))
0: \x80 PROTO 4
2: \x95 FRAME 25
11: } EMPTY_DICT
12: \x94 MEMOIZE (as 0)
13: ( MARK
14: K BININT1 0
16: K BININT1 0
18: K BININT1 1
20: K BININT1 1
22: K BININT1 2
24: K BININT1 2
26: K BININT1 3
28: K BININT1 3
30: K BININT1 4
32: K BININT1 4
34: u SETITEMS (MARK at 13)
35: . STOP
highest protocol among opcodes = 4
In [27]: pickletools.dis(pickle.dumps(A({0: 0, 1: 1, 2: 2, 3: 3, 4: 4})))
0: \x80 PROTO 4
2: \x95 FRAME 43
11: \x8c SHORT_BINUNICODE '__main__'
21: \x94 MEMOIZE (as 0)
22: \x8c SHORT_BINUNICODE 'A'
25: \x94 MEMOIZE (as 1)
26: \x93 STACK_GLOBAL
27: \x94 MEMOIZE (as 2)
28: ) EMPTY_TUPLE
29: \x81 NEWOBJ
30: \x94 MEMOIZE (as 3)
31: ( MARK
32: K BININT1 0
34: K BININT1 0
36: K BININT1 1
38: K BININT1 1
40: K BININT1 2
42: K BININT1 2
44: K BININT1 3
46: K BININT1 3
48: K BININT1 4
50: K BININT1 4
52: u SETITEMS (MARK at 31)
53: . STOP
highest protocol among opcodes = 4
我们看到两者之间的区别在于第二个 pickle 需要一大堆操作码来查找 __main__.A 并实例化它，而第一个 pickle 只是 EMPTY_DICT 来获得一个空字典之后，两个 pickle 将相同的键和值压入 pickle 操作数堆栈和 运行 SETITEMS.
我正在开发一个扩展 dict 的简单 class，我意识到 pickle 的键查找和使用 非常 慢。
我认为这是我的 class 的问题，所以我做了一些简单的基准测试：
(venv) marco@buzz:~/sources/python-frozendict/test$ python --version
Python 3.9.0a0
(venv) marco@buzz:~/sources/python-frozendict/test$ sudo pyperf system tune --affinity 3
[sudo] password for marco:
Tune the system configuration to run benchmarks
Actions
=======
CPU Frequency: Minimum frequency of CPU 3 set to the maximum frequency
System state
============
CPU: use 1 logical CPUs: 3
Perf event: Maximum sample rate: 1 per second
ASLR: Full randomization
Linux scheduler: No CPU is isolated
CPU Frequency: 0-3=min=max=2600 MHz
CPU scaling governor (intel_pstate): performance
Turbo Boost (intel_pstate): Turbo Boost disabled
IRQ affinity: irqbalance service: inactive
IRQ affinity: Default IRQ affinity: CPU 0-2
IRQ affinity: IRQ affinity: IRQ 0,2=CPU 0-3; IRQ 1,3-17,51,67,120-131=CPU 0-2
Power supply: the power cable is plugged
Advices
=======
Linux scheduler: Use isolcpus=<cpu list> kernel parameter to isolate CPUs
Linux scheduler: Use rcu_nocbs=<cpu list> kernel parameter (with isolcpus) to not schedule RCU on isolated CPUs
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
x = {0:0, 1:1, 2:2, 3:3, 4:4}
' 'x[4]'
.........................................
Mean +- std dev: 35.2 ns +- 1.8 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
class A(dict):
pass
x = A({0:0, 1:1, 2:2, 3:3, 4:4})
' 'x[4]'
.........................................
Mean +- std dev: 60.1 ns +- 2.5 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
x = {0:0, 1:1, 2:2, 3:3, 4:4}
' '5 in x'
.........................................
Mean +- std dev: 31.9 ns +- 1.4 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
class A(dict):
pass
x = A({0:0, 1:1, 2:2, 3:3, 4:4})
' '5 in x'
.........................................
Mean +- std dev: 64.7 ns +- 5.4 ns
(venv) marco@buzz:~/sources/python-frozendict/test$ python
Python 3.9.0a0 (heads/master-dirty:d8ca2354ed, Oct 30 2019, 20:25:01)
[GCC 9.2.1 20190909] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> class A(dict):
... def __reduce__(self):
... return (A, (dict(self), ))
...
>>> timeit("dumps(x)", """
... from pickle import dumps
... x = {0:0, 1:1, 2:2, 3:3, 4:4}
... """, number=10000000)
6.70694484282285
>>> timeit("dumps(x)", """
... from pickle import dumps
... x = A({0:0, 1:1, 2:2, 3:3, 4:4})
... """, number=10000000, globals={"A": A})
31.277778962627053
>>> timeit("loads(x)", """
... from pickle import dumps, loads
... x = dumps({0:0, 1:1, 2:2, 3:3, 4:4})
... """, number=10000000)
5.767975459806621
>>> timeit("loads(x)", """
... from pickle import dumps, loads
... x = dumps(A({0:0, 1:1, 2:2, 3:3, 4:4}))
... """, number=10000000, globals={"A": A})
22.611666693352163
结果真是出乎意料。虽然密钥查找速度慢 2 倍，但 pickle 速度 5x。
怎么会这样？其他方法，如 get()、__eq__() 和 __init__()，以及 keys()、values() 和 items() 的迭代速度与 dict.
EDIT: 我看了一下Python 3.9的源代码，在Objects/dictobject.c中似乎是__getitem__()方法由 dict_subscript() 实施。并且 dict_subscript() 只有在密钥丢失时才会减慢 subclasses，因为 subclass 可以实现 __missing__() 并且它会尝试查看它是否存在。但是基准测试使用的是现有密钥。
但我注意到一些事情：__getitem__() 是用标志 METH_COEXIST 定义的。还有 __contains__()，另一种慢 2 倍的方法，具有相同的标志。来自 official documentation:
The method will be loaded in place of existing definitions. Without METH_COEXIST, the default is to skip repeated definitions. Since slot wrappers are loaded before the method table, the existence of a sq_contains slot, for example, would generate a wrapped method named contains() and preclude the loading of a corresponding PyCFunction with the same name. With the flag defined, the PyCFunction will be loaded in place of the wrapper object and will co-exist with the slot. This is helpful because calls to PyCFunctions are optimized more than wrapper object calls.
所以如果我没理解错的话，理论上METH_COEXIST应该会加快速度，但似乎适得其反。为什么？
编辑 2：我发现了更多东西。
__getitem__() 和 __contains()__ 被标记为 METH_COEXIST，因为它们在 PyDict_Type 两次 中被声明。
它们都出现在插槽 tp_methods 中一次，它们被明确声明为 __getitem__() 和 __contains()__。但是 official documentation 说 tp_methods 是 而不是 由 subclasses.
所以dict的子class不调用__getitem__()，而是调用子槽mp_subscript。实际上，mp_subscript 包含在插槽 tp_as_mapping 中，它允许子 class 继承其子插槽。
问题是__getitem__()和mp_subscript都使用了相同的函数，dict_subscript。有没有可能只是它的遗传方式减慢了它的速度？
索引和 in 在 dict subclasses 中较慢，因为 dict 优化与逻辑 subclasses 之间的交互不良用于继承 C 插槽。这应该是可以修复的，但不是从你这边开始的。
CPython 实现有两组用于运算符重载的钩子。有 Python 级别的方法，如 __contains__ 和 __getitem__，但在类型对象的内存布局中也有一组单独的 C 函数指针槽。通常，Python 方法将是 C 实现的包装器，或者 C 插槽将包含一个搜索和调用 Python 方法的函数。 C槽直接实现操作效率更高，因为C槽是Python实际访问的
用 C 编写的映射实现了 C 插槽 sq_contains 和 mp_subscript 以提供 in 和索引。通常，Python 级别的 __contains__ 和 __getitem__ 方法将自动生成为 C 函数的包装器，但 dict class 具有 explicit implementations __contains__ 和 __getitem__，因为显式实现比生成的包装器快一点：
static PyMethodDef mapp_methods[] = {
DICT___CONTAINS___METHODDEF
{"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
getitem__doc__},
...
（实际上，显式 __getitem__ 实现与 mp_subscript 实现具有相同的功能，只是使用了不同类型的包装器。）
通常，subclass 会继承其父级的 C 级钩子实现，如 sq_contains 和 mp_subscript，而 subclass 将同样快作为超级class。但是，update_one_slot 中的逻辑通过尝试通过 MRO 搜索查找生成的包装器方法来查找父实现。
dict 没有 为 sq_contains 和 mp_subscript 生成包装器，因为它提供了明确的 __contains__ 和 __getitem__ 实现。
不是继承sq_contains和mp_subscript，update_one_slot最终给出了子class sq_contains和mp_subscript实现MRO 搜索 __contains__ 和 __getitem__ 并调用它们。这比直接继承 C 插槽效率低得多。
解决此问题需要更改 update_one_slot 实施。
除了我上面描述的之外，dict_subscript 还会查找 __missing__ for dict subclasses，所以修复插槽继承问题不会使 subclass 在查找速度方面完全与 dict 本身相当，但它应该使它们更接近。
至于 pickling，在 dumps 方面，pickle 实现有一个 dedicated fast path 用于字典，而字典 subclass 通过 object.__reduce_ex__ 和 save_reduce.
在 loads 方面，时间差异主要来自额外的操作码和查找以检索和实例化 __main__.A class，而字典有一个专用的 pickle 操作码制作一个新的字典。如果我们比较泡菜的反汇编：
In [26]: pickletools.dis(pickle.dumps({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}))
0: \x80 PROTO 4
2: \x95 FRAME 25
11: } EMPTY_DICT
12: \x94 MEMOIZE (as 0)
13: ( MARK
14: K BININT1 0
16: K BININT1 0
18: K BININT1 1
20: K BININT1 1
22: K BININT1 2
24: K BININT1 2
26: K BININT1 3
28: K BININT1 3
30: K BININT1 4
32: K BININT1 4
34: u SETITEMS (MARK at 13)
35: . STOP
highest protocol among opcodes = 4
In [27]: pickletools.dis(pickle.dumps(A({0: 0, 1: 1, 2: 2, 3: 3, 4: 4})))
0: \x80 PROTO 4
2: \x95 FRAME 43
11: \x8c SHORT_BINUNICODE '__main__'
21: \x94 MEMOIZE (as 0)
22: \x8c SHORT_BINUNICODE 'A'
25: \x94 MEMOIZE (as 1)
26: \x93 STACK_GLOBAL
27: \x94 MEMOIZE (as 2)
28: ) EMPTY_TUPLE
29: \x81 NEWOBJ
30: \x94 MEMOIZE (as 3)
31: ( MARK
32: K BININT1 0
34: K BININT1 0
36: K BININT1 1
38: K BININT1 1
40: K BININT1 2
42: K BININT1 2
44: K BININT1 3
46: K BININT1 3
48: K BININT1 4
50: K BININT1 4
52: u SETITEMS (MARK at 31)
53: . STOP
highest protocol among opcodes = 4
我们看到两者之间的区别在于第二个 pickle 需要一大堆操作码来查找 __main__.A 并实例化它，而第一个 pickle 只是 EMPTY_DICT 来获得一个空字典之后，两个 pickle 将相同的键和值压入 pickle 操作数堆栈和 运行 SETITEMS.