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.

Sign up for GitHub

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

Jump to bottom

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

Closed
orenmn mannequin opened this issue Jun 4, 2016 · 4 comments
Closed

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

orenmn mannequin opened this issue Jun 4, 2016 · 4 comments
Assignees
@mdickinson
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@orenmn
Copy link
Mannequin

orenmn mannequin commented 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']
    @orenmn
    Copy link
    Mannequin Author

    orenmn mannequin commented Jun 4, 2016

    ------------ 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.

    @orenmn orenmn mannequin added interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Jun 4, 2016
    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Aug 29, 2016

    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

    @mdickinson
    Copy link
    Member

    Agreed with the analysis and proposed solution. Thanks!

    @mdickinson mdickinson self-assigned this Aug 29, 2016
    @orenmn
    Copy link
    Mannequin Author

    orenmn mannequin commented Aug 29, 2016

    Thanks for the review, Mark :)

    @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
    Assignees

    @mdickinson mdickinson

    Labels
    interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    1 participant
    @mdickinson