Speed up tuple comparisons for exact compact integers

[lesshaste]

Feature or enhancement

Proposal

tuple_richcompare() currently calls PyObject_RichCompareBool(..., Py_EQ) for each pair of corresponding tuple elements until it finds a mismatch.

When both elements are exact compact int objects, equality can be determined directly from _PyLong_CompactValue(), avoiding generic rich-comparison dispatch for every element in a long common prefix.

This could speed up comparisons such as:

a == b
a != b
a < b
a <= b
a > b
a >= b

when the tuples contain ordinary integers.

Current implementation

On current main, tuple_richcompare() searches for the first unequal pair with:

for (i = 0; i < vlen && i < wlen; i++) {
    int k = PyObject_RichCompareBool(vt->ob_item[i],
                                     wt->ob_item[i], Py_EQ);
    if (k < 0)
        return NULL;
    if (!k)
        break;
}

If a differing pair is found, == and != are resolved immediately. For the ordering operators, the differing elements are then compared again using:

return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);

Consequently, comparing two equal integer tuples of length 10,000 can perform 10,000 generic rich-comparison operations even though each comparison is between ordinary integers.

Similarly, tuples with a long common integer prefix perform a generic comparison for every element in that prefix.

Possible fast path

pycore_long.h already provides _PyLong_CheckExactAndCompact() and _PyLong_CompactValue().

tuple_richcompare() could therefore special-case a pair when both objects are exact compact integers:

PyObject *vitem = vt->ob_item[i];
PyObject *witem = wt->ob_item[i];

if (vitem == witem) {
    continue;
}

if (_PyLong_CheckExactAndCompact(vitem) &&
    _PyLong_CheckExactAndCompact(witem))
{
    Py_ssize_t a =
        _PyLong_CompactValue((PyLongObject *)vitem);
    Py_ssize_t b =
        _PyLong_CompactValue((PyLongObject *)witem);

    if (a == b) {
        continue;
    }

    break;
}

int k = PyObject_RichCompareBool(vitem, witem, Py_EQ);
if (k < 0) {
    return NULL;
}
if (!k) {
    break;
}

Objects/tupleobject.c would need to include pycore_long.h.

The existing generic path would remain unchanged for every other type.

A further small optimization is possible once the first differing elements are known. If they are also exact compact integers, the ordering operation could be evaluated directly:

Py_RETURN_RICHCOMPARE(a, b, op);

instead of calling PyObject_RichCompare().

That second optimization is optional; avoiding generic equality comparisons throughout a long integer prefix is the main opportunity.

Correctness

The shortcut is restricted to exact int objects.

This is important because integer subclasses may override comparison methods:

class MyInt(int):
    def __eq__(self, other):
        ...

Such objects would continue through PyObject_RichCompareBool() exactly as they do now.

Other numeric types including bool, float, Decimal, NumPy scalar types, etc. would also remain on the generic path.

For two exact compact integers, CPython's existing integer comparison already compares their compact values directly. long_compare() contains:

if (_PyLong_BothAreCompact(a, b)) {
    return _PyLong_CompactValue(a) - _PyLong_CompactValue(b);
}

so comparing _PyLong_CompactValue() values directly gives the same equality and ordering result.

The current PyObject_RichCompareBool() also treats identical objects as equal before generic dispatch. An explicit:

if (vitem == witem)
    continue;

preserves that behavior while avoiding even the compact-int tests in that case.

Tuple immutability means that the tuple contents and lengths cannot change as a side effect of comparing two exact integer elements. The existing implementation already explicitly relies on tuple immutability to reuse the cached tuple lengths across comparison calls.

Why this may be worthwhile

The avoided overhead occurs once per corresponding element, rather than once per Python operation.

For:

a = tuple(...)
b = tuple(...)

a == b

with a long common integer prefix, the current cost includes potentially thousands of calls to PyObject_RichCompareBool(...).

The exact compact-int path would replace each of those with a small number of inline checks, two compact-value loads, and a machine integer comparison.

This is particularly relevant for:

• equality of long integer tuples;
• inequality where the first mismatch occurs late;
• lexicographical ordering of tuples with long common prefixes;
• tuples used as structured numeric records or keys.

Benchmark

A patch should be benchmarked with pyperf on current main.

It is important that the benchmark include equal integer objects that are not merely identical references, since PyObject_RichCompareBool() already has a fast identity check.

For example:

import pyperf

runner = pyperf.Runner()

for n in (10, 100, 1_000, 10_000):
    base = 100_000

    # Construct separately so corresponding ints are equal
    # but generally distinct Python objects.
    a = tuple(range(base, base + n))
    b = tuple(range(base, base + n))

    c = tuple(range(base, base + n))
    c = c[:-1] + (base + n + 1,)

    runner.timeit(
        f"equal integer tuples, n={n}",
        stmt="a == b",
        globals={"a": a, "b": b},
    )

    runner.timeit(
        f"late unequal integer tuples, n={n}",
        stmt="a == c",
        globals={"a": a, "c": c},
    )

    runner.timeit(
        f"ordered integer tuples, n={n}",
        stmt="a < c",
        globals={"a": a, "c": c},
    )

Benchmarks should also include:

• tuples whose corresponding elements are identical objects, to make sure that case does not regress;
• tuples of strings or arbitrary objects, to check the generic path;
• mixed-type tuples;
• short tuples, where additional fast-path tests must not outweigh the saving.

Scope

I suggest starting with tuples because the implementation is small and tuple immutability makes the fast path particularly simple.

If the change proves worthwhile, a similar idea might later be investigated for list comparisons, where mutation and free-threading require more care.

Related issues

• Speed up tuple search operations for exact compact integers #156711 proposes the corresponding exact-compact-integer fast path for tuple search operations.
• Add a self-comparison fast path for some built-ins types #141858 proposes self-comparison fast paths for built-in containers. This proposal is distinct because its main target is equal but non-identical exact compact integers in long common prefixes.

Has this already been discussed elsewhere?

This is a minor performance enhancement which does not need previous discussion elsewhere.

Links to previous discussion of this feature

• Speed up tuple search operations for exact compact integers #156711
• Add a self-comparison fast path for some built-ins types #141858

[picnixz]

This is purely AI generated and does not provide any benchmark results and thus we have no way to evaluate this proposal. Please do some work before opening issues.

[lesshaste]

I implemented and benchmarked a prototype against the same current-main baseline used for #156711.

Setup and validation

• CPython: d7f9c6400f49633221983d0c454cf27ecb0302ba (3.16.0a0)
• Build: ./configure --enable-optimizations=no && make -j2
• Compiler flags reported by pyperf: -DNDEBUG -g -O3
• GCC 13.3.0; AMD Ryzen 5 3400G; Linux 7.0.0-28-generic x86-64
• pyperf 2.10.0; sequential standard runs
• test_tuple: PASS (38 tests)
• Targeted subclass/mixed-type/all-six-operators/NaN assertions: PASS

I tried three implementation shapes:

1. Per-element identity and compact-int checks: strong integer gains, but generic string comparisons regressed about 4%.
2. A leading compact-int loop followed by the generic loop inline: integer gains remained, but code-layout effects produced 7–8% string regressions.
3. Final measured version: dispatch long compact-int tuples to a separate helper, preserving the existing generic loop unchanged. A minimum length of 16 avoids paying the specialization probe for short tuples.

The final patch is confined to Objects/tupleobject.c (54 insertions). The helper compares a leading compact-int run directly and resumes generic comparison at the first other type. A differing compact pair is resolved directly with Py_RETURN_RICHCOMPARE.

Integer results

Benchmark	Baseline	Patched	Change
equal distinct, n=10	108 ns	108 ns	no significant change
late unequal, n=10	108 ns	108 ns	no significant change
ordered, n=10	115 ns	113 ns	1.01x faster
equal distinct, n=100	669 ns	186 ns	3.60x faster
late unequal, n=100	671 ns	190 ns	3.54x faster
ordered, n=100	682 ns	189 ns	3.61x faster
equal distinct, n=1,000	6.29 us	1.59 us	3.97x faster
late unequal, n=1,000	6.32 us	1.60 us	3.94x faster
ordered, n=1,000	6.21 us	1.62 us	3.84x faster
equal distinct, n=10,000	64.8 us	17.0 us	3.81x faster
late unequal, n=10,000	64.0 us	16.8 us	3.80x faster
ordered, n=10,000	64.7 us	17.5 us	3.69x faster

Generic and identity controls

This prototype is not regression-free, and I do not want to hide that:

• distinct strings: n=10 statistically unchanged; n=1,000 1.03x slower; n=10,000 1.02x slower;
• mixed numeric tuples: n=10 1.02x slower; n=1,000 1.02x slower; n=10,000 statistically unchanged;
• distinct tuple containers whose corresponding elements are identical references:
  • n=10: 58.6 ns -> 65.6 ns (1.12x slower)
  • n=1,000: 2.49 us -> 2.60 us (1.04x slower)
  • n=10,000: no significant change;
• tuple self-comparison:
  • n=10: 59.0 ns -> 66.2 ns (1.12x slower)
  • n=1,000: 2.46 us -> 2.61 us (1.06x slower)
  • n=10,000: 24.6 us -> 25.5 us (1.04x slower).

I initially used tuple(existing_tuple) for the identical-element control, then caught that it returns the same tuple. I corrected the fixture to create two distinct tuple containers and separately measured true self-comparison; the numbers above are the corrected results.

So the benchmark confirms a large compact-int opportunity, but this exact dispatch shape still has tradeoffs that need discussion or further implementation work.

Main reproduction script

import pyperf

runner = pyperf.Runner()

for n in (10, 100, 1_000, 10_000):
    base = 100_000
    a = tuple(range(base, base + n))
    b = tuple(range(base, base + n))
    late = b[:-1] + (base + n + 1,)
    assert all(x is not y for x, y in zip(a, b))
    runner.timeit(f"int equal distinct n={n}", "a == b",
                  globals={"a": a, "b": b})
    runner.timeit(f"int late unequal n={n}", "a == late",
                  globals={"a": a, "late": late})
    runner.timeit(f"int ordered n={n}", "a < late",
                  globals={"a": a, "late": late})

for n in (10, 1_000, 10_000):
    a = tuple(("value-" + str(i)).encode().decode() for i in range(n))
    b = tuple(("value-" + str(i)).encode().decode() for i in range(n))
    assert all(x == y and x is not y for x, y in zip(a, b))
    runner.timeit(f"str equal distinct n={n}", "a == b",
                  globals={"a": a, "b": b})

    mixed_a = tuple(i if i % 2 == 0 else float(i) for i in range(n))
    mixed_b = tuple(i if i % 2 == 0 else float(i) for i in range(n))
    runner.timeit(f"mixed numeric equal n={n}", "a == b",
                  globals={"a": mixed_a, "b": mixed_b})

Corrected identity control:

shared = object()
for n in (10, 1_000, 10_000):
    a = tuple([shared] * n)
    b = tuple([shared] * n)
    assert a is not b
    runner.timeit(f"distinct tuples, identical elements n={n}", "a == b",
                  globals={"a": a, "b": b})
    runner.timeit(f"tuple self comparison n={n}", "a == a",
                  globals={"a": a})

Commands:

./python bench_tuple_compare.py --quiet -o baseline.json
./python bench_tuple_compare.py --quiet -o patched.json
./python -m pyperf compare_to baseline.json patched.json --table

SHA-256:

• main benchmark script: 1853f385d02f97acef70e9cf7297d23bfa142937ee257082d50ff0d72b7e6f75
• corrected identity-control script: 4c0ddfe9bad81c055d40da39740b096d6c8f043a9df93d5a1b7a5e21e8eb1ef7
• baseline main JSON: d2bc8820cac9746eeeb916e4c941b919c81f20a3d85bc78060c8aef38aecf45c
• patched main JSON: 10462dc478a26ed918ceff7326ae3948a79d7b81b02ecb20e394dddd4ce2cd0d
• baseline identity JSON: e26580467001eb9e50d532995307ae06a76d91fceaf1767a453ee1bad7d7480c
• patched identity JSON: f570be375783637175a7987592896373398f4dba598932f0e2e0bd78fb0ae94c

[picnixz]

Since this regresses other types I do not think it is good. Note that purely AI comments and PRs will be rejected because no human contributed to those additions.

[lesshaste]

It's my first attempt at a cpython performance issue. I did put a lot of effort into choosing the issue and cajoling the ai to do the right things.

[picnixz]

And this is not what we want as a contribution. I would suggest trying to find simpler issues. Contributions solely by AI are not meaningful.