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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
Removed message: http://bugs.python.org/msg181206

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
assignee:  -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 and how they perform.  It also contributes to the 
invariants being understandable.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Serhiy Storchaka]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Simon Law]

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 least, an 
assertion should be there to protect future refactorings.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 unnecessary cache line misses and was blowing useful data out 
of cache.

IMO, a performance bug is different from a micro-optimization, especially if it 
is affecting the intended uses for part of an API.

Serhiy, you're welcome to backport to 3.3 if you desire.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Why only 2.7 and 3.4?

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Jesús Cea Avión]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
keywords: +patch
Added file: http://bugs.python.org/file28703/rotate.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[John O'Connor]

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 chains (by just swapping some pointers).


[1]. 
http://hg.python.org/cpython/file/a4292889e942/Modules/_collectionsmodule.c#l429

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
Removed message: http://bugs.python.org/msg179666

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 rotate 
without visiting all the underlying objects (each of which would likely be a 
cache-line miss).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[John O'Connor]

Changes by John O'Connor :


--
nosy: +jcon

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Jesús Cea Avión]

Changes by Jesús Cea Avión :


--
nosy: +jcea

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
nosy: +rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Serhiy Storchaka]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Simon Law]

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 recommends using rotate() to do 
slicing-style operations, this could get seriously slow.

deque.rotate() could just touch up the internal pointers and use memmove() to 
realign the data.

Benchmarks, of course, would have to be written to make sure this is a win.

--
components: Library (Lib)
messages: 174679
nosy: sfllaw
priority: normal
severity: normal
status: open
title: deque.rotate() could be much faster
type: performance
versions: Python 2.7, Python 3.2, Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com