Модуль dis и constant folding в Python 3.7

Недавно я наткнулся на одну интересную вещь. Оказывается, выражение

>>> pow(3,99)

работает медленнее, чем вот это:

>>> 3**99

Эта интересная особенность подтверждается непосредственным вычислением с помощью модуля timeit:

$ python3 -m timeit 'pow(3,99)'
500000 loops, best of 5: 527 nsec per loop

$ python3 -m timeit '3**99'
500000 loops, best of 5: 460 nsec per loop

Разница небольшая, но она все таки есть. Причина, по которой функция pow немного медленнее, заключается в том, что в CPython есть дополнительный шаг загрузки pow из пространства имен. Это также означает, что разница останется более или менее постоянной, даже если мы увеличим входные числа.

Наша догадка подтвердилась:

$ python3 -m timeit 'pow(3,9999)'
5000 loops, best of 5: 57.6 usec per loop

$ python3 -m timeit '3**9999'
5000 loops, best of 5: 58.9 usec per loop

В процессе изучения этого вопроса я также пользовался модулем dis. Этот модуль позволяет декомпилировать байт-код Python и проверять его.

>>> from dis import dis
>>> dis('pow(3,99)')
  1           0 LOAD_NAME                0 (pow)
              2 LOAD_CONST               0 (3)
              4 LOAD_CONST               1 (99)
              6 CALL_FUNCTION            2
              8 RETURN_VALUE

>>> dis('3**99')
  1           0 LOAD_CONST               0 (3)
              2 LOAD_CONST               1 (99)
              4 BINARY_POWER
              6 RETURN_VALUE

Декомпиляция pow в целом имеет смысл. Сначала происходит загрузка pow из пространства имен, затем загрузка 3 и 99 в регистры и, наконец, вызов функции pow. Но давайте рассмотрим еще один пример:

>>> dis('3**64')
  1           0 LOAD_CONST               0 (3433683820292512484657849089281)
              2 RETURN_VALUE

>>> dis('3**65')
  1           0 LOAD_CONST               0 (3)
              2 LOAD_CONST               1 (65)
              4 BINARY_POWER
              6 RETURN_VALUE

Воу, а вот это уже становится интересным. Почему выводы dis двух похожих функций так различаются? Ведь мы всего лишь изменили 64 на 65!

Этот вопрос относит нас к другой интересной концепции, которая носит название «свертка констант». Это означает, что когда у нас есть константное выражение, Python оценивает значение этого выражения во время компиляции, так что, когда вы запускаете программу, она не занимает много времени, потому что Python использует уже вычисленное значение. Приведу простой пример. Вот это:

def one_plue_one():
    return 1+1

превращается в это:

def one_plue_one():
    return 2

Самая распространенная реализация языка (CPython), которую вы обычно используете в своих программах, является интерпретируемой, с некоторой компиляцией. CPython компилирует исходный код на Питоне в байткод, а затем интерпретирует этот байткод, запуская его в процессе.

Так и почему же constant folding работает для числа 3**64, а не для 3**65? Может быть дело в том, что количество цифр в числе 3**65 больше, а Python ограничивает его например 30 знаками для целого числа? И да и нет.

Рассмотрим еще один, казалось бы абсурдный, пример:

>>> dis('2**66')
  1           0 LOAD_CONST               0 (2)
              2 LOAD_CONST               1 (66)
              4 BINARY_POWER
              6 RETURN_VALUE

>>> dis('4**33')
  1           0 LOAD_CONST               2 (73786976294838206464)
              2 RETURN_VALUE

Краткий ответ таков: нет никаких особых правил для constant folding. Есть только детали реализации, заключающиеся в том, что оптимизатор AST включает в себя некоторые меры предосторожности, чтобы не тратить слишком много времени или памяти на constant folding.

Подобные "меры предосторожности" для 2**66 или 4**33 основаны на количестве битов в LHS и значении RHS:

if (PyLong_Check(v) && PyLong_Check(w) && Py_SIZE(v) && Py_SIZE(w) > 0) {
    size_t vbits = _PyLong_NumBits(v);
    size_t wbits = PyLong_AsSize_t(w);
    if (vbits == (size_t)-1 || wbits == (size_t)-1) {
        return NULL;
    }
    if (vbits > MAX_INT_SIZE / wbits) {
        return NULL;
    }
}

MAX_INT_SIZE определен ранее как 128. Поскольку 2 – это 2-битное число, а 4 – 3-битное число, предполагаемый размер результата меньше для 4**33, поэтому оно проходит проверку и получает constant folding.

И еще один интересный пример. Поскольку Python производит вычисления слева направо, то выражение 1+2+3+x будет оптимизировано с помощью constant folding, а выражение x+3+2+1 – нет.

>>> dis('lambda x: 1+2+3+x')
  1           0 LOAD_CONST               0 (<code object <lambda> at 0x10a440c00, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<lambda>')
              4 MAKE_FUNCTION            0
              6 RETURN_VALUE

Disassembly of <code object <lambda> at 0x10a440c00, file "<dis>", line 1>:
  1           0 LOAD_CONST               1 (6)
              2 LOAD_FAST                0 (x)
              4 BINARY_ADD
              6 RETURN_VALUE

>>> dis('lambda x: x+3+2+1')
  1           0 LOAD_CONST               0 (<code object <lambda> at 0x10a4400c0, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<lambda>')
              4 MAKE_FUNCTION            0
              6 RETURN_VALUE

Disassembly of <code object <lambda> at 0x10a4400c0, file "<dis>", line 1>:
  1           0 LOAD_FAST                0 (x)
              2 LOAD_CONST               1 (3)
              4 BINARY_ADD
              6 LOAD_CONST               2 (2)
              8 BINARY_ADD
             10 LOAD_CONST               3 (1)
             12 BINARY_ADD
             14 RETURN_VALUE

P.S. Не забывайте делиться статьями и вступать на мой канал hello world. Это поможет выпускать больше качественного материала.