What is the use of preallocating memory for an array in perl?

Question

Perl allows preallocated arrays. We can preallocate the array before use, then we can add more elements. For example, allocating 50 array members then adding a 51st member, because arrays are expandable. So does preallocating an array improve performance?

Answer 1

Its because of how memory is allocated in computers. Computer memory is like space on a whiteboard: it has a position in relation to other memory; and it cannot be moved, it must be copied.

If you create a small array it might look like this:

@array = (1, 4, 8, 12, 19);

allocate memory for @array
______________________|               |______| a b c|__________

copy in the data
______________________|  1  4  8 12 19|______| a b c|__________

_ is unallocated memory. | indicates the bounds of what is allocated to your array. | a b c| is some other array.

Then if you push onto that array a few times, Perl will have to reallocate memory. In this case it can grow the memory it already has into the unallocated space.

push @array, 23, 42;

grow the existing memory
______________________|  1  4  8 12 19      | a b c|__________

add the new data
______________________|  1  4  8 12 19 23 42| a b c|__________

Now what happens if you push more numbers onto @array? It can't grow your memory anymore, there's another array in the way. So, just like on a whiteboard, it has to copy the entire array to a clear chunk of memory.

push @array, 85, 99;

Allocate a new chunk of memory
|                           |  1  4  8 12 19 23 42| a b c|__________

Copy the existing data
|  1  4  8 12 19 23 42      |  1  4  8 12 19 23 42| a b c|__________

Deallocate the old memory
|  1  4  8 12 19 23 42      |__1__4__8_12_19_23_42| a b c|__________

Add the new data
|  1  4  8 12 19 23 42 85 99|__1__4__8_12_19_23_42| a b c|__________

To save time, Perl will not bother to erase the old data. It will just deallocate it and something else can scribble over it when they need to.

This makes push more expensive, especially with very large arrays which need to copy more data. As your array gets larger it's more and more likely that Perl will have to allocate a fresh hunk of memory and copy everything.

There's another problem: memory fragmentation. If you're allocating and reallocating over and over again, the hunks of memory can get chopped up so it's difficult to find big blocks of free memory. This is less of a problem on modern operating systems, but still a concern. It can make it seem like you have less memory than you really have, and it can cause the Operating System to use the disk as memory (virtual memory) more than it should. Disks are slower than memory.

---

I simplified a lot of things. I made it look like Perl has to reallocate every time you push. This isn't true. Perl allocates more memory to arrays than it needs for just this reason. So you can safely add a few extra entries to an array without Perl having to reallocate. The same goes for strings and hashes.

The other thing is this is probably a somewhat outdated view of how memory allocation works on modern operating systems... although Perl will sometimes do its own memory allocation if it doesn't trust the OS. Check use Config; print $Config{usemymalloc}. n indicates Perl is using the operating system's memory allocation, y indicates it's using Perl's.

The rule of thumb is: don't preallocate, it's probably a waste of your time and the computer's memory. However, if all of the conditions below are true, see if preallocating helps.

• You profiled and found a problem.
• You're building a data structure incrementally by adding to it.
• You know for certain its minimum eventual size.
• That size is "large".

What is "large" is up for debate and depends on your version of Perl, your operating system, your hardware, and your performance tolerance.