classification
Title: add rotate{left,right} methods to bytearray
Type: enhancement Stage:
Components: Interpreter Core Versions: Python 3.3
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: ethan.furman, josiahcarlson, pitrou, rhettinger, serhiy.storchaka, terry.reedy
Priority: low Keywords:

Created on 2008-08-01 17:57 by pitrou, last changed 2013-05-18 16:04 by terry.reedy. This issue is now closed.

Messages (10)
msg70579 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-08-01 17:57
While tweaking the BufferedWriter implementation it came to me that it
would be useful to have rotate_left and rotate_right methods on
bytearray,  so as to rotate the array by a number of bytes without any
wasteful memory allocations and copies.

(or, if memoryview is one day implemented it could be a memoryview
method instead...)
msg70909 - (view) Author: Josiah Carlson (josiahcarlson) * Date: 2008-08-08 20:38
Sadly, this isn't quite as easy as it would seem.  The O(1) memory
overhead version of this requires 2n reads and 2n writes, but does both
reads and writes at two memory locations at a time, which may have
nontrivial performance implications.

The simple version that copies out the small part of the shift into a
temporary buffer, doing a memcpy/memmov internally, then copying the
small data back is likely to have much better performance (worst-case
1.5n reads and 1.5n writes.

Offering this ability in the momoryview object would be very
interesting, though I'm not sure that the memoryview object is able to
offer a multi-segment buffer interface where the segments are not the
same length (this could be hacked by having a single pointer per byte,
but at that point we may as well perform a copy).
msg70910 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-08-08 20:49
Hi,

> Sadly, this isn't quite as easy as it would seem.

You are right, I was overly optimist when thinking about this.

> Offering this ability in the momoryview object would be very
> interesting, though I'm not sure that the memoryview object is able to
> offer a multi-segment buffer interface where the segments are not the
> same length (this could be hacked by having a single pointer per byte,
> but at that point we may as well perform a copy).

I'm not sure what you mean, but I think we can just restrict it to the
simple case of a single contiguous buffer.

shift{left,right} could be useful too (and faster).
msg70915 - (view) Author: Josiah Carlson (josiahcarlson) * Date: 2008-08-08 21:44
In order for MemoryView to know what bytes it is pointing to in memory,
it (generally) keeps a pointer with a length.  In order to rotate the
data without any copies, you need a pointer and length for each rotation
plus the original.  For example, the equivalent to a rotate left of 8
characters using slicing is... x[8:] + x[:8].  That is two segments. 
That's a "multi-segment buffer interface".  But typical multi-segment
buffer interfaces require each segment to be exactly the same length
(like numpy), which is not the case with rotations.
msg70916 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-08-08 22:00
Le vendredi 08 août 2008 à 21:44 +0000, Josiah Carlson a écrit :
> Josiah Carlson <josiahcarlson@users.sourceforge.net> added the comment:
> 
> In order for MemoryView to know what bytes it is pointing to in memory,
> it (generally) keeps a pointer with a length.  In order to rotate the
> data without any copies, you need a pointer and length for each rotation
> plus the original.  For example, the equivalent to a rotate left of 8
> characters using slicing is... x[8:] + x[:8].

Hmm, I think it's simpler if the rotate is done in-place rather than
returning a new object. Most uses of memoryviews are going to be with
APIs requiring a single contiguous segment.
(of course for read-only buffers it would raise an error)
msg87954 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-05-17 03:11
Am -1 on this.  Rotating byte arrays has very few use cases and the ones
it does have can typically be met by indexing.
msg113438 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2010-08-09 18:29
Antoine, do you disagree with Raymond or should we close this?
In any case, I believe this would delayed by the moratorium.
msg189494 - (view) Author: Ethan Furman (ethan.furman) * (Python committer) Date: 2013-05-18 03:46
Antoine, do you want to pursue, or can we close this?
msg189500 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-18 08:48
I think we can close. issue17100 would have been more useful actually.
msg189502 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-05-18 09:34
I think you rather need the inplace shift operation. Or even the move the tail of buffer to the start without filling the remaining. I.e. something like

    buffer[:size] = buffer[-size:]

but without creating immediate bytes object. Now it may be written as:

    buffer[:size] = memoryview(buffer)[-size:]
History
Date User Action Args
2013-05-18 16:04:53terry.reedysetstatus: open -> closed
resolution: rejected
2013-05-18 09:34:06serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg189502
2013-05-18 08:48:27pitrousetmessages: + msg189500
2013-05-18 03:46:37ethan.furmansetnosy: + ethan.furman
messages: + msg189494
2010-08-11 19:58:12rhettingersetpriority: normal -> low
stage: test needed ->
2010-08-09 18:29:00terry.reedysetnosy: + terry.reedy

messages: + msg113438
versions: + Python 3.3, - Python 2.7, Python 3.2
2009-05-17 03:11:35rhettingersetnosy: + rhettinger
messages: + msg87954
2009-05-16 20:45:37ajaksu2setstage: test needed
versions: + Python 3.2, - Python 3.1
2008-08-08 22:00:05pitrousetmessages: + msg70916
2008-08-08 21:44:03josiahcarlsonsetmessages: + msg70915
2008-08-08 20:49:31pitrousetmessages: + msg70910
2008-08-08 20:38:30josiahcarlsonsetnosy: + josiahcarlson
messages: + msg70909
2008-08-01 17:57:57pitroucreate