Por que a subclasse no Python atrasa tanto as coisas?

Eu estava trabalhando em uma classe simples que se estende dicte percebi que a pesquisa e o uso de chaves picklesão muito lentos.

Eu pensei que era um problema com a minha classe, então fiz alguns benchmarks triviais:

(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

Os resultados são realmente uma surpresa. Enquanto a pesquisa de teclas é 2x mais lenta, pickleé 5x mais lenta.

Como isso pode ser? Outros métodos, como get(), __eq__()e __init__(), e iteração terminam keys(), values()e items()são tão rápidos quanto dict.

Edição : dei uma olhada no código fonte do Python 3.9, e Objects/dictobject.cparece que o __getitem__()método é implementado por dict_subscript(). E dict_subscript()diminui a velocidade das subclasses apenas se a chave estiver faltando, pois a subclasse pode ser implementada __missing__()e tenta ver se existe. Mas a referência foi com uma chave existente.

Mas notei algo: __getitem__()é definido com a bandeira METH_COEXIST. E também __contains__(), o outro método que é 2x mais lento, tem a mesma bandeira. A partir da documentação oficial :

O método será carregado no lugar das definições existentes. Sem METH_COEXIST, o padrão é pular definições repetidas. Como os wrappers de slot são carregados antes da tabela de métodos, a existência de um slot sq_contains, por exemplo, geraria um método empacotado chamado contains () e impediria o carregamento de uma PyCFunction correspondente com o mesmo nome. Com o sinalizador definido, o PyCFunction será carregado no lugar do objeto wrapper e coexistirá com o slot. Isso é útil porque as chamadas para PyCFunctions são otimizadas mais do que as chamadas de objeto de wrapper.

Então, se eu entendi direito, em teoria, METH_COEXISTdeveria acelerar as coisas, mas parece ter o efeito oposto. Por quê?

EDIT 2 : Eu descobri algo mais.

__getitem__()e __contains()__são sinalizados como METH_COEXIST, porque são declarados em PyDict_Type duas vezes.

Ambos estão presentes, uma vez, no slot tp_methods, onde são explicitamente declarados como __getitem__()e __contains()__. Mas a documentação oficial diz que nãotp_methods são herdadas pelas subclasses.

Portanto, uma subclasse de dictnão chama __getitem__(), mas chama o sub-lote mp_subscript. De fato, mp_subscriptestá contido no slot tp_as_mapping, que permite que uma subclasse herde seus sub-lotes.

O problema é que ambos __getitem__()e mp_subscriptusam a mesma função dict_subscript,. É possível que seja apenas a maneira como foi herdada que a torna mais lenta?

A indexação iné mais lenta nas dictsubclasses devido a uma interação ruim entre uma dictotimização e as subclasses lógicas usadas para herdar slots C. Isso deve ser corrigível, embora não do seu fim.

A implementação do CPython possui dois conjuntos de ganchos para sobrecargas do operador. Existem métodos no nível Python como __contains__e __getitem__, mas também há um conjunto separado de slots para ponteiros de função C no layout de memória de um objeto de tipo. Normalmente, o método Python será um wrapper em torno da implementação C ou o slot C conterá uma função que procura e chama o método Python. É mais eficiente para o slot C implementar a operação diretamente, pois o slot C é o que o Python realmente acessa.

Os mapeamentos escritos em C implementam os slots C sq_containse mp_subscriptfornecem ine indexam. Normalmente, o nível __contains__e os __getitem__métodos do Python seriam gerados automaticamente como wrappers em torno das funções C, mas a dictclasse possui implementações explícitas de __contains__e __getitem__, porque as implementações explícitas são um pouco mais rápidas que os wrappers gerados:

static PyMethodDef mapp_methods[] = {
    DICT___CONTAINS___METHODDEF
    {"__getitem__", (PyCFunction)(void(*)(void))dict_subscript,        METH_O | METH_COEXIST,
     getitem__doc__},
    ...

(Na verdade, a __getitem__implementação explícita tem a mesma função que a mp_subscriptimplementação, apenas com um tipo diferente de wrapper.)

Normalmente, uma subclasse herdaria as implementações de ganchos de nível C de seus pais como sq_containse mp_subscript, e a subclasse seria tão rápida quanto a superclasse. No entanto, a lógica update_one_slotprocura a implementação pai tentando localizar os métodos de wrapper gerados por meio de uma pesquisa MRO.

dictnão têm invólucros gerados para sq_containse mp_subscript, porque fornece explícita __contains__e __getitem__implementações.

Em vez de herdar sq_containse mp_subscript, update_one_slotacaba dando a subclasse sq_containse mp_subscriptimplementações que executar a busca por uma MRO para __contains__e __getitem__e chamar aqueles. Isso é muito menos eficiente do que herdar os slots C diretamente.

Corrigir isso exigirá alterações na update_one_slotimplementação.

Além do que eu descrevi acima, dict_subscripttambém procura __missing__subclasses de dict, portanto, corrigir o problema de herança de slot não tornará as subclasses completamente iguais dictpara a velocidade de pesquisa, mas deve aproximá-las bastante.

Quanto à decapagem, por dumpsoutro lado, a implementação da decapagem possui um caminho rápido dedicado para dictos, enquanto a subclasse dict segue um caminho mais indireto através de object.__reduce_ex__e save_reduce.

Por loadsoutro lado, a diferença de horário é principalmente dos opcodes e pesquisas extras para recuperar e instanciar a __main__.Aclasse, enquanto os dictos têm um opcode pickle dedicado para fazer um novo dict. Se compararmos a desmontagem dos picles:

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

vemos que a diferença entre os dois é que o segundo pickle precisa de um monte de opcodes para procurá-lo __main__.Ae instancia-lo, enquanto o primeiro pickle apenas faz EMPTY_DICTpara obter um ditado vazio. Depois disso, os dois pickles pressionam as mesmas chaves e valores na pilha de operandos pickle e executam SETITEMS.