Pourquoi le sous-classement en Python ralentit-il tant les choses?

13

Je travaillais sur une classe simple qui s'étend dict, et j'ai réalisé que la recherche de clés et l'utilisation de picklesont très lentes.

Je pensais que c'était un problème avec ma classe, alors j'ai fait quelques repères triviaux:

(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

Les résultats sont vraiment une surprise. Alors que la recherche de clé est 2 fois plus lente, elle pickleest 5 fois plus lente.

Comment se peut-il? D' autres méthodes, comme get(), __eq__()et __init__(), et l' itération sur keys(), values()et items()sont aussi rapides que dict.


EDIT : J'ai jeté un coup d'œil au code source de Python 3.9, et Objects/dictobject.cil semble que la __getitem__()méthode soit implémentée par dict_subscript(). Et ne dict_subscript()ralentit les sous-classes que si la clé est manquante, car la sous-classe peut être implémentée __missing__()et elle essaie de voir si elle existe. Mais la référence était avec une clé existante.

Mais j'ai remarqué quelque chose: __getitem__()est défini avec le drapeau METH_COEXIST. Et aussi __contains__(), l'autre méthode qui est 2x plus lente, a le même indicateur. De la documentation officielle :

La méthode sera chargée à la place des définitions existantes. Sans METH_COEXIST, la valeur par défaut est d'ignorer les définitions répétées. Étant donné que les wrappers d'emplacement sont chargés avant la table de méthodes, l'existence d'un emplacement sq_contains, par exemple, générerait une méthode encapsulée nommée contains () et empêcherait le chargement d'une fonction PyCFunction correspondante portant le même nom. Avec l'indicateur défini, la fonction PyCFunction sera chargée à la place de l'objet wrapper et coexistera avec l'emplacement. Cela est utile car les appels à PyCFunctions sont plus optimisés que les appels d'objet wrapper.

Donc, si j'ai bien compris, en théorie, cela METH_COEXISTdevrait accélérer les choses, mais cela semble avoir l'effet inverse. Pourquoi?


EDIT 2 : J'ai découvert quelque chose de plus.

__getitem__()et __contains()__sont marqués comme METH_COEXIST, car ils sont déclarés deux fois dans PyDict_Type .

Ils sont tous deux présents, une fois, dans la fente tp_methods, où ils sont explicitement déclarés comme __getitem__()et __contains()__. Mais la documentation officielle dit que netp_methods sont pas hérités par les sous-classes.

Ainsi, une sous-classe de dictn'appelle pas __getitem__(), mais appelle le sous-intervalle mp_subscript. En effet, mp_subscriptest contenu dans le slot tp_as_mapping, qui permet à une sous-classe d'hériter de ses sous-slots.

Le problème est que les deux __getitem__()et mp_subscriptutilisent la même fonction dict_subscript,. Est-il possible que ce soit seulement la façon dont il a été hérité qui le ralentisse?

Marco Sulla
la source
5
Je ne suis pas en mesure de trouver la partie spécifique du code source, mais je crois qu'il existe un chemin rapide dans l'implémentation C qui vérifie si l'objet est un dictet si oui, appelle directement l'implémentation C au lieu de rechercher la __getitem__méthode à partir de la classe de l'objet. Votre code effectue donc deux recherches de dict, la première pour la clé '__getitem__'dans le dictionnaire des Amembres de la classe , donc on peut s'attendre à ce qu'elle soit environ deux fois plus lente. L' pickleexplication est probablement assez similaire.
kaya3
@ kaya3: Mais si c'est le cas, pourquoi len(), par exemple, n'est pas 2x plus lent mais a la même vitesse?
Marco Sulla
Je ne suis pas certain de ça; J'aurais pensé qu'il lendevrait y avoir un chemin rapide pour les types de séquence intégrés. Je ne pense pas être en mesure de donner une bonne réponse à votre question, mais elle est bonne, alors j'espère que quelqu'un qui connaît mieux les internes de Python que moi y répondra.
kaya3
J'ai fait une enquête et mis à jour la question.
Marco Sulla
1
...Oh. Je le vois maintenant. L' __contains__implémentation explicite bloque la logique utilisée pour l'héritage sq_contains.
user2357112 prend en charge Monica le

Réponses:

7

L'indexation inest plus lente dans les dictsous-classes en raison d'une mauvaise interaction entre une dictoptimisation et les sous-classes logiques utilisées pour hériter des emplacements C. Cela devrait être réparable, mais pas de votre côté.

L'implémentation CPython possède deux ensembles de crochets pour les surcharges d'opérateur. Il existe des méthodes de niveau Python comme __contains__et __getitem__, mais il existe également un ensemble distinct d'emplacements pour les pointeurs de fonction C dans la disposition de la mémoire d'un objet type. Habituellement, soit la méthode Python sera un wrapper autour de l'implémentation C, soit l'emplacement C contiendra une fonction qui recherche et appelle la méthode Python. Il est plus efficace pour le slot C d'implémenter l'opération directement, car le slot C est ce à quoi Python accède réellement.

Les mappages écrits en C implémentent les slots C sq_containset mp_subscriptfournissent inet indexent. Ordinairement, le niveau Python __contains__et les __getitem__méthodes seraient générés automatiquement en tant que wrappers autour des fonctions C, mais la dictclasse a des implémentations explicites de __contains__et __getitem__, car les implémentations explicites sont un peu plus rapides que les wrappers générés:

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

(En fait, l' __getitem__implémentation explicite est la même fonction que l' mp_subscriptimplémentation, juste avec un type de wrapper différent.)

Habituellement, une sous-classe hériterait des implémentations de ses parents de crochets de niveau C comme sq_containset mp_subscript, et la sous-classe serait tout aussi rapide que la superclasse. Cependant, la logique dans update_one_slotrecherche l'implémentation parent en essayant de trouver les méthodes d'encapsulation générées via une recherche MRO.

dictne pas avoir les enveloppes générées pour sq_containset mp_subscript, car il fournit explicitement __contains__et __getitem__mises en œuvre.

Au lieu d'hériter sq_containset mp_subscript, update_one_slotfinit par donner la sous - classe sq_containset les mp_subscriptimplémentations qui effectuer une recherche MRO pour __contains__et __getitem__et appeler ceux -ci . C'est beaucoup moins efficace que d'hériter directement des slots C.

Pour résoudre ce problème, vous devrez modifier l' update_one_slotimplémentation.


Mis à part ce que j'ai décrit ci-dessus, dict_subscript recherche également les __missing__sous-classes dict, donc la résolution du problème d'héritage des emplacements ne rendra pas les sous-classes complètement à égalité avec dictlui-même pour la vitesse de recherche, mais cela devrait les rapprocher beaucoup plus.


Quant au décapage, sur le dumpscôté, la mise en œuvre du cornichon a un chemin rapide dédié pour les dict, tandis que la sous-classe dict prend un chemin plus détourné à travers object.__reduce_ex__et save_reduce.

Sur le loads côté, la différence de temps vient principalement des opcodes et des recherches supplémentaires pour récupérer et instancier la __main__.Aclasse, tandis que les dicts ont un opcode pickle dédié pour faire un nouveau dict. Si l'on compare le démontage des cornichons:

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

nous voyons que la différence entre les deux est que le second cornichon a besoin de tout un tas d'opcodes pour le rechercher __main__.Aet l'instancier, tandis que le premier cornichon ne fait que EMPTY_DICTpour obtenir un dict vide. Après cela, les deux cornichons poussent les mêmes clés et valeurs sur la pile d'opérandes de cornichons et s'exécutent SETITEMS.

user2357112 prend en charge Monica
la source
Merci beaucoup! Avez-vous une idée pourquoi CPython utilise cette étrange méthode d'héritage? Je veux dire, n'y a-t-il pas un moyen de déclarer __contains__()et __getitem()d'une manière qui puisse être hérité par des sous-classes? Dans la documentation officielle de tp_methods, il est écrit cela methods are inherited through a different mechanism, donc cela semble possible.
Marco Sulla
@MarcoSulla: __contains__et __getitem__ sont hérités, mais le problème est que sq_containset mp_subscriptne le sont pas.
user2357112 prend en charge Monica
Mh, eh bien ... attendez un instant. Je pensais que c'était le contraire. __contains__et __getitem__sont dans la fente tp_methods, que pour les documents officiels ne sont pas hérités par les sous-classes. Et comme vous l'avez dit, update_one_slotn'utilise pas sq_containset mp_subscript.
Marco Sulla
En termes pauvres, containset le reste ne peut pas être simplement déplacé dans un autre emplacement, qui est hérité par les sous-classes?
Marco Sulla
@MarcoSulla: tp_methodsn'est pas hérité, mais les objets de la méthode Python générés à partir de lui sont hérités dans le sens où la recherche MRO standard pour l'accès aux attributs les trouvera.
user2357112 prend en charge Monica le