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 assignments to ob_size of new ints that _PyLong_New returned #71628

Closed
orenmn mannequin opened this issue Jul 2, 2016 · 6 comments
Closed

redundant assignments to ob_size of new ints that _PyLong_New returned #71628

orenmn mannequin opened this issue Jul 2, 2016 · 6 comments
Assignees
Labels
3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@orenmn
Copy link
Mannequin

orenmn mannequin commented Jul 2, 2016

BPO 27441
Nosy @mdickinson, @vstinner, @serhiy-storchaka, @orenmn
PRs
  • [Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
  • Files
  • CPythonTestOutput.txt: test output of CPython without my patches (tested on my PC)
  • issue27441_ver1.diff: proposed patches diff file - ver1
  • patchedCPythonTestOutput_ver1.txt: test output of CPython with my patches (tested on my PC) - ver1
  • issue27441_ver2.diff: proposed patches diff file - ver2
  • patchedCPythonTestOutput_ver2.txt: test output of CPython with my patches (tested on my PC) - ver2
  • 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.18:50:08.692>
    created_at = <Date 2016-07-02.14:38:57.740>
    labels = ['interpreter-core', '3.7', 'performance']
    title = 'redundant assignments to ob_size of new ints that _PyLong_New returned'
    updated_at = <Date 2017-03-31.16:36:28.938>
    user = 'https://github.com/orenmn'

    bugs.python.org fields:

    activity = <Date 2017-03-31.16:36:28.938>
    actor = 'dstufft'
    assignee = 'mark.dickinson'
    closed = True
    closed_date = <Date 2016-09-17.18:50:08.692>
    closer = 'mark.dickinson'
    components = ['Interpreter Core']
    creation = <Date 2016-07-02.14:38:57.740>
    creator = 'Oren Milman'
    dependencies = []
    files = ['43607', '43608', '43609', '43661', '43662']
    hgrepos = []
    issue_num = 27441
    keywords = ['patch']
    message_count = 6.0
    messages = ['269715', '269871', '269987', '276813', '276814', '276815']
    nosy_count = 5.0
    nosy_names = ['mark.dickinson', 'vstinner', '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/issue27441'
    versions = ['Python 3.7']

    @orenmn
    Copy link
    Mannequin Author

    orenmn mannequin commented Jul 2, 2016

    ------------ current state ------------
    In six different functions, the following happens:
    1. Function x calls _PyLong_New, with var y as the size argument.
    * Among others, _PyLong_New sets the ob_size of the new int to y (the size argument it received).
    2. Function x sets the ob_size of the new int to y, even though y is already the value of ob_size.

    The functions in which this happens are:
    1. in Objects/longobject.c:
    - PyLong_FromUnsignedLong
    - PyLong_FromLongLong
    - PyLong_FromUnsignedLongLong
    - PyLong_FromSsize_t
    - PyLong_FromSize_t
    2. in Python/marshal.c:
    - r_PyLong

    With regard to relevant changes made in the past, it seems that the redundant assignment was added (in each of these six functions) on the last major rewriting of the function, or when the function was first added, and remained there to this day.

    The revisions in which the redundant assignments were added:
    1. changeset 18114 (https://hg.python.org/cpython/rev/31cd0db0f09f):
    - PyLong_FromUnsignedLong
    2. changeset 38307 (https://hg.python.org/cpython/rev/5a63369056a7):
    - PyLong_FromLongLong
    - PyLong_FromUnsignedLongLong
    3. changeset 46460 (https://hg.python.org/cpython/rev/b04f2052e812):
    - PyLong_FromSize_t
    - PyLong_FromSsize_t
    4. changeset 52215 (https://hg.python.org/cpython/rev/bb5de24a343f):
    - r_PyLong

    ------------ proposed changes ------------
    Remove these six redundant assignments.

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

    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 Jul 2, 2016
    @serhiy-storchaka
    Copy link
    Member

    Changes to PyLong_FromUnsignedLong() and PyLong_FromUnsignedLongLong() LGTM. I don't know whether other changes have a positive effect. Are there any microbenchmarks? There are other places in which Py_SIZE() is set to the same value.

    @orenmn
    Copy link
    Mannequin Author

    orenmn mannequin commented Jul 8, 2016

    I am sorry, but I can't see why micro-benchmarking is needed here, as my patches only remove code that does nothing, while they don't add any new code.

    The assembly the compiler generates (on my PC) for 'Py_SIZE(v) = negative ? -ndigits : ndigits;' in PyLong_FromLongLong is:
    ('[edx+8]' is 'Py_SIZE(v)',
    '[esp+10h+var_4]' is 'negative',
    The 'lea ecx, [edx+0Ch]' and 'mov eax, edi' instructions set ecx and eax for later (I haven't removed them in order to be as precise as possible.))
    ...
    cmp [esp+10h+var_4], 0
    lea ecx, [edx+0Ch]
    jz short loc_1E0D48EC
    neg ebx
    loc_1E0D48EC:
    mov eax, edi
    mov [edx+8], ebx
    ...
    In contrast, the assembly the compiler generates for 'if (negative) Py_SIZE(v) = -ndigits;' is:
    ...
    cmp [esp+10h+var_4], 0
    lea ecx, [edx+0Ch]
    jz short loc_1E0D482F
    neg ebx
    mov [edx+8], ebx
    loc_1E0D482F:
    mov eax, edi
    ...
    Comparing the assembly generated for the other original '?:' expressions with my corresponding patches looks quite the same. Each patch moves the assignment from code which is executed in both of the flows, to code which is executed in only one of the flows.

    Am I missing anything that might cause my patches to introduce a performance penalty?

    I searched (all of the cpython repo) for other places in which Py_SIZE() is set to the same value, and indeed found one in Objects/longobject.c in _PyLong_Init:
    The loop that initializes the small_ints array goes over every element in the array, and checks whether it was already initialized. For some reason, even when it realizes the current element was already initialized, it still sets 'Py_SIZE(v)' and 'v->ob_digit[0]' (to the values they are already set to).
    These redundant assignments were first added in changeset 45072 (https://hg.python.org/cpython/rev/f183f1189824), and remained there to this day.

    So I added a patch to move these assignments so they would be executed only in case the current element of small_ints wasn't already initialized.
    The updated patches diff file is attached. I also ran the tests again, and got quite the same output (the output is attached).

    Have you spotted any other places in which Py_SIZE() is set to the same value?

    @orenmn orenmn mannequin added the 3.7 (EOL) end of life label Sep 13, 2016
    @mdickinson
    Copy link
    Member

    Am I missing anything that might cause my patches to introduce a performance penalty?

    It's at least conceivable that code like

    Py_SIZE(v) = negative ? -ndigits : ndigits;

    might be compiled to something branchless on some platforms (with some sets of compiler flags). The assembly you show demonstrates that that doesn't happen on your machine, but that doesn't say anything about other current or future machines.

    I also prefer the original form for readability; so I agree with Serhiy that we shouldn't change it without evidence that the change improves performance.

    I'll remove the two obviously redundant Py_SIZE(v) = ... operations in PyLong_FromUnsignedLong and PyLong_FromUnsignedLongLong.

    @mdickinson mdickinson self-assigned this Sep 17, 2016
    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Sep 17, 2016

    New changeset 27a6ecf84f72 by Mark Dickinson in branch 'default':
    Issue bpo-27441: Remove some redundant assignments to ob_size in longobject.c. Thanks Oren Milman.
    https://hg.python.org/cpython/rev/27a6ecf84f72

    @mdickinson
    Copy link
    Member

    Changes to PyLong_FromUnsignedLong and PyLong_FromUnsignedLongLong applied. I've left the others; for the small int initialisation, that code isn't performance critical anyway, and I'm not entirely comfortable with assuming that PyObject_INIT_VAR will always handle negative sizes correctly. (The (ab)use of the sign bit of the ob_size field is something that's particular to the int type.)

    @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 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    2 participants