Memory efficiency with arrays

[Hot Pastrami]

Good day, everyone.

It is commonly known that it is mildly inefficient to tack items onto an array one by one, particularly with large amounts of data. This is less true if the array is pre-extended, however. If I understand correctly, this is because the array has to find a hunk of RAM big enough to hold the array with the new data, and move itself to the new spot in its entirety, which can be slow.

What I am wondering is this... does the same work backwards? If you pop or shift items off a large array one at a time, does it simply deallocate the memory those elements used, or does it still have to move the whole dad-gum array with each removal?

The reason I ask is because I am using an array which holds quite a remarkable amount of data, and I need to rifle through it only once. It occurred to me that it may be a good idea to shift() each element off the array as I go, therefore freeing up the memory a bit sooner, but if the array must be relocated in memory with each shift(), that would aggravate the problem rather than soothe it.

An alternative is that I could just find something better to do with my time than belly-aching about the finer points of array memory allocation in Perl... but that would be downright loony.

Thanks,

Hot Pastrami

[tye]

Note that growing the array doesn't have to move all of the contents of the array, just the memory for the array itself (mostly the references to the elements of the array).

Shrinking an array will never move its memory block. I doubt it will free any memory either, though undefing it will allow that memory to be reused.

In theory, pop()ing would be more efficient than shift()ing since every so often the array will be moved down so that the gap in front of its memory space is not huge. But in practice this is done infrequently enough that it usually doesn't matter. However, if you have a huge array, I'd probably play it safe and use push() and pop() and pre-extend the space for the array if possible.

See also Shift, Pop, Unshift and Push with Impunity!.

This node has been updated.

        - tye (but my friends call me "Tye")

[tilly]

You are correct that a pre-extended array is marginally more efficient to push stuff onto than one started from scratch. But the difference is generally small in comparison with the effort it takes to create the stuff in the array.

With current versions of Perl, growing an array with push is fast. Walking through it with shift and pop is fast. (I would suspect that pop is marginally faster because it does less accounting.) With current versions of Perl it is slow to unshift. But this will change.

In short, unless you are encountering problems, don't worry about it.

(That notwithstanding, if you have to only go through it once think about whether there is any way to redesign your program to operate incrementally so you never have to have it all in memory at once.)

[Dominus]

Says tilly:

With current versions of Perl it is slow to unshift.

It's probably also worth pointing out that unshift is fast if the array has previously been shifted. The shift leaves a gap at the beginning of the memory block, and when you unshift, Perl sticks the new data into the gap.

[Dominus]

Says tye, apparently reporting from an alternate dimension:

In theory, pop()ing would be more efficient than shift()ing since every so often the array will be moved down so that the gap in front of its memory space is not huge.

Since Perl never does move the array down when you do shift, I don't see the purpose of this theory. You could exchange pop and shift in your theory and it would make as much sense and be as true.

[tye]

I guess that goes along with Perl's general theory of always choose faster over less memory. (: I think Perl will move the array down in some situations, but I'll take your word for it that it doesn't do it in this specific situation (I'm now guessing that Perl will wait until you try to push() passed the end of the memory space -- but that is a guess).

tilly notes that the shift() might have more accounting to do and so might be slightly slower.

By the way, does the same apply to shifting of strings? I recall my playing with this showing that Perl would shift the string, but perhaps again that was only when I appended past the end of the string's memory buffer (in fact, that sounds familiar now that I think back). (Bonus points for anyone who can detect this in straight Perl -- I cheated in an interesting and dangerous way.)

        - tye (but my friends call me "Tye")