Почему создание подклассов в Python сильно тормозит?

13

Я работал на простой класс , который простирается dict, и я понял , что ключевой поиск и использование pickleявляются очень медленно.

Я думал, что это была проблема с моим классом, поэтому я сделал несколько тривиальных тестов:

(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

Результаты действительно сюрприз. В то время как поиск ключей в 2 раза медленнее, pickleв 5 раз медленнее.

Как это может быть? Другие методы, вроде get(), __eq__()и __init__(), и итерации keys(), values()и items()так же быстро, как dict.

РЕДАКТИРОВАТЬ : я взглянул на исходный код Python 3.9, и, Objects/dictobject.cкажется, что __getitem__()метод реализован dict_subscript(). И dict_subscript()замедляет подклассы, только если ключ отсутствует, так как подкласс может реализовать, __missing__()и он пытается видеть, существует ли он. Но тест был с существующим ключом.

Но я кое-что заметил: __getitem__()определяется флагом METH_COEXIST. А также __contains__(), другой метод, который в 2 раза медленнее, имеет тот же флаг. Из официальной документации :

Метод будет загружен вместо существующих определений. Без METH_COEXIST по умолчанию пропускаются повторные определения. Так как слот обертка загружается перед таблицей методы, наличие слота sq_contains, например, будет генерировать завернутый метод с именем содержит () и исключает загрузку соответствующего PyCFunction с тем же именем. С установленным флагом PyCFunction будет загружен вместо объекта-оболочки и будет сосуществовать со слотом. Это полезно, потому что вызовы PyCFunctions оптимизированы больше, чем вызовы объектов-оболочек.

Так что, если я правильно понял, теоретически METH_COEXISTследует ускорить процесс, но, похоже, это имеет противоположный эффект. Почему?

РЕДАКТИРОВАТЬ 2 : я обнаружил нечто большее.

__getitem__()и __contains()__помечены как METH_COEXIST, потому что они объявлены в PyDict_Type два раза.

Они оба присутствуют, один раз, в слоте tp_methods, где они явно объявлены как __getitem__()и __contains()__. Но официальная документация говорит , что tp_methodsявляются не наследуются подклассами.

Таким образом, подкласс dictне вызывает __getitem__(), но вызывает подслот mp_subscript. Действительно, mp_subscriptсодержится в слоте tp_as_mapping, что позволяет подклассу наследовать его подслоты.

Проблема в том, что оба __getitem__()и mp_subscriptиспользуют одну и ту же функцию dict_subscript. Возможно ли, что только способ наследования замедляет его?

python python-3.x performance dictionary subclass Марко Сулла
источник
5
Я не могу найти конкретную часть исходного кода, но я полагаю, что в реализации C есть быстрый путь, который проверяет, является ли объект a, dictи, если это так, вызывает реализацию C напрямую, вместо того, чтобы искать __getitem__метод из класс объекта. Таким образом, ваш код выполняет два точных поиска, первый - для ключа '__getitem__'в словаре членов класса A, поэтому можно ожидать, что он будет примерно в два раза медленнее. pickleОбъяснение, вероятно , очень похожи.
kaya3
@ kaya3: Но если это так, то почему len(), например, не в 2 раза медленнее, а с такой же скоростью?
Марко Сулла
Я не уверен в этом; Я бы подумал, что lenдолжен иметь быстрый путь для встроенных типов последовательности. Я не думаю, что смогу дать правильный ответ на ваш вопрос, но это хороший вопрос, так что, надеюсь, на него ответит кто-то более осведомленный о внутренностях Python, чем я.
kaya3
Я провел некоторое расследование и обновил вопрос.
Марко Сулла
1
...ой. Я вижу это сейчас. Явная __contains__реализация блокирует логику, используемую для наследования sq_contains.
user2357112 поддерживает Монику

Ответы:

7

Индексирование inвыполняется медленнее в dictподклассах из-за плохого взаимодействия между dictоптимизацией и логическими подклассами, используемыми для наследования С-слотов. Это должно быть исправимо, хотя и не с вашей стороны.

Реализация CPython имеет два набора хуков для перегрузок операторов. Существуют методы уровня Python, такие как __contains__и __getitem__, но есть также отдельный набор слотов для указателей на функции C в макете памяти объекта типа. Обычно либо метод Python будет оберткой для реализации C, либо слот C будет содержать функцию, которая ищет и вызывает метод Python. Для слота C более эффективно реализовывать эту операцию напрямую, поскольку слот C - это то, к чему фактически обращается Python.

Отображения, написанные на C, реализуют слоты C, sq_containsа mp_subscriptтакже обеспечивают inи индексируют. Обычно, Python уровня __contains__и __getitem__методы будут автоматически генерироваться как обертки вокруг функций C, но dictкласс имеет явные реализации из __contains__и __getitem__, так как явные реализаций немного быстрее , чем сгенерированные обертки:

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

(На самом деле, явная __getitem__реализация - это та же функция, что и mp_subscriptреализация, только с другим типом оболочки).

Обычно подкласс наследовал бы реализации своего родителя хуков уровня C, таких как sq_containsи mp_subscript, и подкласс был бы таким же быстрым, как и суперкласс. Однако логика update_one_slotищет родительскую реализацию, пытаясь найти сгенерированные методы-оболочки через поиск MRO.

dictне имеет сгенерированные оберток для sq_containsи mp_subscript, поскольку она обеспечивает явное __contains__и __getitem__реализации.

Вместо того, чтобы наследовать sq_containsи mp_subscript, в update_one_slotконечном итоге дает подкласс sq_containsи mp_subscriptреализации, которые выполняют MRO для поиска __contains__и __getitem__и вызова их. Это гораздо менее эффективно, чем прямое наследование С-слотов.

Исправление этого потребует изменений в update_one_slotреализации.

Помимо того, что я описал выше, dict_subscriptтакже __missing__выполняется dictпоиск подклассов dict, поэтому исправление проблемы наследования слотов не сделает подклассы полностью равными себе по скорости поиска, но должно приблизить их.

Что касается консервирования, то со dumpsстороны реализация pickle имеет выделенный быстрый путь для dicts, в то время как подкласс dict проходит более обходной путь через object.__reduce_ex__и save_reduce.

Кроме того loads, разница во времени в основном заключается в дополнительных кодах операций и поисках для извлечения и создания экземпляра __main__.Aкласса, в то время как у диктов есть специальный код операции выбора для создания новой диктовки. Если мы сравним разборку для солений:

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

мы видим, что различие между ними заключается в том, что второму рассолу нужна целая куча кодов операций, чтобы найти __main__.Aи создать его экземпляр, в то время как первый рассол просто делает, EMPTY_DICTчтобы получить пустой дикт. После этого оба маринада помещают одни и те же ключи и значения в стек операнда и запускаются SETITEMS.

user2357112 поддерживает Monica
источник
Большое спасибо! Есть ли у вас идеи, почему CPython использует этот странный метод наследования? Я имею в виду, не существует ли способ объявить __contains__()и __getitem()таким образом, что может быть унаследовано подклассами? В официальной документации tp_methodsнаписано, что methods are inherited through a different mechanismэто кажется возможным.
Марко Сулла
@MarcoSulla: __contains__и __getitem__ будут унаследованы, но проблема в том , что sq_containsи mp_subscriptнет.
user2357112 поддерживает Монику
Ммм, ну .... подожди минутку. Я думал, что это было наоборот. __contains__и __getitem__находятся в слоте tp_methods, что для официальных документов не наследуются подклассами. И, как вы сказали, update_one_slotне использует sq_containsи mp_subscript.
Марко Сулла
В плохих словах, containsа остальные не могут быть просто перемещены в другой слот, который наследуется подклассами?
Марко Сулла
@MarcoSulla: tp_methodsне наследуется, но сгенерированные из него объекты метода Python наследуются в том смысле, что стандартный поиск MRO для доступа к атрибутам найдет их.
user2357112 поддерживает Монику