int как PyLong: arbitrary precision и small-int cache

В CPython нет привычного из C типа «int как машинное слово». Все целые числа — это объекты типа PyLong, представляющие собой динамически растущий массив 30-битных digit’ов на 64-битных платформах. Из этой модели прямо вытекают три фундаментальных свойства:

1. int не переполняется — массив digit’ов растёт по требованию.
2. Каждое целое — heap-allocated PyObject — даже число 0 весит 28 байт в памяти.
3. Small-int cache для [-5, 256] — частые значения предкэшированы, и id(256) == id(256) всегда True.

Эти три факта определяют performance numeric-кода в чистом Python и объясняют, почему data-engineering-библиотеки (NumPy, pandas, PyArrow) обходят PyLong через C-arrays.

PyLong layout

Структура PyLong (см. Include/cpython/longintrepr.h в исходниках CPython):

• PyObject_HEAD — 16 байт на 64-bit: ob_refcnt (8 байт) + ob_type (8 байт).
• ob_size — Py_ssize_t (8 байт): abs(ob_size) = число digit’ов в массиве; знак ob_size = знак самого числа. Для 0 — ob_size = 0.
• ob_digit[] — массив digit’ов переменной длины, каждый digit — uint32_t (но используется только 30 нижних бит).

Зачем 30 бит, а не 32? Потому что при умножении двух 30-битных digit’ов результат укладывается в 60 бит — а это меньше 64. Значит, промежуточный результат гарантированно не переполняет машинный uint64_t, и Karatsuba/schoolbook умножение работает без overflow-проверок на каждом шаге. См. Objects/longobject.c, функцию long_mul.

Arbitrary precision: почему int не переполняется

Когда вы пишете a + b, CPython вызывает long_add из Objects/longobject.c (source). Алгоритм:

1. Аллоцирует новый PyLong с ob_size = max(|a.ob_size|, |b.ob_size|) + 1 (с запасом на carry).
2. Складывает digit’ы поразрядно, обрабатывая carry.
3. Если итоговый старший digit оказался нулём — нормализует размер (_PyLong_Normalize).

Никакой arithmetic overflow не возникает: размер просто растёт. Цена этого — каждое арифметическое действие может аллоцировать новый объект.

import sys

print(2**1000)                # работает, ~302 десятичных цифры
print(sys.getsizeof(2**1000)) # ~156 байт (≈34 digits по 30 бит)

print(sys.getsizeof(2**63))   # >> чем 8 байт C int64

Это контрастирует с C, где int + int молча переполняется и даёт UB (или wraparound для unsigned). Python-семантика медленнее, но безопаснее по умолчанию.

Small-int cache: -5..256

Для интов в диапазоне [-5, 256] CPython предкэширует объекты в статическом массиве _PyLong_SMALL_INTS[NSMALLNEGINTS + NSMALLPOSINTS] (см. Objects/longobject.c, код). Функция PyLong_FromLong сначала проверяет, попадает ли значение в диапазон через макрос IS_SMALL_INT(ival) — если да, возвращает указатель на кэшированный объект и инкрементирует refcount. Аллокация не выполняется.

# Проверка границ кэша (значения сверены с baseline cpython-3.12.7)
a = -5;  b = -5;  print(a is b)   # True — нижняя граница в кэше
a = 256; b = 256; print(a is b)   # True — верхняя граница в кэше
a = 257; b = 257; print(a is b)   # False — за пределами, два отдельных PyLong
a = -6;  b = -6;  print(a is b)   # False — за пределами

# Размеры (sys.getsizeof из baseline)
import sys
print(sys.getsizeof(0))        # 28
print(sys.getsizeof(255))      # 28
print(sys.getsizeof(256))      # 28
print(sys.getsizeof(10**100))  # 72 (multi-digit)

Важно: границы кэша — implementation detail CPython. PyPy, MicroPython, Jython могут иметь другие границы или вовсе не иметь кэша. Никогда не пишите код, опирающийся на is для int значений.

Implications для performance

• Каждое целое — heap-allocated PyObject с overhead в 24+ байта на копию. Tight numeric loop типа s = 0; for x in lst: s += x создаёт ровно len(lst) + 1 промежуточных PyLong объектов (один на каждый промежуточный результат). Для lst из миллиона элементов — миллион аллокаций.
• Нет stack-allocated ints, как в C/Rust/Go. Альтернативы: array.array('q', ...) (C-array из int64), numpy.int64 (vectorized), Cython с typed cdef long. Но это уже не «чистый Python».
• sys.getsizeof(x) — самый быстрый способ оценить per-instance cost.

import sys
nums = [i for i in range(1_000_000)]
print(sys.getsizeof(nums))  # ~8MB только на сам list (указатели), плюс ~28MB на сами PyLong
# Для тяжёлой числовой работы: numpy.arange(1_000_000) — ~8MB суммарно (8 байт на int64)

Cross-course context

Cross-course → Storage Formats: 01/03 encoding-basics — Python int arbitrary-precision (массив 30-битных digits, размер растёт по требованию); binary форматы Parquet/Avro/Arrow используют fixed-width encoding (Int32, Int64, UInt8) или variable-width VarInt (Protobuf-style). Trade-off: Python безопаснее (no overflow), но платит per-int header’ом 28 байт; столбцовые форматы экономят память за счёт fixed-width plus dictionary/RLE encoding.

Ключевые выводы

1. int = PyLong = heap-allocated object с массивом 30-битных digits. PyObject_HEAD занимает 16 байт, ob_size — ещё 8, плюс digits.
2. Small-int cache для [-5, 256] амортизирует аллокацию для самых частых значений; _PyLong_SMALL_INTS — статический массив в Objects/longobject.c.
3. Arbitrary precision означает ноль overflow ценой constant per-int overhead. Для tight numeric loops используйте array.array или NumPy.