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

Alternative algorithm for deque_remove() #69433

rhettinger opened this issue Sep 27, 2015 · 6 comments

Alternative algorithm for deque_remove() #69433

rhettinger opened this issue Sep 27, 2015 · 6 comments
3.8 only security fixes


Copy link

BPO 25246
Nosy @rhettinger, @taleinat, @serhiy-storchaka
  • bpo-25246: Improve the performance of deque_remove() #7671
  • bpo-25246: Improve the performance of deque_remove() #9851
  • bpo-25246: Optimize deque.remove() #23898
  • Files
  • deque_better_remove.diff: Alternate remove()
  • 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 = ''
    closed_at = <Date 2020-12-22.19:02:56.223>
    created_at = <Date 2015-09-27.08:43:41.086>
    labels = ['3.8']
    title = 'Alternative algorithm for deque_remove()'
    updated_at = <Date 2020-12-23.19:45:44.160>
    user = '' fields:

    activity = <Date 2020-12-23.19:45:44.160>
    actor = 'rhettinger'
    assignee = 'rhettinger'
    closed = True
    closed_date = <Date 2020-12-22.19:02:56.223>
    closer = 'rhettinger'
    components = []
    creation = <Date 2015-09-27.08:43:41.086>
    creator = 'rhettinger'
    dependencies = []
    files = ['40594']
    hgrepos = []
    issue_num = 25246
    keywords = ['patch']
    message_count = 6.0
    messages = ['251691', '261280', '319399', '383600', '383656', '383657']
    nosy_count = 3.0
    nosy_names = ['rhettinger', 'taleinat', 'serhiy.storchaka']
    pr_nums = ['7671', '9851', '23898']
    priority = 'low'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = None
    url = ''
    versions = ['Python 3.8']

    Copy link
    Contributor Author

    The current algorithm for remove() rotates the deque one-by-one until a match is found, pops it off the deque and does single mass rotate to undo the 1-step rotates.

    An alternative approach is to use deque_index() to locate the value of interest and use deque_del_item() to remove it.

    If not value is found, the alternative is better because it never moves the data in the deque. If the value is found, the alternative removes it using two mass rotations. The advantage in that case is the mass rotates are faster than many 1-step rotates. The disadvantage is that we go through the pointer chain twice (the first time visiting and comparing every element and the second time only following the chain of links).

    If the deque mutates during the search, a RuntimeError is raised. This is a behavior change, formerly it raised an IndexError.

    @rhettinger rhettinger self-assigned this Sep 27, 2015
    Copy link

    There is more optimal approach.

    Find not just an index in a deque, but a block and an index in a block. After that move left or right part of a deque one position right or left. __delitem__() could be 2 times faster, remove() could be faster too. Helpers proposed in bpo-17394 allow to do this easily.

    @rhettinger rhettinger added the 3.8 only security fixes label Jan 29, 2018
    Copy link

    IMO both approaches sound better than the existing implementation. Better to choose one than to do nothing.

    Copy link
    Contributor Author

    Am closing this one because it isn't worth an API change. The remove() method is little used and to the extent people do use it, they expect it to work like list.remove(). The latter never raises a RuntimeError.

    Copy link
    Contributor Author

    Created a new PR that gives a substantial speed-up while keeping the API unchanged and while closely matching the logic for list.remove().

    Copy link
    Contributor Author

    New changeset 6b1ac80 by Raymond Hettinger in branch 'master':
    bpo-25246: Optimize deque.remove() (GH-23898)

    @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
    3.8 only security fixes
    None yet

    No branches or pull requests

    3 participants