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

redundant checks and a weird use of goto statements in long_rshift #71409

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

redundant checks and a weird use of goto statements in long_rshift #71409

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

Comments

@4e331a12-c2bb-4cd1-b83c-dcc766e8fbf8
Copy link
Mannequin

orenmn mannequin commented Jun 4, 2016

BPO 27222
Nosy @mdickinson, @serhiy-storchaka, @orenmn
PRs
  • [Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
  • 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-09-17.16:52:03.947>
    created_at = <Date 2016-06-04.19:54:27.179>
    labels = ['interpreter-core', '3.7', 'performance']
    title = 'redundant checks and a weird use of goto statements in long_rshift'
    updated_at = <Date 2017-03-31.16:36:33.721>
    user = 'https://github.com/orenmn'

    bugs.python.org fields:

    activity = <Date 2017-03-31.16:36:33.721>
    actor = 'dstufft'
    assignee = 'mark.dickinson'
    closed = True
    closed_date = <Date 2016-09-17.16:52:03.947>
    closer = 'mark.dickinson'
    components = ['Interpreter Core']
    creation = <Date 2016-06-04.19:54:27.179>
    creator = 'Oren Milman'
    dependencies = []
    files = ['43207', '43208', '43209']
    hgrepos = []
    issue_num = 27222
    keywords = ['patch']
    message_count = 4.0
    messages = ['267308', '276290', '276803', '276804']
    nosy_count = 4.0
    nosy_names = ['mark.dickinson', 'python-dev', 'serhiy.storchaka', 'Oren Milman']
    pr_nums = ['552']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue27222'
    versions = ['Python 3.7']

    @4e331a12-c2bb-4cd1-b83c-dcc766e8fbf8
    Copy link
    Mannequin Author

    orenmn mannequin commented Jun 4, 2016

    ------------ current state ------------

    1. long_rshift first checks whether a is a negative int. If it is, it does (edited for brevity) 'z = long_invert(long_rshift(long_invert(a), b));'.
      Otherwise, it calculates the result of the shift and stores it in z. In this block, there is a check whether a is a negative int.

    The second check was always there - since revision 443, in which long_rshift was first added. However, in revision 590, the first aforementioned check (whether a is a negative int), along with a (edited for brevity) 'return long_invert(long_rshift(long_invert(a), b));' were added, but the second check whether a is a negative int wasn't removed, and remained there to this day.

    1. Ultimately, long_rshift does 'return (PyObject *) maybe_small_long(z);' for both cases (whether a is a negative int or not).
      Calling maybe_small_long in case a is a negative int is redundant, as long_invert returns (in case it doesn't fail) by either doing 'return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));' or 'return (PyObject *)maybe_small_long(x);'. In both cases, long_invert would return a reference to an element of small_ints if it should.

    Calls to maybe_small_long were added both to long_rshift and long_invert in revision 48567, as part of an effort to wipe out different places in the code where small_ints could be used (to save up memory), but was not. I am not sure why maybe_small_long was added to long_rshift where it would be redundant in case a is a negative int.

    1. In different cases of failure, long_rshift does 'goto rshift_error;'.
      The destination of these goto statements is actually a return statement that would also be reached in almost any case of success (except for a certain case in which the result of the shift is obviously zero).

    That goto was added in revision 15725. Back then, CONVERT_BINOP was added, and calling it in long_rshift required calling Py_DECREF for a and b before returning.
    Later on, in revision 43313, CONVERT_BINOP was removed, along with the calls to Py_DECREF it required, but the goto was left untouched, and remained there to this day.

    ------------ proposed changes ------------
    All of the proposed changes are in Objects/longobject.c in long_rshift:
    1. Remove the check whether a is a negative int in the block that gets executed in case a is not a negative int.

    2. Move the call to maybe_small_long inside the block that runs in case a is not a negative int.
    
    3. Replace every 'goto rshift_error;' with a 'return NULL;', and remove the rshift_error label. 
    
    I could have kept the goto statements, with 'return (PyObject *)z;' as their destination, but I believe it would have been less clear. Also, there are many similar places in longobject.c where 'return NULL;' is done on failure.
    

    ------------ diff ------------
    The proposed patches diff file is attached.

    ------------ tests ------------
    I built the patched CPython for x86, and played with it a little. Everything seemed to work as usual.
    Specifically, I did:
    for i in range(10000):
    if not all(smallInt is ((smallInt << i) >> i) for (
    smallInt) in range(-5, 257)):
    break
    print(i)
    And indeed 9999 was printed.

    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.

    @4e331a12-c2bb-4cd1-b83c-dcc766e8fbf8 orenmn mannequin added interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Jun 4, 2016
    @4e331a12-c2bb-4cd1-b83c-dcc766e8fbf8 orenmn mannequin added the 3.7 only security fixes label Sep 13, 2016
    @mdickinson
    Copy link
    Member

    Sorry, this fell off my list of things to look at.

    @mdickinson mdickinson self-assigned this Sep 13, 2016
    @1762cc99-3127-4a62-9baf-30c3d0f51ef7
    Copy link
    Mannequin

    python-dev mannequin commented Sep 17, 2016

    New changeset 21b70c835b5b by Mark Dickinson in branch 'default':
    Issue bpo-27222: various cleanups in long_rshift. Thanks Oren Milman.
    https://hg.python.org/cpython/rev/21b70c835b5b

    @mdickinson
    Copy link
    Member

    Thanks for the patch and the thorough analysis!

    @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.7 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    1 participant