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 pickle
sont 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 pickle
est 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.c
il 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_COEXIST
devrait 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 dict
n'appelle pas __getitem__()
, mais appelle le sous-intervalle mp_subscript
. En effet, mp_subscript
est 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_subscript
utilisent 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?
la source
dict
et 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 desA
membres de la classe , donc on peut s'attendre à ce qu'elle soit environ deux fois plus lente. L'pickle
explication est probablement assez similaire.len()
, par exemple, n'est pas 2x plus lent mais a la même vitesse?len
devrait 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.__contains__
implémentation explicite bloque la logique utilisée pour l'héritagesq_contains
.Réponses:
L'indexation
in
est plus lente dans lesdict
sous-classes en raison d'une mauvaise interaction entre unedict
optimisation 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_contains
etmp_subscript
fournissentin
et 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 ladict
classe 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:(En fait, l'
__getitem__
implémentation explicite est la même fonction que l'mp_subscript
implé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_contains
etmp_subscript
, et la sous-classe serait tout aussi rapide que la superclasse. Cependant, la logique dansupdate_one_slot
recherche l'implémentation parent en essayant de trouver les méthodes d'encapsulation générées via une recherche MRO.dict
ne pas avoir les enveloppes générées poursq_contains
etmp_subscript
, car il fournit explicitement__contains__
et__getitem__
mises en œuvre.Au lieu d'hériter
sq_contains
etmp_subscript
,update_one_slot
finit par donner la sous - classesq_contains
et lesmp_subscript
implé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_slot
implé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é avecdict
lui-même pour la vitesse de recherche, mais cela devrait les rapprocher beaucoup plus.Quant au décapage, sur le
dumps
cô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é à traversobject.__reduce_ex__
etsave_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__.A
classe, tandis que les dicts ont un opcode pickle dédié pour faire un nouveau dict. Si l'on compare le démontage des cornichons: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__.A
et l'instancier, tandis que le premier cornichon ne fait queEMPTY_DICT
pour 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écutentSETITEMS
.la source
__contains__()
et__getitem()
d'une manière qui puisse être hérité par des sous-classes? Dans la documentation officielle detp_methods
, il est écrit celamethods are inherited through a different mechanism
, donc cela semble possible.__contains__
et__getitem__
sont hérités, mais le problème est quesq_contains
etmp_subscript
ne le sont pas.__contains__
et__getitem__
sont dans la fentetp_methods
, que pour les documents officiels ne sont pas hérités par les sous-classes. Et comme vous l'avez dit,update_one_slot
n'utilise passq_contains
etmp_subscript
.contains
et le reste ne peut pas être simplement déplacé dans un autre emplacement, qui est hérité par les sous-classes?tp_methods
n'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.