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

ShareableList read and write access is O(N), should be O(1) #83072

Closed
JakeNorthey mannequin opened this issue Nov 22, 2019 · 4 comments
Closed

ShareableList read and write access is O(N), should be O(1) #83072

JakeNorthey mannequin opened this issue Nov 22, 2019 · 4 comments
Labels
3.9 only security fixes performance Performance or resource usage stdlib Python modules in the Lib dir

Comments

@JakeNorthey
Copy link
Mannequin

JakeNorthey mannequin commented Nov 22, 2019

BPO 38891
Nosy @pitrou, @applio, @corona10, @tkren, @dirkroorda
PRs
  • bpo-38891: avoid quadratic item access performance of ShareableList #18996
    		•
    Files
  • report.py: Test of computing max of a shareable list of several sizes, timings for python 3.8.3 and 3.9.0b3
    		•

    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 2020-04-19.15:19:42.186>
created_at = <Date 2019-11-22.02:31:14.877>
labels = ['library', '3.9', 'performance']
title = 'ShareableList read and write access is O(N), should be O(1)'
updated_at = <Date 2020-06-30.08:43:24.104>
user = 'https://bugs.python.org/JakeNorthey'

    bugs.python.org fields:

    activity = <Date 2020-06-30.08:43:24.104>
actor = 'dirkroorda'
assignee = 'none'
closed = True
closed_date = <Date 2020-04-19.15:19:42.186>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2019-11-22.02:31:14.877>
creator = 'Jake Northey'
dependencies = []
files = ['49279']
hgrepos = []
issue_num = 38891
keywords = ['patch']
message_count = 4.0
messages = ['357239', '357262', '366784', '372665']
nosy_count = 6.0
nosy_names = ['pitrou', 'davin', 'corona10', 'tkren', 'Jake Northey', 'dirkroorda']
pr_nums = ['18996']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue38891'
versions = ['Python 3.9']
    @JakeNorthey
    Copy link
    Mannequin Author

    JakeNorthey mannequin commented Nov 22, 2019

    For an illustration of the performance implications of the __getitem__ and __setitem__ implementation, see the article below.
    https://medium.com/@rvprasad/performance-of-system-v-style-shared-memory-support-in-python-3-8-d7a7d1b1fb96

    The issue appears to be due to the summing of ShareableList item sizes to generate an offset for the requested item. Perhaps an offset-based index could be created in which the allocation sizes could be constructed by comparing two offets.

    @JakeNorthey JakeNorthey mannequin added 3.8 only security fixes stdlib Python modules in the Lib dir performance Performance or resource usage labels Nov 22, 2019
    @corona10
    Copy link
    Member

    IMHO,

    1. replace self._allocated_bytes to self._sum_allocated_bytes
    2. initialize self._sum_allocated_bytes at the __init__ time.
    3. if self._allocated_bytes is needed, calculate from _sum_allocated_bytes it will take O(1)

    If the suggestion is accepted, I'd like to work on this issue.

    @pitrou pitrou added 3.9 only security fixes and removed 3.8 only security fixes labels Apr 18, 2020
    @pitrou
    Copy link
    Member

    pitrou commented Apr 19, 2020

    New changeset c8f1715 by Thomas Krennwallner in branch 'master':
    bpo-38891: avoid quadratic item access performance of ShareableList (GH-18996)
    c8f1715

    @pitrou pitrou closed this as completed Apr 19, 2020
    @dirkroorda
    Copy link
    Mannequin

    dirkroorda mannequin commented Jun 30, 2020

    I can see that the performance of ShareableList is much better now.
    Still the performance of list operations on a ShareableList may be degraded by a factor 200-300 with respect to a normal list.

    If this is unavoidable then the docs should clearly mention this degradation, because this will, in many use cases, cancel the performance gain that shared memory offers!

    @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
    No one assigned
    Labels
    3.9 only security fixes performance Performance or resource usage stdlib Python modules in the Lib dir
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    2 participants
    @pitrou @corona10