Ich arbeitete an einer einfachen Klasse , die erweitert dict
, und ich erkannte , dass die Schlüsselsuche und Verwendung pickle
sind sehr langsam.
Ich dachte, es sei ein Problem mit meiner Klasse, also habe ich einige triviale Benchmarks durchgeführt:
(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
Die Ergebnisse sind wirklich eine Überraschung. Während die Schlüsselsuche 2x langsamer ist, pickle
ist sie 5x langsamer.
Wie kann das sein? Andere Verfahren, wie get()
, __eq__()
und __init__()
, und Iteration über keys()
, values()
und items()
sind so schnell wie dict
.
EDIT : Ich habe mir den Quellcode von Python 3.9 angesehen und Objects/dictobject.c
es scheint, dass die __getitem__()
Methode von implementiert wird dict_subscript()
. Und dict_subscript()
verlangsamt Unterklassen nur, wenn der Schlüssel fehlt, da die Unterklasse implementiert werden kann __missing__()
und versucht, festzustellen, ob er vorhanden ist. Der Benchmark war jedoch ein vorhandener Schlüssel.
Aber mir ist etwas aufgefallen: __getitem__()
wird mit der Flagge definiert METH_COEXIST
. Und auch __contains__()
die andere Methode, die 2x langsamer ist, hat das gleiche Flag. Aus der offiziellen Dokumentation :
Die Methode wird anstelle der vorhandenen Definitionen geladen. Ohne METH_COEXIST werden standardmäßig wiederholte Definitionen übersprungen. Da Schlitz Umhüllungen vor dem Methodentabelle geladen werden, erzeugen würde die Existenz eines sq_contains Schlitz, beispielsweise eine umhüllten Methode namens enthält () , und schließt das Laden eines entsprechendes PyCFunction mit dem gleichen Namen. Wenn das Flag definiert ist, wird die PyCFunction anstelle des Wrapper-Objekts geladen und existiert neben dem Slot. Dies ist hilfreich, da Aufrufe von PyCFunctions mehr optimiert sind als Wrapper-Objektaufrufe.
Wenn ich es richtig verstanden habe, METH_COEXIST
sollte es theoretisch die Dinge beschleunigen, aber es scheint den gegenteiligen Effekt zu haben. Warum?
EDIT 2 : Ich habe etwas mehr entdeckt.
__getitem__()
und __contains()__
als Liste steht METH_COEXIST
, weil sie in PyDict_Type deklariert sind zwei mal.
Sie sind beide einmal im Slot vorhanden tp_methods
, wo sie explizit als __getitem__()
und deklariert werden __contains()__
. Aber die offizielle Dokumentation sagt , dass tp_methods
sind nicht von den Unterklassen geerbt.
Eine Unterklasse von dict
ruft also nicht auf __getitem__()
, sondern ruft den Unterschlitz auf mp_subscript
. In der Tat mp_subscript
ist in dem Slot enthalten tp_as_mapping
, der es einer Unterklasse ermöglicht, ihre Subslots zu erben.
Das Problem ist, dass beide __getitem__()
und mp_subscript
die gleiche Funktion verwenden dict_subscript
. Ist es möglich, dass nur die Art und Weise, wie es geerbt wurde, es verlangsamt?
quelle
dict
und in diesem Fall die C-Implementierung direkt aufruft, anstatt die__getitem__
Methode von nachzuschlagen die Klasse des Objekts. Ihr Code führt daher zwei Diktatsuchen durch, die erste für den Schlüssel'__getitem__'
im Wörterbuch der KlassenmitgliederA
, sodass davon ausgegangen werden kann, dass er etwa doppelt so langsam ist. Diepickle
Erklärung ist wahrscheinlich ziemlich ähnlich.len()
ist zum Beispiel nicht 2x langsamer, sondern hat die gleiche Geschwindigkeit?len
sollte einen schnellen Weg für eingebaute Sequenztypen haben. Ich glaube nicht, dass ich in der Lage bin, Ihre Frage richtig zu beantworten, aber es ist eine gute. Hoffentlich wird jemand, der sich mit Python-Interna besser auskennt als ich, sie beantworten.__contains__
Implementierung blockiert die zum Erben verwendete Logiksq_contains
.Antworten:
Indizierung und
in
langsamer indict
Unterklassen aufgrund einer schlechten Interaktion zwischen einerdict
Optimierung und den logischen Unterklassen, die zum Erben von C-Slots verwendet werden. Dies sollte reparabel sein, aber nicht von Ihrem Ende.Die CPython-Implementierung verfügt über zwei Sätze von Hooks für Operatorüberladungen. Es gibt Python-Level-Methoden wie
__contains__
und__getitem__
, aber es gibt auch einen separaten Satz von Slots für C-Funktionszeiger im Speicherlayout eines Typobjekts. Normalerweise ist entweder die Python-Methode ein Wrapper um die C-Implementierung, oder der C-Slot enthält eine Funktion, die nach der Python-Methode sucht und diese aufruft. Für den C-Slot ist es effizienter, die Operation direkt zu implementieren, da Python tatsächlich auf den C-Slot zugreift.In C geschriebene Zuordnungen implementieren die C-Slots
sq_contains
und dienenmp_subscript
zum Bereitstellenin
und Indizieren. Normalerweise werden die Python-Ebene__contains__
und__getitem__
-Methoden automatisch als Wrapper um die C-Funktionen generiert, aber diedict
Klasse verfügt über explizite Implementierungen von__contains__
und__getitem__
, da die expliziten Implementierungen etwas schneller sind als die generierten Wrapper:(Tatsächlich ist die explizite
__getitem__
Implementierung dieselbe Funktion wie diemp_subscript
Implementierung, nur mit einer anderen Art von Wrapper.)Normalerweise würde eine Unterklasse die Implementierungen von C-Level-Hooks wie
sq_contains
und durch ihre Eltern erbenmp_subscript
, und die Unterklasse wäre genauso schnell wie die Oberklasse. Die Logikupdate_one_slot
sucht jedoch nach der übergeordneten Implementierung, indem versucht wird, die generierten Wrapper-Methoden über eine MRO-Suche zu finden.dict
nicht haben generiert Wrapper fürsq_contains
undmp_subscript
, weil es explizit bietet__contains__
und__getitem__
Implementierungen.Statt vererben
sq_contains
undmp_subscript
,update_one_slot
endet die Unterklasse gebensq_contains
undmp_subscript
Implementierungen , die eine MRO Suche ausführen für__contains__
und__getitem__
und die Teilnehmer anrufen. Dies ist viel weniger effizient als das direkte Erben der C-Slots.Um dies zu beheben, müssen Änderungen an der
update_one_slot
Implementierung vorgenommen werden.Abgesehen von dem, was ich oben beschrieben habe, wird
dict_subscript
auch nach__missing__
diktierten Unterklassen gesucht. Wenn Sie also das Problem der Slot-Vererbung beheben, werden die Unterklassen hinsichtlich der Suchgeschwindigkeit nicht vollständig mit sichdict
selbst gleichgesetzt, sollten sie jedoch viel näher bringen.Was das Beizen betrifft, hat die Beizimplementierung nebenbei
dumps
einen dedizierten schnellen Pfad für Diktate, während die Diktat-Unterklasse einen Kreisverkehrspfad durchobject.__reduce_ex__
und nimmtsave_reduce
.Auf der
loads
Seite ist die Zeitdifferenz meist nur von den zusätzlichen OP - Codes und Lookups abzurufen und die instanziiert__main__.A
Klasse, während dicts eine spezielle Gurke Opcode haben einen neuen dict zu machen. Wenn wir die Demontage für die Gurken vergleichen:Wir sehen, dass der Unterschied zwischen den beiden darin besteht, dass die zweite Gurke eine ganze Reihe von Opcodes benötigt, um sie
__main__.A
nachzuschlagen und zu instanziieren, während die erste Gurke nurEMPTY_DICT
ein leeres Diktat erhält. Danach drücken beide Pickles die gleichen Tasten und Werte auf den Pickle-Operandenstapel und laufenSETITEMS
.quelle
__contains__()
und__getitem()
in einer Weise , die von den Unterklassen geerbt werden kann? In der offiziellen Dokumentation vontp_methods
steht das geschriebenmethods are inherited through a different mechanism
, also scheint es möglich.__contains__
und__getitem__
werden geerbt, aber das Problem ist dassq_contains
undmp_subscript
nicht.__contains__
und__getitem__
sind in dem Slottp_methods
, dass für die offiziellen Dokumente nicht von Unterklassen geerbt werden. Und wie Sie sagten,update_one_slot
verwendetsq_contains
und nichtmp_subscript
.contains
und der Rest kann nicht einfach in einen anderen Slot verschoben werden, der von Unterklassen geerbt wird?tp_methods
wird nicht vererbt, aber die daraus generierten Python-Methodenobjekte werden in dem Sinne vererbt, dass die Standard-MRO-Suche nach Attributzugriff sie findet.