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

In reply to Re^2: How to implement a Queue that doesn't leak memory? by LanX
in thread How to implement a Queue that doesn't leak memory? by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.