Caching/interning of small ints sometimes fails

[stevendaprano]

BPO	46961
Nosy	@stevendaprano, @brandtbucher, @sweeneyde
PRs	gh-91117: Ensure integer mod and pow operations use cached small ints #31843

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/brandtbucher'
closed_at = None
created_at = <Date 2022-03-08.15:48:45.811>
labels = ['interpreter-core', 'type-bug', '3.10']
title = 'Caching/interning of small ints sometimes fails'
updated_at = <Date 2022-03-13.09:38:02.095>
user = 'https://github.com/stevendaprano'

bugs.python.org fields:

activity = <Date 2022-03-13.09:38:02.095>
actor = 'AlexWaygood'
assignee = 'brandtbucher'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2022-03-08.15:48:45.811>
creator = 'steven.daprano'
dependencies = []
files = []
hgrepos = []
issue_num = 46961
keywords = ['patch']
message_count = 4.0
messages = ['414762', '414764', '414766', '415030']
nosy_count = 3.0
nosy_names = ['steven.daprano', 'brandtbucher', 'Dennis Sweeney']
pr_nums = ['31843']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue46961'
versions = ['Python 3.10']

[stevendaprano]

I'm reluctant to call this a bug, as small int interning/caching is an implementation detail and there are no hard guarantees made.

But on the other hand, it seems that the intention is that small ints such as 0, 1 and 2 should be cached. Here are some examples where they are not. Intentional or a bug?

>>> x = 1
>>> y = pow(2, 31, 2**31-1)
>>> y == x
True
>>> y is x
False


>>> x = 2
>>> y = pow(2, 31, 2**31-2)
>>> y == x
True
>>> y is x
False

It also affects values which are presumably constant-folded at compile time:

>>> x = 1
>>> y = 2**31 % (2**31 - 1)
>>> z = 2**31 % (2**31 - 1)
>>> x == y == z
True
>>> x is y
False
>>> y is z
False
>>> x is z
False

But if you run the code in exec, the value is interned:

>>> code = """
... x = 1
... y = 2**31 % (2**31-1)
... """
>>> dis(code)
  2           0 LOAD_CONST               0 (1)
              2 STORE_NAME               0 (x)

  3           4 LOAD_CONST               0 (1)
              6 STORE_NAME               1 (y)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE
>>> exec(code)
>>> x is y
True

Also affects zero:

>>> x = 0
>>> y = 2**29 % (2**29)
>>> x is y
True
>>> y = 2**30 % (2**30)
>>> x is y
False

First noted here:

https://discuss.python.org/t/cached-integer-id-on-high-calculations/14128/1

>>> sys.version
'3.10.0 (default, Oct 28 2021, 20:43:43) [GCC 8.3.1 20190223 (Red Hat 8.3.1-2)]'

[AlexWaygood]

I think this might be a duplicate of bpo-46361?

[brandtbucher]

Related, except this seems to be happening in long_pow. I’ll take a look at it today.

[sweeneyde]

I believe the issue is the usage of the x_divrem function.

x_divrem always returns fresh ints, never cached small ints. This behavior is relied upon in the long_true_divide function, as it mutates the returned quotient at the line """x->ob_digit[0] = low & ~(2U*mask-1U);""".

The other uses of x_divrem account for this when handling the *quotient*, but apparently missed checking for small ints in the *remainder*.

uses of x_divrem:
- long_divrem
- uses maybe_small_long on quotient
- doesn't check if remainder is small <---- oops
- long_rem
- throws away quotient
- doesn't check if remainder is small <---- oops
- long_true_divide
- modifies the quotient
- throws away remainder

Possible patches to fix it:

1. Modify long_divrem and long_rem to check for small remainders, in addition to the small-quotient checks they already do.
2. Modify x_divrem to check for small remainders, but still always return fresh quotients.
3. Modify x_divrem to return cached quotients and remainders, and modify long_true_divide to make a copy before mutating.

I'd lean towards #1, since that quotient check already exists.
In #2, the mismatch of checking/not checking between quotient/remainder would be confusing.
In #3, an extra int allocation gets added to integer true divide, which isn't ideal.