Either you or I are mis-reading Shift, Pop, Unshift and Push with Impunity! because as in the snippet quoted it simply mentions reallocation and not leakage. Do you have an SSCCE which actually demonstrates leakage? If not, I wouldn't worry about it.

thanks for the correct link.

> it simply mentions reallocation and not leakage

yes, but the question could be if memory is released again.

IIRC, Perl's arrays are "improved" C-Arrays to have O(1) lookup.¹

The slots of the C-array are equally sized pointers to scalars holding the various data types

Furthermore will they always allocate a power of 2 of RAM, and only double if needed.

The empty slots are available as fill-in margins at the beginning and end of the C-array, The Perl is keeping a counters to see where the actual values start and end.

Like this unshift and push are O(1) if there is margin left. Otherwise reallocating more space only happens for doubling it. I.e. complexity is negligible since it only happens in O(log) occasions.

This bargaining of time-complexity for space-complexity allows nearly as efficient appending operations like linked lists have.

Now in theory it could happen that you have an array of a handful elements and after 1 million combined push and shift operations it allocates megabytes of space while not logically growing.

I doubt this happens and otherwise should be easy to demonstrate by the OP with a loop and using Devel::Size before and after.

edit

1) see also https://blob.perl.org/tpc/1998/Perl_Language_and_Modules/Perl%20Illustrated/#AV

update

It could also be an issue if the OS doesn't "take back" released memory.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

Now in theory it could happen that you have an array of a handful elements and after 1 million combined push and shift operations it allocates megabytes of space while not logically growing. ... I doubt this happens

That's my position also. And I was bored, so here's the proof.

#!/usr/bin/env perl
#=====================================================================
+==========
#
#         FILE: fifo-mem.pl
#
#        USAGE: ./fifo-mem.pl  
#
#  DESCRIPTION: Test memory consumption of a push/shift FIFO
#               See https://www.perlmonks.org/?node_id=11157497
#
#=====================================================================
+==========

use strict;
use warnings;
use Memory::Usage;

my @fifo;

my $max = 100_000_000;

my $mu = Memory::Usage->new;

$mu->record ('start');

for my $count (1 .. $max) {
    push @fifo, 'dog';
    shift @fifo;
    $mu->record ("After $count iterations") unless $count % 10_000_000
+;
}

$mu->record ('finish');
$mu->dump;
[download]

And since not everyone can run this, here's the output:

$   time    vsz (  diff)    rss (  diff) shared (  diff)   code (  dif
+f)   data (  diff)
     0  10780 ( 10780)   6544 (  6544)   5448 (  5448)      4 (     4)
+   1356 (  1356) start
     3  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 10000000 iterations
     5  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 20000000 iterations
     8  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 30000000 iterations
    10  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 40000000 iterations
    12  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 50000000 iterations
    15  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 60000000 iterations
    17  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 70000000 iterations
    20  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 80000000 iterations
    22  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 90000000 iterations
    24  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) After 100000000 iterations
    24  10780 (     0)   6544 (     0)   5448 (     0)      4 (     0)
+   1356 (     0) finish
$
[download]

As expected, no leak whatsoever.

It could also be an issue if the OS doesn't "take back" released memory.

Of course, but so could any program doing anything. That doesn't constitute a leak.

---

🦛

use Devel::Peek;

my $n = 1_000_000;

my @q;
for ( 1 .. $n ) {
   push @q, undef;
   shift @q;
}

Dump( @q );
[download]

SV = PVAV(0x5588bbfb50c0) at 0x5588bbfe31b8
  REFCNT = 1
  FLAGS = ()
  ARRAY = 0x5588bbfee1d0 (offset=4)
  ALLOC = 0x5588bbfee1b0
  FILL = -1
  MAX = -1
  FLAGS = (REAL)
[download]

offset + MAX + 1 gives the size of the array buffer, which is 4. The memory "leak" described by the linked post does not exist.

Doesn't change anything if you prevent it from becoming empty.

Creeping forward is not referring to memory leak. What its referring to is the need from time to time for perl to re-allocate memory (which is slow).

Example: Say you have 16 element array a(16). Internally perl will have a(32) and be using 8 to 23 for your 16 spots. This is so push and unshift can work extremely quickly - as there is already allocated space for them (position 7 for unshift, 24 for push)

However if perl is using 8 to 23, and then you push and then unshift, perl is now using 9 to 24. Then 10 to 25. etc. So internally to perl, the array "creeps forward". Eventually, Perl has to either move everything back down (to 8 to 23), or re-allocate (change a(32) to a(64)).

The author is talking about how while most push/pop/shift/unshift is going to work very quickly, occasionally 1 will be slow, while perl performs this internal work.