[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset 12ef5a4bba63 by Raymond Hettinger in branch 'default': Issue 16398: One more assertion for good measure. http://hg.python.org/cpython/rev/12ef5a4bba63 -- ___ Python tracker

[issue16398] deque.rotate() could be much faster

Changes by Raymond Hettinger : -- Removed message: http://bugs.python.org/msg181206 ___ Python tracker ___ ___ Python-bugs-list mailin

[issue16398] deque.rotate() could be much faster

Changes by Raymond Hettinger : -- assignee: -> rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: Serhiy, it is intentional that a new block is created. Also, note the deque implementation uses freelisting (block reuse) so getting a "new block" is very cheap. Please leave this design unchanged -- it makes it very easy to reason about the deques work

[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset efb8d80af320 by Raymond Hettinger in branch 'default': Issue 16398: Add assertions to show why memcmp is safe. http://hg.python.org/cpython/rev/efb8d80af320 -- ___ Python tracker

[issue16398] deque.rotate() could be much faster

Serhiy Storchaka added the comment: It is possible to use only one new block (or even none). It should a little speed up rotate(). I will open a new issue when prepare a patch. -- ___ Python tracker __

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: Also note, len>=1 and |n| < len//2, so even within a single block, memcpy() doesn't overwrite data. -- ___ Python tracker ___ __

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: Even when leftblock == rightblock, a memcpy() will work fine. When the block extends off the end, it *always* creates a newblock and never wraps around to the current block. Data doesn't get overwritten in any scenario. -- ___

[issue16398] deque.rotate() could be much faster

Simon Law added the comment: Raymond, looking at your patch, can we assert that deque->leftblock is never equal to deque->rightblock? If not, you need to use memmove() instead of memcpy(), which is unsafe for overlapping arrays. It is not clear to me that this invariant is true. At the very le

[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset cb5cde9e5ac5 by Raymond Hettinger in branch '2.7': Issue 16398: Use memcpy() in deque.rotate(). http://hg.python.org/cpython/rev/cb5cde9e5ac5 -- ___ Python tracker ___

[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset f7b01daffe01 by Raymond Hettinger in branch 'default': Issue 16398: Use memcpy() in deque.rotate(). http://hg.python.org/cpython/rev/f7b01daffe01 -- ___ Python tracker

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: Jesús, I backported this to 2.7 because it was affecting intended usability of multiple parts of the API. The current code had the egregious and unintended side-effect of touching every data element during a rotate -- this resulted in a huge number of unne

[issue16398] deque.rotate() could be much faster

Serhiy Storchaka added the comment: Why only 2.7 and 3.4? -- nosy: +serhiy.storchaka ___ Python tracker ___ ___ Python-bugs-list maili

[issue16398] deque.rotate() could be much faster

Jesús Cea Avión added the comment: I am OK with this patch being applied to 2.7, but I wonder why. This is not a bugfix... :-) -- ___ Python tracker ___

[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset 0d81333bde78 by Raymond Hettinger in branch '2.7': Issue #16398: Optimize deque.rotate() http://hg.python.org/cpython/rev/0d81333bde78 -- ___ Python tracker __

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: John, that wouldn't work because the blocks are fixed length and the endmost blocks are typically only partially filled, so all the data elements have to shift positions within their blocks. -- resolution: -> fixed status: open -> closed _

[issue16398] deque.rotate() could be much faster

Roundup Robot added the comment: New changeset 9fb793b60e79 by Raymond Hettinger in branch 'default': Issue #16398: Optimize deque.rotate() http://hg.python.org/cpython/rev/9fb793b60e79 -- nosy: +python-dev ___ Python tracker

[issue16398] deque.rotate() could be much faster

Changes by Raymond Hettinger : -- keywords: +patch Added file: http://bugs.python.org/file28703/rotate.diff ___ Python tracker ___ ___

[issue16398] deque.rotate() could be much faster

John O'Connor added the comment: Looking at the implementation (rather quickly)[1]. I'm wondering if there is a reason why the appendleft(pop()) loop is required. It would seem the best way would be to determine the new head link, make the previous link the new end link and concatenate the two

[issue16398] deque.rotate() could be much faster

Changes by Raymond Hettinger : -- Removed message: http://bugs.python.org/msg179666 ___ Python tracker ___ ___ Python-bugs-list mailin

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: The easiest change would essentially involve inlining the code for append/appendleft and then removing unneeded steps (the state update, the INCREF/DECREF of item, and the TRIM() test). Of these, the INCREF/DECREF is likely to be a nice win because we can

[issue16398] deque.rotate() could be much faster

Raymond Hettinger added the comment: It could be made a bit faster, but it would complicate the code for very little benefit. IMO, this isn't worth it. -- priority: normal -> low ___ Python tracker __

[issue16398] deque.rotate() could be much faster

Changes by John O'Connor : -- nosy: +jcon ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.or

[issue16398] deque.rotate() could be much faster

Changes by Jesús Cea Avión : -- nosy: +jcea ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue16398] deque.rotate() could be much faster

Changes by Serhiy Storchaka : -- nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.

[issue16398] deque.rotate() could be much faster

Changes by Serhiy Storchaka : -- components: +Extension Modules -Library (Lib) stage: -> needs patch versions: +Python 3.4 -Python 2.7, Python 3.2, Python 3.3 ___ Python tracker ___

[issue16398] deque.rotate() could be much faster

New submission from Simon Law: If you look at the implementation of deque.rotate(), it does the equivalent of deque.append(deque.popleft()) or deque.appendleft(deque.pop()). Unfortunately, for larger rotations, the pop() and append() calls just do too much work. Since the documentation recomme