classification
Title: Alternative algorithm for deque_remove()
Type: Stage: resolved
Components: Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: rhettinger, serhiy.storchaka, taleinat
Priority: low Keywords: patch

Created on 2015-09-27 08:43 by rhettinger, last changed 2020-12-23 19:45 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
deque_better_remove.diff rhettinger, 2015-09-27 08:43 Alternate remove() review
Pull Requests
URL Status Linked Edit
PR 7671 closed pablogsal, 2018-06-12 23:22
PR 9851 closed pablogsal, 2018-10-13 18:56
PR 23898 merged rhettinger, 2020-12-22 21:23
Messages (6)
msg251691 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-27 08:43
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.
msg261280 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-03-07 06:39
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 issue17394 allow to do this easily.
msg319399 - (view) Author: Tal Einat (taleinat) * (Python committer) Date: 2018-06-12 20:09
IMO both approaches sound better than the existing implementation.  Better to choose one than to do nothing.
msg383600 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-12-22 19:02
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.
msg383656 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-12-23 19:44
Created a new PR that gives a substantial speed-up while keeping the API unchanged and while closely matching the logic for list.remove().
msg383657 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-12-23 19:45
New changeset 6b1ac809b9718a369aea67b99077cdd682be2238 by Raymond Hettinger in branch 'master':
bpo-25246: Optimize deque.remove() (GH-23898)
https://github.com/python/cpython/commit/6b1ac809b9718a369aea67b99077cdd682be2238
History
Date User Action Args
2020-12-23 19:45:44rhettingersetresolution: rejected -> fixed
2020-12-23 19:45:18rhettingersetmessages: + msg383657
2020-12-23 19:44:46rhettingersetmessages: + msg383656
2020-12-22 21:23:25rhettingersetpull_requests: + pull_request22753
2020-12-22 19:02:56rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg383600

stage: patch review -> resolved
2018-10-13 18:56:36pablogsalsetpull_requests: + pull_request9221
2018-06-12 23:22:33pablogsalsetpull_requests: + pull_request7285
2018-06-12 20:09:10taleinatsetnosy: + taleinat
messages: + msg319399
2018-01-29 20:54:39rhettingersetpriority: normal -> low
versions: + Python 3.8, - Python 3.6
2016-03-07 06:39:16serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg261280
2015-09-27 08:43:41rhettingercreate