Skip to content

a potential future bug and an optimization that mostly undermines performance in long_invert #71401

Closed
Closed
a potential future bug and an optimization that mostly undermines performance in long_invert#71401
Assignees
mdickinson
Labels
interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

Description

@orenmn
orenmn
mannequin
opened on Jun 4, 2016
BPO 27214
Nosy @mdickinson, @serhiy-storchaka, @orenmn
Files
  • proposedPatches.diff: proposed patches diff file
  • CPythonTestOutput.txt: test output of CPython without my patches (tested on my PC)
  • patchedCPythonTestOutput.txt: test output of CPython with my patches (tested on my PC)
    		•

    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/mdickinson'
closed_at = <Date 2016-08-29.15:41:22.866>
created_at = <Date 2016-06-04.08:05:36.818>
labels = ['interpreter-core', 'performance']
title = 'a potential future bug and an optimization that mostly undermines performance in long_invert'
updated_at = <Date 2016-08-29.15:50:03.022>
user = 'https://github.com/orenmn'

    bugs.python.org fields:

    activity = <Date 2016-08-29.15:50:03.022>
actor = 'Oren Milman'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2016-08-29.15:41:22.866>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2016-06-04.08:05:36.818>
creator = 'Oren Milman'
dependencies = []
files = ['43186', '43187', '43188']
hgrepos = []
issue_num = 27214
keywords = ['patch']
message_count = 4.0
messages = ['267244', '273865', '273866', '273867']
nosy_count = 4.0
nosy_names = ['mark.dickinson', 'python-dev', 'serhiy.storchaka', 'Oren Milman']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue27214'
versions = ['Python 3.6']

    Activity

    1. orenmn commented on Jun 4, 2016

      @orenmn
      orenmnmannequin
      on Jun 4, 2016
      MannequinAuthor

      ------------ the current state ------------
      long_invert first checks whether v is a single-digit int. If it is, it simply does 'return PyLong_FromLong(-(MEDIUM_VALUE(v) + 1));'.
      Otherwise, long_invert does (edited for brevity) 'x = long_add(v, PyLong_FromLong(1));', and then negates x in-place.

      In other words, long_invert assumes long_add hasn't returned a reference to an element of small_ints.
      However, if all of the following conditions are true:
      * NSMALLNEGINTS is maximized (i.e. NSMALLNEGINTS == 2 ** PyLong_SHIFT - 1).
      * long_add is changed in such a way that if someone does (in Python) '-2 ** PyLong_SHIFT + 1' while NSMALLNEGINTS is maximized, long_add would return a reference to an element of small_ints. (Actually, I have recently opened an issue that proposes such a change - http://bugs.python.org/issue27145.)
      * long_invert is called for (-2 ** PyLong_SHIFT).
      Then long_invert would negate in-place an element of small_ints.

      In addition, because long_invert first checks whether v is a single-digit int, calling maybe_small_long before returning would save up memory only in case both of the following conditions are true:
      * NSMALLPOSINTS is maximized (i.e. NSMALLPOSINTS == 2 ** PyLong_SHIFT).
      * long_invert is called for (-2 ** PyLong_SHIFT).
      So the call to maybe_small_long introduces a performance penalty for every case where v is a multiple-digit int (and long_invert doesn't fail), while the only case where it actually saves up memory is the aforementioned corner case.

      ------------ the proposed changes ------------
      Both of the proposed changes are in Objects/longobject.c in long_invert:
      1. Replace the in-place negation with a call to _PyLong_Negate, which safely negates an int.

      2. Remove the call to maybe_small_long.

maybe_small_long was added to long_invert in revision 48567, as part of an effort to wipe out different places in the code where small_ints could be used (and saved up memory), but was not. I am not sure why maybe_small_long was also added to long_invert back then, even though it mostly undermines performance.

      ------------ diff ------------
      The patches diff is attached.

      ------------ tests ------------
      I built the patched CPython for x86, and played with it a little. Everything seemed to work as usual.

      In addition, I ran 'python_d.exe -m test -j3' (on my 64-bit Windows 10) with and without the patches, and got quite the same output.
      the outputs of both runs are attached.

    2. orenmn
      added
      interpreter-core(Objects, Python, Grammar, and Parser dirs)
      performancePerformance or resource usage
      on Jun 4, 2016

    3. python-dev commented on Aug 29, 2016

      @python-dev
      python-devmannequin
      on Aug 29, 2016
      Mannequin

      New changeset 6e1d38674b17 by Mark Dickinson in branch 'default':
      Issue bpo-27214: Fix potential bug and remove useless optimization in long_invert. Thanks Oren Milman.
      https://hg.python.org/cpython/rev/6e1d38674b17

    4. mdickinson commented on Aug 29, 2016

      @mdickinson
      mdickinson
      on Aug 29, 2016
      Member

      Agreed with the analysis and proposed solution. Thanks!

    5. mdickinson
      closed this as completedon Aug 29, 2016
    6. mdickinson
      self-assigned this
      on Aug 29, 2016

    7. orenmn commented on Aug 29, 2016

      @orenmn
      orenmnmannequin
      on Aug 29, 2016
      MannequinAuthor

      Thanks for the review, Mark :)

    8. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions