Re^2: How to implement a Queue that doesn't leak memory?

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

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}

Comment on Re^2: How to implement a Queue that doesn't leak memory?

Replies are listed 'Best First'.
Re^3: How to implement a Queue that doesn't leak memory? by hippo (Archbishop) on Feb 03, 2024 at 16:47 UTC
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. 🦛	[reply] [d/l] [select]
Re^4: How to implement a Queue that doesn't leak memory? by LanX (Saint) on Feb 03, 2024 at 17:13 UTC
> Of course, but so could any program doing anything. That doesn't constitute a leak. maybe I misread "reallocating", if that means that at some point the whole array is moved (copied) to a formerly released memory location it's fine. If Perl was only allocating forward after x `push` and releasing backwards after x `shift` and the released memory wasn't reused otherwise, then memory consumption for the process would grow. This I'd call a leak. It would be interesting to know how and when this reallocation happens and if it's automatically done on C-level. update I now seem to remember (in the context of paging to the disk) that memory management operates on physical blocks or pages which are dispersed over RAM, and translates a virtual address to a physical one. Hence a released block would be naturally reused, without much intervention. :) Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re^5: How to implement a Queue that doesn't leak memory? by eyepopslikeamosquito (Archbishop) on Feb 04, 2024 at 02:13 UTC
> It would be interesting to know how and when this reallocation happens and if it's automatically done on C-level I suggest you study your good friend ikegami's excellent Mini-Tutorial: Perl's Memory Management ... which concludes with: You can't rely on memory being returned to the system, but it can happen ... if and when memory is returned to the OS is dependant on the memory allocation mechanism perl was compiled to use ... you are more likely to see memory being released to the OS on Windows See also: Returning Memory back to the OS References 👁️🍾👍🦟	[reply]
Re^5: How to implement a Queue that doesn't leak memory? by Anonymous Monk on Feb 05, 2024 at 14:19 UTC
It would be interesting to know how and when this reallocation happens and if it's automatically done on C-level. No, nothing is automatic in C. Heck, C barely has arrays but normally you would malloc(3) an intial size and when you need more memory you would use realloc(3) to ask for more. A lot of time realloc can just extend the array but sometimes it needs to allocate more space and memcpy into the new larger space. I wish I had the link where I saw it (LWN?) but it turns out that, in practice, Linux can do some magic with pages and you almost never get that stall from having to copy the whole array. I don't know what perl does under the covers but it is extremely likely it follows this traditional approach.	[reply]