Hello, thanks for the suggestions!

I think I should have been specific -- when I said "not sparse", I actually meant that the data structure had been fully created in advance with a loop exactly like this. I've added in the checks, and before the program the program crashes (about 3 hours of CPU) it does not every autovivify.

One thing that goes on inside the #do great deeds is to change values in the Array part of the HoHoA, and I had expected that to be the cause of my memory leak. I'm really confuzzled as to why this:

foreach my $value ( @$subarray ) {
[download]

would eat up memory. I would have guessed it would use one scalar's worth (perhaps 15 bytes of data), and that this memory would get reused over & over again. Instead, the script runs on this loop for a few hours before using up all the memory.

I'm really confuzzled as to why this:

foreach my $value ( @$subarray ) {
[download]

would eat up memory.

That line expands the contents of the array into a list (Ie. On Perls' stack). If the subarray pointed by $subarray is large, it will consume a large amount of memory to do that.

You can avoid that by indexing the array, rather than aliasing it's elements. Eg.

for my $index ( 0 .. $#$subarray ) {
    my $value = $subarray->[ $index ];
    ...
}
[download]

Or, if you need to modify the elements, substitue $subarray->[ $index ] wherever you are currently using $value.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

That line expands the contents of the array into a list (Ie. On Perls' stack). If the subarray pointed by $subarray is large, it will consume a large amount of memory to do that.

But... but... wait a minute. I thought that in this sort of loop:

  for $value ( @array ) { # or ( @$arrayref )
     # do something with $value
  }
[download]

the "$value" is just being used as a "magical" reference to the actual values in the array. If you do something like $value++ inside the loop, the values of the original array are incremented in place -- the increment doesn't apply to copies of the array elements.

So, why would that sort of loop consume extra memory? Why would it make a separate list from @array (or from the actual array pointed to by @$arrayref), when $value is being used as a reference to each array element in turn? (If it really does take up extra memory, then I'm just making clear how little I understand about the underlying implementation of for loops in perl, and if someone explains it to me, I'll probably be better off at some point...)

The dialog so far leads me to think that the AM has some other trap or "gotcha" inside that nested loop, which hasn't been shown yet, and which is probably causing some horribly unintended consequence (e.g. something like the now-infamous sprintf bug).

(updated to add link to Format string vulnerability)

Another update: Okay, your reference to "Perl's stack" is probably the part I hadn't understood before: in order to process (queue-up) the elements to be iterated over, the for loop has to push the whole set of elements onto a stack. But then, I would presume that in the AM's situation, with that particulat for loop being done so many times, Perl would be re-using that stack space.

Obviously, if the array in question is really big, the stack could boil over -- OOM -- at the first attempt on the inner-most for loop. This seems consistent with the reported symptoms, and iterating over an array index instead of array values might fix it.

Okay, I'm curious: does this matter? In my case the foreach loop is going over arrays that have ~100 elements. In this case, I would have expected the maximum memory usage to be 100 x (element-size + over-head). That doesn't seem too large, but it assumes that all memory is getting smoothly cleared after the foreach loop is finished. is that a valid assumption?

YES YES YES!!!

No matter how sure I was about the data-structure being properly created, I decided to out code like inside my loop:

if ( exists( $data{$array[$i]}{$array[$j]} ) ) {
        next();
        }
else {
        print OUT join("\t", $i, $j), "\n";
        }
[download]

and... wouldn't ya know it, there *were* elements being autovivified. I've fixed that problem, and now the code appears to be running correctly (appears = its been running for a day without crashing yet -- it still has another couple of days to run, though).

Many thanks -- this has led me to one key problem in the code. Any monks who haven't done so yet, please ++ the parent.