[SciPy-user] How to "move" data within an array

[Anne Archibald]

On 04/07/07, Andrew Smart <subscriptions at smart-knowhow.de> wrote:

> I found roll() in the meantime also as one option. It's a feasible approach,
> but still may cause memory fragmentation. I'll take roll() for the time
> being - and some time later I'll see if someone makes me a C based function
> which does the same without copying the array...

I don't think memory fragmentation should be a concern. For one thing,
as you've described the problem, the array size isn't changing, so it
will almost certainly be copied back and forth between two memory
blocks. For another, for an array big enough for you to care about,
malloc() will request a new hunk of memory from the OS, and then free
it back to the OS when you're done with it. (Well, on Linux anyway.)

If you do want to move the array in place, you could try
A[:-1]=A[1:]
I don't know if that is smart enough to use memmove() if the copy is
of a contiguous block, but at the least it will be done in place by C
code. (The implementation of that optimization is complicated by the
semantics of that operation - since source and destination overlap,
the order of the indexing matters.)

A true in-place roll() is tricky and might have very poor cache
behaviour (because roll() tries to preserve all the array elements, so
rolling a 7-element array only has to loop around once, skipping by 3,
while rolling a 9-element array has to loop around nine times,
skipping by three).

Memory allocation is cheap and efficient, so eliminating temporaries
is less helpful than it might seem. In particular, it's worth knowing
that numpy array memory is a leaf with respect to the python garbage
collector - it doesn't need to be traversed, it just disappears when
the array objects pointing to it go. Also, as I said above, at least
on Linux, big monolithic allocations like numpy's go on fresh pages
from the OS, and are given back to it when done.

Is this actually the slowdown in your application?

Anne