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

Optimize iterating split table values #72766

Closed
zhangyangyu opened this issue Nov 1, 2016 · 26 comments
Closed

Optimize iterating split table values #72766

zhangyangyu opened this issue Nov 1, 2016 · 26 comments
Labels
3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement

Comments

@zhangyangyu
Copy link
Member

BPO 28580
Nosy @vstinner, @methane, @serhiy-storchaka, @zhangyangyu
PRs
  • [Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
  • Files
  • _PyDict_Next.patch
  • iterate_splittable.patch
  • iterate_splittable_v2.patch
  • iterate_splittable_v3.patch: eliminate undefined behaviour
  • iterate_splittable_v4.patch
  • 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 = None
    closed_at = <Date 2016-11-04.08:00:15.957>
    created_at = <Date 2016-11-01.17:25:08.645>
    labels = ['interpreter-core', 'type-feature', '3.7']
    title = 'Optimize iterating split table values'
    updated_at = <Date 2017-03-31.16:36:28.163>
    user = 'https://github.com/zhangyangyu'

    bugs.python.org fields:

    activity = <Date 2017-03-31.16:36:28.163>
    actor = 'dstufft'
    assignee = 'none'
    closed = True
    closed_date = <Date 2016-11-04.08:00:15.957>
    closer = 'methane'
    components = ['Interpreter Core']
    creation = <Date 2016-11-01.17:25:08.645>
    creator = 'xiang.zhang'
    dependencies = []
    files = ['45305', '45312', '45315', '45330', '45332']
    hgrepos = []
    issue_num = 28580
    keywords = ['patch']
    message_count = 26.0
    messages = ['279884', '279908', '279909', '279910', '279912', '279916', '279919', '279928', '279930', '279931', '279933', '279934', '279935', '279936', '279938', '279958', '279966', '279968', '279970', '279971', '279973', '279975', '279977', '280039', '280040', '280041']
    nosy_count = 5.0
    nosy_names = ['vstinner', 'methane', 'python-dev', 'serhiy.storchaka', 'xiang.zhang']
    pr_nums = ['552']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'enhancement'
    url = 'https://bugs.python.org/issue28580'
    versions = ['Python 3.7']

    @zhangyangyu
    Copy link
    Member Author

    Since values of split table is always dense, we can optimise the current implementation of _PyDict_Next. I think this could hardly bring much performance enhancement. More importantly, this emphasizes the invariant and make bugs easy to find and test.

    @zhangyangyu zhangyangyu added type-bug An unexpected behavior, bug, or error 3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) labels Nov 1, 2016
    @zhangyangyu zhangyangyu changed the title Optimise _PyDict_Next for split table Optimize _PyDict_Next for split table Nov 1, 2016
    @serhiy-storchaka
    Copy link
    Member

    I agree that this unlikely could cause visible effect, but this patch simplifies the code. LGTM.

    Similar changes can be applied to other iteration code. dictiter_iternextkey, dict_keys, etc.

    @serhiy-storchaka
    Copy link
    Member

    I think this is too late for 3.6.

    @serhiy-storchaka serhiy-storchaka added type-feature A feature request or enhancement and removed type-bug An unexpected behavior, bug, or error labels Nov 2, 2016
    @methane
    Copy link
    Member

    methane commented Nov 2, 2016

    LGTM, too.

    Similar changes can be applied to other iteration code. dictiter_iternextkey, dict_keys, etc.

    I agree. Xiang, would you update patch?

    @zhangyangyu
    Copy link
    Member Author

    Xiang, would you update patch?

    Working on it.

    @zhangyangyu zhangyangyu changed the title Optimize _PyDict_Next for split table Optimize iterating split table values Nov 2, 2016
    @zhangyangyu
    Copy link
    Member Author

    Here is the new patch to apply the optimization to more places.

    @serhiy-storchaka
    Copy link
    Member

    LGTM.

    @zhangyangyu
    Copy link
    Member Author

    Update the patch to use more obvious comparison way. This uses INADA's suggestion and make the code more like other places.

    I think the performance issue is better to be discussed in bpo-28397. It doesn't have a significant impact on this patch. Hope we can move forward and not block on it.

    @serhiy-storchaka
    Copy link
    Member

    Could you please check how this change affects the performance?

    @zhangyangyu
    Copy link
    Member Author

    python -> unpatched, python3 -> patched

    iterkeys:

    (split)

    ./python3 -m perf timeit --compare-to /home/angwer/cpython/python -s 'from argparse import Namespace; ns = Namespace(); [setattr(ns, str(i), str(i)) for i in range(10000)]' 'list(iter(ns.__dict__))'
    python: ..................... 112 us +- 1 us
    python3: ..................... 109 us +- 1 us

    Median +- std dev: [python] 112 us +- 1 us -> [python3] 109 us +- 1 us: 1.03x faster

    (combined)

    ./python3 -m perf timeit --compare-to /home/angwer/cpython/python -s 'd = {x:x for x in range(10000)}' 'list(iter(d))'python: ..................... 84.3 us +- 2.4 us
    python3: ..................... 86.0 us +- 3.5 us

    Median +- std dev: [python] 84.3 us +- 2.4 us -> [python3] 86.0 us +- 3.5 us: 1.02x slower

    pydict_next:

    (split)

    ./python3 -m perf timeit --compare-to /home/angwer/cpython/python -s 'from argparse import Namespace; ns = Namespace(); [setattr(ns, str(i), str(i)) for i in range(10000)]' 'repr(ns.__dict__)'
    python: ..................... 1.85 ms +- 0.01 ms
    python3: ..................... 1.85 ms +- 0.11 ms

    Median +- std dev: [python] 1.85 ms +- 0.01 ms -> [python3] 1.85 ms +- 0.11 ms: 1.00x faster

    (combined)

    ./python3 -m perf timeit --compare-to /home/angwer/cpython/python -s 'd = {x:x for x in range(10000)}' 'repr(d)'
    python: ..................... 1.99 ms +- 0.01 ms
    python3: ..................... 1.87 ms +- 0.01 ms

    Median +- std dev: [python] 1.99 ms +- 0.01 ms -> [python3] 1.87 ms +- 0.01 ms: 1.06x faster

    @serhiy-storchaka
    Copy link
    Member

    There is not easy to benchmark PyDict_Next. dict.__repr__ does much hard work (calling repr() for keys and values, formatting strings). Using _testcapi.test_dict_iteration perhaps is the easiest way to measure the performance of pure PyDict_Next, but it includes creating and deallocating of dicts.

    @zhangyangyu
    Copy link
    Member Author

    Yes, that's the point. I thought to expose an API in testcapimodule for test, but actually I am not willing to do that since I don't believe this patch could bring any visible performance change.

    @methane
    Copy link
    Member

    methane commented Nov 2, 2016

    Xiang Zhang added the comment:

    Yes, that's the point. I thought to expose an API in testcapimodule for test, but actually I am not willing to do that since I don't believe this patch could bring any visible performance change.

    I agree with you.
    I feel this patch is cleanup rather than optimization.

    • Removing redundant loop which always break at first
    • Adding very useful assertion to find potential bugs

    @methane
    Copy link
    Member

    methane commented Nov 2, 2016

    LGTM again for iterate_splittable_v2.patch.

    How about issue title (and commit message) to
    "Cleanup iterating split table"?

    @serhiy-storchaka
    Copy link
    Member

    I believe the patch doesn't makes iterating split table slower and likely makes it a little faster. The patch adds one additional check, but it removes other checks. Thus this still is an optimization.

    But the last patch has an undefined behavior.

    @methane
    Copy link
    Member

    methane commented Nov 3, 2016

    (Off topic note)

    For readability, I prefer this style:

      PyDictKeyEntry *entries = DK_ENTRIES(mp->ma_keys);
      while (i < n && entries[i].me_value == NULL)
          i++;

    But because sizeof(PyDictKeyEntry) is not 2^n, entries[i].me_value, i++
    may be slower than entry_ptr->me_value, i++, entry_ptr++.

    So we should prefer i++, entry_ptr++ style in case of iterating dict entries.

    @serhiy-storchaka
    Copy link
    Member

    Following example causes a crash in debug build:

    d = dict.fromkeys(range(100))
    for k in range(99):
        del d[k]
    
    it = iter(d)
    assert next(it) == 99
    d.clear()
    d[0] = None
    next(it)

    @zhangyangyu
    Copy link
    Member Author

    Hmm, the resolution could be simple. But how about

    >>> d = dict.fromkeys(range(100))
    >>> for k in range(98):
    ...     del d[k]
    ... 
    >>> it = iter(d)
    >>> next(it)
    98
    >>> d.clear()
    >>> d[0] = 1
    >>> d[1] = 2
    >>> next(it)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    StopIteration

    Actually we haven't exhaust the dict yet. Is it reasonable for me to expect the second next returning 0? I actually mean is it reasonable for me to expect len(dict) elements returned before StopIteration raised even if the dict is changed?

    @serhiy-storchaka
    Copy link
    Member

    It is appropriate if iterating modifying dict raises RuntimeError, produces less items or even produce some items multiple times. What is not appropriate -- crash, hang and infinite iteration. There was a proposition about making this behavior more consistent (bpo-19332), but it was rejected.

    I would suggest just remove assert() from your patch and address undefined behavior in other issue.

    @zhangyangyu
    Copy link
    Member Author

    Currently dict iterator does not allow size changed during iteration. This is more strict than list iterator but still allow modification during iteration. Maybe we could deny all modification by checking dict->ma_version_tag. But that's irrelevant to this issue.

    Serhiy, this means the iternext* functions all get UB. These codes existed even in 3.3. Do we really need to eliminate them now?

    @zhangyangyu
    Copy link
    Member Author

    I would suggest just remove assert() from your patch and address undefined behavior in other issue.

    That's what v2 does. If there is another issue, let's also leave _PyDict_Next to it.

    @serhiy-storchaka
    Copy link
    Member

    In current code there is no UB in _PyDict_Next().

    @serhiy-storchaka
    Copy link
    Member

    v4 LGTM.

    @methane
    Copy link
    Member

    methane commented Nov 4, 2016

    LGTM. I'll commit.

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Nov 4, 2016

    New changeset 3904194d06e6 by INADA Naoki in branch 'default':
    Issue bpo-28580: Optimize iterating split table values.
    https://hg.python.org/cpython/rev/3904194d06e6

    @methane methane closed this as completed Nov 4, 2016
    @zhangyangyu
    Copy link
    Member Author

    Thanks!

    @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) type-feature A feature request or enhancement
    Projects
    None yet
    Development

    No branches or pull requests

    3 participants