Speed up `range.__contains__` and `range.count()` for compact ints

[jeffchen006]

Feature or enhancement

Proposal

range.__contains__ (and range.count) currently route every exact-int or
bool needle through range_contains_long(), which does the whole membership
test through the abstract number API: three PyObject_RichCompareBool() calls,
a PyNumber_Subtract(), a PyNumber_Remainder(), and a final
PyObject_RichCompareBool() — with two intermediate PyLongObjects allocated
along the way.

That generality is only needed when one of the operands does not fit in a
machine word. In the overwhelmingly common case, the needle and all three range
fields are compact ints (a single digit, so bounded by PyLong_MASK), and the
entire test is a few comparisons and one remainder in Py_ssize_t.

I would like to add a compact fast path to range_contains_long():

• if the needle and r->start / r->stop / r->step are all compact, do the
  bounds check and the divisibility check in Py_ssize_t;
• otherwise fall through to the existing implementation, unchanged.

Because compact ints hold one digit, their values are bounded by PyLong_MASK
(2**30 - 1 on 64-bit builds), which leaves a spare bit so that
value - start cannot overflow Py_ssize_t — this holds on 15-bit-digit and
32-bit builds too. C's % and Python's % differ in the sign of a non-zero
result but never in whether the result is zero, so the == 0 divisibility test
is unchanged.

range's start/stop/step are always exact ints: make_range_object() is
the only place they are assigned, and every caller supplies either a
PyNumber_Index() result or PyNumber_* arithmetic over ints.

Measurements

--enable-optimizations=no --with-pydebug=no CFLAGS="-O3 -g0", gcc 13.3,
x86-64 Linux. Baseline and patched interpreters interleaved round by round,
120 samples per arm, min per-loop ns. A no-op control case (needle, a bare
name load) is included to show the harness is unbiased.

microbenchmark	before	after
999 in range(0, 1000, 3)	59.5 ns	14.8 ns	4.02x
998 in range(0, 1000, 3) (miss)	63.1 ns	14.0 ns	4.49x
997 in range(1000, 0, -3)	56.4 ns	14.0 ns	4.03x
True in range(0, 1000, 3)	68.3 ns	14.8 ns	4.61x
range(0, 1000, 3).count(999)	67.9 ns	20.6 ns	3.29x
10**100 in range(0, 1000, 3) (fallback)	36.2 ns	35.3 ns	1.03x
999 in range(0, 10**100, 3) (fallback)	59.5 ns	57.6 ns	1.03x
6.0 in range(0, 8, 3) (non-int, unaffected)	116.2 ns	114.7 ns	1.01x
control: needle	7.46 ns	7.50 ns	0.99x

Every path that falls back is neutral within noise.

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere.

Linked PRs

Linked PRs

• gh-155385: Speed up range.__contains__ for compact ints #155386

[pochmann]

Is it actually common to do this at all? I doubt I ever have other than out of curiosity.