CPython's int Implementation in C

TL;DR: Python’s int is arbitrary precision, but the common case is tiny. One tag word packs sign, digit count, and the small-int flag; the digits themselves are 30-bit limbs in a little-endian array, and -5..1024 are immortal singletons.

Python’s int is arbitrary precision: it grows to hold whatever integer you ask for. In CPython that is implemented by PyLongObject in Objects/longobject.c, backed by an array of 30-bit (or 15-bit) “digits”. This article traces the representation and the hot paths through the 3.15 source.

The object struct

Every Python object starts with PyObject_HEAD (ob_refcnt and ob_type). For ints the payload is a single struct, _PyLongValue, embedded directly:

c
// Include/cpython/longintrepr.h
typedef struct _PyLongValue {
    uintptr_t lv_tag;   /* digit count, sign and flags */
    digit ob_digit[1];  /* least-significant digit first */
} _PyLongValue;

struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

There is no separate allocation for the digit array: ob_digit is declared with size 1 and the allocator over-allocates trailing storage (see below). Digits are stored little-endian, least significant first, and on the default build each digit is a uint32_t holding 30 bits (PyLong_SHIFT == 30, PyLong_MASK == (1 << 30) - 1).

Think of it as a hand-rolled big-endian-bytes, little-endian-limb number: base 2^30, least significant limb first. Textbook, but fast.

The tag: count, sign and flags

All of the metadata lives in the low bits of lv_tag:

c
// Include/internal/pycore_long.h
#define SIGN_MASK 3          /* low 2 bits: 1 - sign */
#define NON_SIZE_BITS 3     /* total low bits used */
#define IMMORTALITY_BIT_MASK (1 << 2)   /* small-int flag */

bits 0-1 encode the sign: 0 positive, 1 zero, 2 negative (i.e. sign = 1 - (tag & 3)).
bit 2 is set for the immortal small ints.
bits 3+ hold the digit count (tag >> 3).

So a single 64-bit word records “how many digits, which sign, and whether this is a cached small int”. _PyLong_DigitCount and _PyLong_IsCompact are just shifts and comparisons on this word.

The real win: there’s no separate “is this a small int” field, no side table, no vtable. The tag is the metadata.

Compact vs. long form

A value is compact when its tag is below 2 << 3, i.e. it has at most one digit and fits in a Py_ssize_t with a spare bit. Compact ints are the common case (anything in roughly [-2^62, 2^62) on a 64-bit build) and most arithmetic takes a fast path for them. The value is recovered with

c
// Include/cpython/longintrepr.h
static inline Py_ssize_t
_PyLong_CompactValue(const PyLongObject *op) {
    Py_ssize_t sign = 1 - (op->long_value.lv_tag & _PyLong_SIGN_MASK);
    if (sign == 0) { /* zero */
        assert(op->long_value.ob_digit[0] == 0);
    }
    return sign * (Py_ssize_t)op->long_value.ob_digit[0];
}

Non-compact values use the full digit array and the signed digit count.

Allocation

long_alloc (in Objects/longobject.c) is the single allocation routine:

c
// Objects/longobject.c
static PyLongObject *long_alloc(Py_ssize_t size) {
    assert(size >= 0);
    PyLongObject *result = NULL;
    if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
        PyErr_SetString(PyExc_OverflowError, "too many digits in integer");
        return NULL;
    }
    /* Fast operations for single digit integers assume at least one digit. */
    Py_ssize_t ndigits = size ? size : 1;

    if (ndigits == 1) {
        result = (PyLongObject *)_Py_FREELIST_POP(PyLongObject, ints);
    }
    if (result == NULL) {
        result = PyObject_Malloc(offsetof(PyLongObject, long_value.ob_digit) +
                                 ndigits * sizeof(digit));
        if (!result) { PyErr_NoMemory(); return NULL; }
        _PyObject_Init((PyObject *)result, &PyLong_Type);
        _PyLong_InitTag(result);
    }
    _PyLong_SetSignAndDigitCount(result, size != 0, size);
    ...
    return result;
}

Two points matter: the size is clamped by MAX_LONG_DIGITS, and single-digit ints (including zero) are pulled from a freelist of up to Py_ints_MAXFREELIST (100) compact objects before falling back to PyObject_Malloc. The freelist is LIFO and linked through the first word of the object.

The freelist is a recycling bin: dead one-digit ints get stacked up and reused, so the allocator stays out of the hot path for small arithmetic.

The small-int cache

A fixed array of immortal single-digit ints covers the range -_PY_NSMALLNEGINTS .. _PY_NSMALLPOSINTS - 1, i.e. -5 .. 1024:

c
// Include/internal/pycore_runtime_structs.h
#define _PY_NSMALLPOSINTS 1025
#define _PY_NSMALLNEGINTS 5
...
PyLongObject small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];

// Include/internal/pycore_long.h
#define _PyLong_SMALL_INTS _Py_SINGLETON(small_ints)
static inline PyObject* get_small_int(sdigit ival) {
    assert(IS_SMALL_INT(ival));
    return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + ival];
}

These are immortal (PEP 683) and carry the IMMORTALITY_BIT_MASK bit, so _PyLong_IsSmallInt recognizes them. PyLong_FromLong and friends return them directly via get_small_int, and _PyLong_Copy collapses any value in the range to the cached singleton. This is why a = 256; b = 256; a is b is True but 257 is 257 is not (257 is outside the cache).

Gotcha: is on ints is an implementation detail, not a language guarantee. The cache range is small on purpose — CPython traded a tiny bit of memory for skipping allocation, and 1024 is the sweet spot.

Dealloc and the freelist

c
// Objects/longobject.c
static void long_dealloc(PyObject *self) {
    if (_PyLong_IsSmallInt((PyLongObject *)self)) {
        _Py_SetImmortal(self);   /* accidental de-immortalizing guard */
        return;
    }
    if (PyLong_CheckExact(self) && _PyLong_IsCompact((PyLongObject *)self)) {
        _Py_FREELIST_FREE(ints, self, PyObject_Free);
        return;
    }
    Py_TYPE(self)->tp_free(self);   /* PyObject_Free */
}

Small ints can never be freed; compact exact ints go back to the freelist; everything else is freed directly. _PyLong_ExactDealloc is the specialized entry point used by the refcount fast path.

Addition with carry

Absolute-value addition is the canonical example of the digit algorithm:

c
// Objects/longobject.c
static PyLongObject *x_add(PyLongObject *a, PyLongObject *b) {
    Py_ssize_t size_a = _PyLong_DigitCount(a), size_b = _PyLong_DigitCount(b);
    ...
    /* Ensure a is the larger of the two. */
    if (size_a < size_b) { swap a, b; }
    z = long_alloc(size_a + 1);          /* one extra digit for carry */
    digit carry = 0;
    for (i = 0; i < size_b; ++i) {
        carry += a->long_value.ob_digit[i] + b->long_value.ob_digit[i];
        z->long_value.ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->long_value.ob_digit[i];
        z->long_value.ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->long_value.ob_digit[i] = carry;
    return long_normalize(z);          /* strip leading zero digits */
}

long_normalize then trims leading zero digits and adjusts the digit count (and the sign, for zero). The public PyLong_Add checks signs first: same sign uses x_add, opposite signs uses x_sub. Compact ints are handled even faster through _PyCompactLong_Add, which operates on the raw Py_ssize_t values.

That’s it — schoolbook addition with a carry. No Karatsuba here, because this operates on absolute values only after the sign has been split off.

Conversion to and from C `long`

PyLong_FromLong (and the unsigned/size_t variants) first tries the small and medium paths, then counts digits:

c
// Objects/longobject.c
PyObject *PyLong_FromLong(long ival) {
    PYLONG_FROM_INT(unsigned long, long, ival);
}

where the macro checks IS_SMALL_INT, then ival <= PyLong_MASK (single medium digit via _PyLong_FromMedium), and otherwise shifts by two PyLong_SHIFTs at a time to count digits before writing them least significant first.

Going the other way, PyLong_AsLong calls PyLong_AsLongAndOverflow, which for compact ints returns _PyLong_CompactValue directly and for larger ints accumulates digits into an unsigned long, checking overflow at each step. PyLong_AsSsize_t does the same with size_t/Py_ssize_t bounds. A negative result is only allowed when the value actually fits in the signed range.

Hashing

Compact ints hash to their own value (with -1 mapped to -2, since -1 means “error” in the hash protocol). For larger ints, long_hash folds the digits into a Py_uhash_t modulo PyHASH_MODULUS:

c
// Objects/longobject.c
static Py_hash_t long_hash(PyObject *obj) {
    PyLongObject *v = (PyLongObject *)obj;
    Py_uhash_t x;
    if (_PyLong_IsCompact(v)) {
        x = (Py_uhash_t)_PyLong_CompactValue(v);
        if (x == (Py_uhash_t)-1) x = (Py_uhash_t)-2;
        return x;
    }
    i = _PyLong_DigitCount(v);
    sign = _PyLong_NonCompactSign(v);
    /* unroll first (and on 64-bit, second) digit */
    --i; x = v->long_value.ob_digit[i];
    ...
    while (--i >= 0) {
        x = ((x << PyLong_SHIFT) & PyHASH_MODULUS) |
            (x >> (PyHASH_BITS - PyLong_SHIFT));
        x += v->long_value.ob_digit[i];
        if (x >= PyHASH_MODULUS) x -= PyHASH_MODULUS;
    }
    x = x * sign;
    if (x == (Py_uhash_t)-1) x = (Py_uhash_t)-2;
    return (Py_hash_t)x;
}

The rotation trick relies on 2**PyHASH_BITS ≡ 1 (mod PyHASH_MODULUS), so multiplying by 2**PyLong_SHIFT is a bit rotation rather than a big multiplication.

Comparison

c
// Objects/longobject.c
static Py_ssize_t long_compare(PyLongObject *a, PyLongObject *b) {
    if (_PyLong_BothAreCompact(a, b)) {
        return _PyLong_CompactValue(a) - _PyLong_CompactValue(b);
    }
    Py_ssize_t sign = _PyLong_SignedDigitCount(a) - _PyLong_SignedDigitCount(b);
    if (sign == 0) {
        Py_ssize_t i = _PyLong_DigitCount(a);
        sdigit diff = 0;
        while (--i >= 0) {
            diff = (sdigit)a->long_value.ob_digit[i] -
                   (sdigit)b->long_value.ob_digit[i];
            if (diff) break;
        }
        sign = _PyLong_IsNegative(a) ? -diff : diff;
    }
    return sign;
}

First compare by signed digit count (which encodes both magnitude length and sign), then fall back to a most-significant-first digit comparison. Same sign flips the result for negatives.

Memory layout summary

text

+---------------------------+  <- PyObject_Malloc result
| ob_refcnt                 |
+---------------------------+
| *ob_type  (&PyLong_Type)  |
+---------------------------+
| lv_tag   (count|sign|flags)|
+---------------------------+
| ob_digit[0]               |
| ob_digit[1]               |
| ...                       |
+---------------------------+

For a zero or single-digit value only ob_digit[0] is allocated (one digit), and the freelist recycles the whole PyLongObject. Multi-digit values allocate offsetof(...) + ndigits*sizeof(digit) bytes.

Key takeaways

int is a PyObject whose payload is _PyLongValue: one tag word plus a little-endian digit array of 30-bit (or 15-bit) limbs.
The tag packs digit count, sign and the small-int flag into lv_tag, enabling compact fast paths without a separate type.
Values in -5..1024 are immortal cached singletons; compact single-digit objects are recycled through a 100-deep freelist.
Arithmetic is schoolbook base-2^30 with carry; conversion, hashing and comparison all special-case compact ints first.