¿Por qué las subclases en Python ralentizan tanto las cosas?

Estaba trabajando en una clase simple que se extiende dicty me di cuenta de que la búsqueda y el uso de claves pickleson muy lentos.

Pensé que era un problema con mi clase, así que hice algunos puntos de referencia triviales:

(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

Los resultados son realmente una sorpresa. Mientras que la búsqueda de claves es 2 veces más lenta, picklees 5 veces más lenta.

¿Cómo puede ser esto? Otros métodos, como get(), __eq__()y __init__(), e iteración keys(), values()y items()son tan rápidos como dict.

EDITAR : Eché un vistazo al código fuente de Python 3.9, y Objects/dictobject.cparece que el __getitem__()método está implementado por dict_subscript(). Y dict_subscript()ralentiza las subclases solo si falta la clave, ya que la subclase puede implementar __missing__()e intenta ver si existe. Pero el punto de referencia fue con una clave existente.

Pero noté algo: __getitem__()se define con la bandera METH_COEXIST. Y también __contains__(), el otro método que es 2 veces más lento, tiene la misma bandera. De la documentación oficial :

El método se cargará en lugar de las definiciones existentes. Sin METH_COEXIST, el valor predeterminado es omitir definiciones repetidas. Dado que los contenedores de ranuras se cargan antes de la tabla de métodos, la existencia de una ranura sq_contains, por ejemplo, generaría un método envuelto llamado contiene () y evitaría la carga de una PyCFunction correspondiente con el mismo nombre. Con la bandera definida, la función PyCFunction se cargará en lugar del objeto contenedor y coexistirá con la ranura. Esto es útil porque las llamadas a PyCFunctions se optimizan más que las llamadas a objetos de contenedor.

Entonces, si entendí correctamente, en teoría METH_COEXISTdebería acelerar las cosas, pero parece tener el efecto contrario. ¿Por qué?

EDIT 2 : descubrí algo más.

__getitem__()y __contains()__se marcan como METH_COEXIST, porque se declaran en PyDict_Type dos veces.

Ambos están presentes, una vez, en la ranura tp_methods, donde se declaran explícitamente como __getitem__()y __contains()__. Pero la documentación oficial dice que notp_methods son heredadas por las subclases.

Entonces, una subclase de dictno llama __getitem__(), sino que llama al subslot mp_subscript. De hecho, mp_subscriptestá contenido en la ranura tp_as_mapping, que permite que una subclase herede sus sublotas.

El problema es que ambos __getitem__()y mp_subscriptusan la misma función dict_subscript,. ¿Es posible que sea solo la forma en que se heredó lo que lo ralentiza?

La indexación y inlas dictsubclases son más lentas debido a una mala interacción entre una dictoptimización y las subclases lógicas utilizadas para heredar las ranuras C. Esto debería ser reparable, aunque no de su parte.

La implementación de CPython tiene dos conjuntos de ganchos para sobrecargas del operador. Existen métodos a nivel de Python como __contains__y __getitem__, pero también hay un conjunto separado de ranuras para punteros de función C en el diseño de memoria de un objeto tipo. Por lo general, el método Python será un envoltorio alrededor de la implementación de C o la ranura C contendrá una función que busca y llama al método Python. Es más eficiente que la ranura C implemente la operación directamente, ya que la ranura C es a lo que Python realmente accede.

Las asignaciones escritas en C implementan las ranuras C sq_containsy mp_subscriptproporcionan ine indexan. Normalmente, el nivel de Python __contains__y los __getitem__métodos se generarían automáticamente como envoltorios alrededor de las funciones de C, pero la dictclase tiene implementaciones explícitas de __contains__y __getitem__, porque las implementaciones explícitas son un poco más rápidas que los envoltorios generados:

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

(En realidad, la __getitem__implementación explícita es la misma función que la mp_subscriptimplementación, solo que con un tipo diferente de envoltorio).

Por lo general, una subclase heredaría las implementaciones de sus padres de ganchos de nivel C como sq_containsy mp_subscript, y la subclase sería tan rápida como la superclase. Sin embargo, la lógica update_one_slotbusca la implementación principal al tratar de encontrar los métodos de contenedor generados a través de una búsqueda MRO.

dictno tienen envolturas generados para sq_containsy mp_subscript, debido a que proporciona explícita __contains__e __getitem__implementaciones.

En lugar de heredar sq_containsy mp_subscript, update_one_slottermina dando la subclase sq_containsy mp_subscriptlas implementaciones que realizar una búsqueda de MRO __contains__y __getitem__y llamar a aquellos. Esto es mucho menos eficiente que heredar las ranuras C directamente.

Arreglar esto requerirá cambios en la update_one_slotimplementación.

Además de lo que describí anteriormente, dict_subscripttambién busca __missing__subclases dict, por lo que solucionar el problema de herencia de ranura no hará que las subclases estén completamente a la par dictpara la velocidad de búsqueda, pero debería acercarlas mucho más.

En cuanto al encurtido, por un dumpslado, la implementación de encurtido tiene una ruta rápida dedicada para los dictados, mientras que la subclase dict toma un camino más indirecto a través de object.__reduce_ex__y save_reduce.

Por loadsotro lado, la diferencia horaria se debe principalmente a los __main__.Acódigos de operación y las búsquedas adicionales para recuperar e instanciar la clase, mientras que los dictos tienen un código de operación de pickle dedicado para hacer un nuevo dict. Si comparamos el desmontaje de los encurtidos:

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 la diferencia entre los dos es que el segundo encurtido necesita un montón de códigos de operación para mirar hacia arriba __main__.Ae instanciarlo, mientras que el primer encurtido solo lo hace EMPTY_DICTpara obtener un dict vacío. Después de eso, ambos pepinillos empujan las mismas teclas y valores en la pila de operandos de pepinillos y se ejecutan SETITEMS.