Speed up tuple search operations for exact compact integers

[lesshaste]

Feature or enhancement

Proposal

tuple.index(), tuple.count(), and tuple membership currently use PyObject_RichCompareBool(..., Py_EQ) for every element examined, even when both the tuple element and the searched-for value are exact compact int objects.

For two exact compact integers, equality can be determined directly from _PyLong_CompactValue(), avoiding generic rich-comparison dispatch on every scanned element. Because these comparisons occur inside linear scans, the potential saving scales with tuple length.

Current implementation

On current main, tuple.index() contains:

for (i = start; i < stop; i++) {
    int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
    if (cmp > 0)
        return PyLong_FromSsize_t(i);
    else if (cmp < 0)
        return NULL;
}

tuple.count() similarly calls:

PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ)

for each element, and tuple_contains() uses the same generic rich-comparison operation.

Therefore code such as:

t = tuple(range(10_000))

9999 in t
t.index(9999)
t.count(-1)

can execute thousands of generic rich-comparison calls even though each comparison is between ordinary exact integers.

Possible fast path

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

If the searched-for value is an exact compact integer, its C value could be extracted once before the scan:

bool compact_value = _PyLong_CheckExactAndCompact(value);
Py_ssize_t needle;

if (compact_value) {
    needle = _PyLong_CompactValue((PyLongObject *)value);
}

The loop could then use direct comparison whenever the current tuple element is also an exact compact integer:

int cmp;

if (compact_value && _PyLong_CheckExactAndCompact(item)) {
    cmp = (_PyLong_CompactValue((PyLongObject *)item) == needle);
}
else {
    cmp = PyObject_RichCompareBool(item, value, Py_EQ);
}

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

The pattern could potentially be shared by:

• tuple_contains()
• tuple_index_impl()
• tuple_count_impl()

An implementation could also branch once on whether value is an exact compact integer and use a separate loop for that case, to avoid adding an unnecessary per-iteration condition to the normal non-integer path.

Semantics

The shortcut would only be used when both operands are exact compact int objects.

For exact integers, CPython's existing integer comparison already compares compact values directly in long_compare(), so direct comparison of _PyLong_CompactValue() produces the same equality result.

No user-defined comparison method can be involved when both operands are exact int objects.

Cases involving integer subclasses or other numeric types would therefore continue through the existing generic path, for example:

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

t = (1, 2, MyInt(3))

Similarly, comparisons involving bool, float, Decimal, NumPy scalar types, or arbitrary objects would remain generic.

The optimization also cannot cause Python-level side effects while comparing two exact integers.

Why this may be worthwhile

The expensive operation being removed occurs once per examined tuple element.

For a tuple containing thousands of integers, thousands of calls to PyObject_RichCompareBool(...) could instead become a compact-int type check, value load, and machine equality comparison.

This makes the opportunity different from optimizations that save only a fixed amount of function-call overhead: the saving grows with the number of elements scanned.

The relevant workloads are:

value in tuple_of_ints
tuple_of_ints.index(value)
tuple_of_ints.count(value)

Benchmark

A patch should be benchmarked on current main with pyperf, including at least:

• membership hit near the end;
• membership miss;
• index() hit near the end;
• count() miss;
• several tuple sizes such as 10, 100, 1,000, and 10,000;
• non-integer tuples to check that the additional specialization does not regress the generic path.

For example:

t = tuple(range(10_000))
needle_hit = 9_999
needle_miss = -1

needle_hit in t
needle_miss in t
t.index(needle_hit)
t.count(needle_miss)

Possible follow-up

If this proves beneficial for tuples, similar exact-integer shortcuts might be worth investigating for list search operations.

Tuples seem like a good first target because their contents are immutable and the existing search loops are particularly simple.

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

No response

[lesshaste]

I implemented a prototype against current main and ran baseline/patched pyperf suites.

Setup

• CPython: d7f9c6400f49633221983d0c454cf27ecb0302ba (3.16.0a0)
• Build: ./configure --enable-optimizations=no && make -j2
• Compiler flags reported by pyperf: -DNDEBUG -g -O3
• Compiler: GCC 13.3.0
• Machine: AMD Ryzen 5 3400G, 4 cores / 8 threads
• OS: Linux 7.0.0-28-generic x86-64
• pyperf: 2.10.0; sequential standard runs (not --fast)
• CPU governor: schedutil (so the JSONs contain the usual pyperf stability warnings)

The first prototype tested every item type inside a specialized loop. A pilot detected 3–6% regressions when an exact-int needle scanned a string tuple. I revised it to scan only a leading run of compact ints, then fall back once to the original generic loop. The results below are for that revised version.

The patch changes only Objects/tupleobject.c (48 insertions, 4 deletions): exact compact-int needles scan a leading compact-int run directly in tuple_contains(), tuple_index_impl(), and tuple_count_impl(); the first non-compact element resumes the existing generic loop.

Correctness

• ./python -m test test_tuple -j1: PASS (38 tests)
• Additional targeted assertions: PASS
  • membership/index/count for compact ints
  • all six tuple comparison operators
  • int subclasses with observable __eq__
  • bool, mixed float/int, and identity-sensitive NaN behavior

Integer results

Benchmark	Baseline	Patched	Change
contains hit, n=10	104 ns	32.3 ns	3.22x faster
contains miss, n=10	105 ns	31.4 ns	3.35x faster
index hit, n=10	105 ns	37.8 ns	2.77x faster
count miss, n=10	111 ns	36.2 ns	3.08x faster
contains hit, n=100	666 ns	131 ns	5.07x faster
contains miss, n=100	685 ns	128 ns	5.34x faster
index hit, n=100	661 ns	135 ns	4.90x faster
count miss, n=100	655 ns	141 ns	4.65x faster
contains hit, n=1,000	6.25 us	1.05 us	5.93x faster
contains miss, n=1,000	6.29 us	1.05 us	6.01x faster
index hit, n=1,000	6.20 us	1.00 us	6.18x faster
count miss, n=1,000	6.16 us	1.15 us	5.36x faster
contains hit, n=10,000	61.9 us	10.6 us	5.83x faster
contains miss, n=10,000	61.8 us	10.3 us	5.99x faster
index hit, n=10,000	61.8 us	9.61 us	6.43x faster
count miss, n=10,000	60.9 us	11.1 us	5.50x faster

Regression controls

The suite also measured:

• string-needle/string-tuple membership and count at n=10, 1,000, and 10,000;
• exact-int needle/string-tuple membership and count at n=10, 1,000, and 10,000;
• identity hits for arbitrary objects at n=10 and 10,000.

pyperf compare_to reported no significant slowdown in any control. Four controls were statistically unchanged; the others measured 1–15% faster, which I would treat as run-to-run noise rather than a claimed benefit.

Reproduction

import pyperf

runner = pyperf.Runner()

for n in (10, 100, 1_000, 10_000):
    base = 100_000
    ints = tuple(range(base, base + n))
    hit = base + n - 1
    miss = base - 1
    runner.timeit(f"int contains hit n={n}", "hit in values",
                  globals={"values": ints, "hit": hit})
    runner.timeit(f"int contains miss n={n}", "miss in values",
                  globals={"values": ints, "miss": miss})
    runner.timeit(f"int index hit n={n}", "values.index(hit)",
                  globals={"values": ints, "hit": hit})
    runner.timeit(f"int count miss n={n}", "values.count(miss)",
                  globals={"values": ints, "miss": miss})

for n in (10, 1_000, 10_000):
    strings = tuple(str(i) for i in range(n))
    string_miss = "not present"
    runner.timeit(f"str contains miss n={n}", "needle in values",
                  globals={"values": strings, "needle": string_miss})
    runner.timeit(f"str count miss n={n}", "values.count(needle)",
                  globals={"values": strings, "needle": string_miss})
    runner.timeit(f"int needle string tuple miss n={n}", "needle in values",
                  globals={"values": strings, "needle": -1})
    runner.timeit(f"int needle string tuple count n={n}",
                  "values.count(needle)",
                  globals={"values": strings, "needle": -1})

shared = object()
for n in (10, 10_000):
    identical = (shared,) * n
    runner.timeit(f"identical object contains n={n}", "needle in values",
                  globals={"values": identical, "needle": shared})

Commands:

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

SHA-256:

• benchmark script: 27aa7926261509143310662ff770c52d7afdab40e5324aec8d80f7f9e448d4ab
• baseline JSON: eed3868576c8cf090215ffb40131ba8b39ac752c4401bb5cd7849eb404814520
• patched JSON: 227b6897a8a422f8cccbe35653399aca0d654b7877f864b917e022cc85c1e0d6

These results support the optimization, with the leading-run/fallback-once shape avoiding the mixed-type regression seen in the initial prototype.

[picnixz]

I think this can be reasonable but I am not very fond of specializing this for ints and tuple of ints because this is not necessarily the most relevant. How often do we have large tuples with compact ints like that? it feels wrong to do it only for compact ints (unless there already exist fast paths for those in tuples?)