Dlaczego podklasowanie w Pythonie tak bardzo spowalnia rzeczy?

Pracowałem nad prostą klasą, która rozszerza się dicti zdałem sobie sprawę, że wyszukiwanie klucza i korzystanie z nich picklejest bardzo wolne.

Myślałem, że to problem z moją klasą, więc zrobiłem kilka prostych testów:

(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

Wyniki są naprawdę niespodzianką. Podczas gdy wyszukiwanie klucza jest 2x wolniejsze, picklejest pięciokrotnie wolniejsze.

Jak to może być? Inne metody, takie jak get(), __eq__()i __init__(), i iteracja nad keys(), values()i items()to jak najszybciej dict.

EDYCJA : Rzuciłem okiem na kod źródłowy Pythona 3.9 i Objects/dictobject.cwydaje się, że __getitem__()metoda jest zaimplementowana przez dict_subscript(). I dict_subscript()spowalnia podklasy tylko wtedy, gdy brakuje klucza, ponieważ podklasa może się zaimplementować __missing__()i próbuje sprawdzić, czy istnieje. Ale punktem odniesienia był istniejący klucz.

Ale zauważyłem coś: __getitem__()jest zdefiniowane za pomocą flagi METH_COEXIST. Również __contains__()druga metoda, która jest 2x wolniejsza, ma tę samą flagę. Z oficjalnej dokumentacji :

Metoda zostanie załadowana w miejsce istniejących definicji. Bez METH_COEXIST domyślnie pomija się powtarzające się definicje. Ponieważ opakowania szczelin są ładowane przed tabelą metod, istnienie gniazda sq_contains zawiera na przykład wygenerowanie zawiniętej metody o nazwie zawiera () i wyklucza ładowanie odpowiedniej funkcji PyC o tej samej nazwie. Po zdefiniowaniu flagi funkcja PyCFunkcja zostanie załadowana w miejsce obiektu opakowania i będzie współistnieć z gniazdem. Jest to pomocne, ponieważ wywołania funkcji PyC są zoptymalizowane bardziej niż wywołania obiektu opakowania.

Więc jeśli dobrze zrozumiałem, teoretycznie METH_COEXISTpowinno to przyspieszyć, ale wydaje się, że ma to odwrotny skutek. Dlaczego?

EDYCJA 2 : Odkryłem coś więcej.

__getitem__()i __contains()__są oznaczane jako METH_COEXIST, ponieważ są zadeklarowane w PyDict_Type dwa razy.

Obaj są obecni jednorazowo w automacie tp_methods, gdzie są wyraźnie zadeklarowani jako __getitem__()i __contains()__. Ale oficjalna dokumentacja mówi, że nietp_methods są dziedziczone przez podklasy.

Tak więc podklasa dictnie wywołuje __getitem__(), ale wywołuje sublot mp_subscript. Rzeczywiście, mp_subscriptjest zawarty w gnieździe tp_as_mapping, który pozwala podklasie odziedziczyć podsieci.

Problem polega na tym, że zarówno __getitem__()i mp_subscriptużyć tej samej funkcji dict_subscript. Czy to możliwe, że spowalnia to tylko sposób odziedziczenia?

Indeksowanie i insą wolniejsze w dictpodklasach z powodu złej interakcji między dictoptymalizacją a logicznymi podklasami używanymi do dziedziczenia szczelin C. Powinno to zostać naprawione, ale nie od końca.

Implementacja CPython ma dwa zestawy zaczepów dla przeciążeń operatora. Istnieją metody na poziomie Python, takie jak __contains__i __getitem__, ale istnieje również osobny zestaw miejsc dla wskaźników funkcji C w układzie pamięci obiektu typu. Zwykle albo metoda Python będzie owijała się wokół implementacji języka C, lub gniazdo C będzie zawierało funkcję, która wyszukuje i wywołuje metodę języka Python. Bardziej wydajne jest, aby gniazdo C realizowało operację bezpośrednio, ponieważ gniazdo C jest tym, do którego faktycznie uzyskuje dostęp Python.

Mapowania napisane w C implementują gniazda C sq_containsoraz mp_subscriptudostępniają ini indeksują. Zwykle Python poziomu __contains__i __getitem__metody będą automatycznie generowane jako obwolut wokół funkcji C, ale dictklasa ma wyraźne implementacje o __contains__i __getitem__, ponieważ jawne implementacje są nieco szybciej niż generowanych owijarki:

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

(W rzeczywistości jawna __getitem__implementacja jest tą samą funkcją co mp_subscriptimplementacja, tylko z innym rodzajem opakowania).

Zwykle podklasa dziedziczy implementacje rodzicielskie haków na poziomie C, takich jak sq_containsi mp_subscript, a podklasa byłaby równie szybka jak nadklasa. Jednak logika update_one_slotszuka implementacji nadrzędnej, próbując znaleźć wygenerowane metody opakowania za pomocą wyszukiwania MRO.

dictnie mają generowane obwoluty dla sq_containsi mp_subscript, ponieważ zapewnia wyraźny __contains__i __getitem__implementacje.

Zamiast dziedziczy sq_containsi mp_subscript, update_one_slotkończy się dając podklasę sq_containsi mp_subscriptimplementacje że przeprowadzenie MRO szukać __contains__i __getitem__i nazywają te. Jest to o wiele mniej wydajne niż bezpośrednie dziedziczenie slotów C.

Naprawienie tego wymagać będzie zmian w update_one_slotimplementacji.

Oprócz tego, co opisałem powyżej, dict_subscriptwyszukuje także __missing__podklasy dict, więc naprawienie problemu dziedziczenia slotów nie spowoduje, że podklasy będą na równi ze dictsobą pod względem szybkości wyszukiwania, ale powinny zbliżyć je znacznie bardziej.

Jeśli chodzi o wytrawianie, z dumpsboku implementacja wytrawiania ma dedykowaną szybką ścieżkę dla nagrań, podczas gdy podklasa nagrań ma bardziej okrągłą ścieżkę przez object.__reduce_ex__i save_reduce.

Z loadsboku różnica czasu wynika głównie z dodatkowych kodów operacyjnych i odnośników do wyszukiwania i tworzenia __main__.Aklasy, podczas gdy dykty mają dedykowany kod piklujący do tworzenia nowego dykta. Jeśli porównamy demontaż pikli:

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

widzimy, że różnica między nimi polega na tym, że druga marynata potrzebuje całej gamy kodów do wyszukiwania __main__.Ai tworzenia jej, podczas gdy pierwsza marynata robi tylko EMPTY_DICTpusty dyktand. Następnie oba pikle pchają te same klucze i wartości na stos operandu piklującego i biegną SETITEMS.