Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Caching/interning of small ints sometimes fails #91117

Closed
stevendaprano opened this issue Mar 8, 2022 · 4 comments
Closed

Caching/interning of small ints sometimes fails #91117

stevendaprano opened this issue Mar 8, 2022 · 4 comments
Assignees
Labels
3.10 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error

Comments

@stevendaprano
Copy link
Member

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
    Copy link
    Member Author

    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)]'

    @stevendaprano stevendaprano added 3.10 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error labels Mar 8, 2022
    @AlexWaygood
    Copy link
    Member

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

    @brandtbucher
    Copy link
    Member

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

    @brandtbucher brandtbucher self-assigned this Mar 8, 2022
    @sweeneyde
    Copy link
    Member

    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.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.10 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error
    Projects
    None yet
    Development

    No branches or pull requests

    5 participants