Nested Calls, Recursion and MEMORY

[robdog]

I wrote a simple recursive routine which file globs a directory, saves all the entires in an array, and recursivly does the same for any sub dirs.. i noticed that a "TON" of memory was consumed, during the process.. and apon return , using Devel::Leak, many many blocks were still allocated..
Calling the same function again, did NOT accumulate any more blocks.. Ok, maybe Perl is reusing the memory.. fine.
So i thought, a recursive function, is just a nested call onto "ITSELF". Would the same memory consumption apply if Function A called Function B, and Function B called Function C? These are just nested calls, but not onto itself. I got back ZERO blocks allocated after Function A. As i wanted. As _should_ be.
So i assumed that nested calls were OK.. but just not on itself. (due to a memory not being immediately released)..
So Obi Wan, i now ask why. Why is memory allocation different when a nested calling function , calls itself, vs calling another function. Does perl have special code to deal with recursion?

Any and all replies are appreciated...

Below is my test code...

System : Win2k, ActiveState 5.6.1.

use strict;



sub cat($)
{
   my $var = shift;
   print "cat ($var)\n";

}

sub bat($)
{
   my $var=shift;
   print "bat ($var)\n";
   cat($var);

}

sub apple($)
{
   my $hello=shift;
   print "Apple ($hello)\n";
   bat($hello);
}


sub recurse($)
{
   my $count=shift;

   print "0Count = ($count)\n";
   if ($count >= 1)
   {
      undef($count);
      print "Leaving...\n";
      return;
   }
   $count++;
   recurse($count);
}

sub recurse1($)
{
   my $count=shift;

   print "Count1 = ($count)\n";
   if ($count >= 1)
   {
      undef($count);
      print "Leaving...\n";
      return;
   }
   $count++;
   recurse2($count);
}

sub recurse2($)
{
   my $count=shift;

   print "Count2 = ($count)\n";
   if ($count >= 1)
   {
      undef($count);
      print "Leaving...\n";
      return;
   }
   $count++;
}

print "GetAll Test\n";
   
   use Devel::Leak;
   my $handle;
   my $count = Devel::Leak::NoteSV($handle);
   print "Memory Count Start = ($count)\n";

   # this loop is here to test accumulation of memory..
   # by increasing the loop max, it does not accumulate
   #  more memory usage.. it _seems_ to reuse....the
   #  results do not change..
  for (my $xx=0; $xx< 1; $xx++)
  {
     recurse(0);       # leaky toilet
    # recurse1(0);    # no leak
    # apple(1);       # no leaks           
  }



  my $count1= Devel::Leak::CheckSV($handle); 
  my $diff = $count1- $count; 
      
  print "\nCount = ($count1)\n";
  print "Difference in Memory = ($diff)\n";

#=== END----

[chromatic]

Your test code looks broken: you're only calling two functions in the recurse1() case.

Even after you fix it, it still won't use as much memory as the recursive case. That's the nature of recursion; every time you make another function call, Perl has to save another stack frame. When you return, Perl pops that frame off the stack. (This is a bit over simplified, but think of it like setting aside a task in memory for a moment to do another task. When the second task is done, you return to the first.)

I wouldn't classify this as a memory leak, because it appears that Perl is doing exactly as it should do.

[robdog]

Thanks for your reply.

The test code is not broken though. The "recurse" function is really recursive, and goes down 2 levels deep. The "recurse1" actually calls "recurse2". This just a 2 level deep nested call. Which pretty much does the same thing as "recurse".

calling recurse, leaves blocks..
calling recurse1, leaves no blocks..

In both examples, they should be saving the same # of call stacks. They essentially do the same thing, they both do a 2 level deep nested call, except that "recurse" calls itself. That is basically the only difference between the two.

so..to rephrase what u said,
Everytime i make another function call (either to myself or another function), Perl has to save another stack frame. When you return (either from myself or another function), Perl pops that frame off the stack.

What im getting at, is that calling yourself or another function in a nested fashion _should_ do the same thing.

but doesnt appear so.

thanks for taking the time to read and answer.

[MarkM]

I would not consider your scenario to show that Perl is 'leaking' memory. Rather, Perl is allocating a bit more memory in a case that you expect should allocate the same or less memory.

Perl requires store to hold lexical variables. For functions that are called many times, but never recursively, Perl can reuse the same lexical variable storage ('pad') for each invocation. When a function is called recursively, new lexical variable storage needs to be allocated, because the previously available storage is currently in use.

The memory is not lost or 'leaked'. Simply, Perl doesn't have an appropriately sized memory block in its freelist, so it allocates a new one.

If you wanted to prove that the memory was actually leaked, you would need to show that multiple iterations of the recurse() function lost additional memory at each iteration. I do not believe that you will find this.

[Anonymous Monk]

Thank you MarkM, for your insights into the memory management of Perl. Very very very helpful.

So to recap what i have discovered..

*) Perl DOES do something different when a function calls itself, vs calling another function. If a function which is currently invoked, gets invoked by another or itself, it will allocate more memory, due to the fact that the current variables are already in use.
I didnt exhibit the extra memory allocations in my Non recursive nested calls, because no functions were ever invoked on themselves. Thus no need to allocate more memory.
It is not like C, where the functions local variables are pushed onto a stack, and it doest matter if it calls itself or another function. It would all be pushed and popped off correctly.

As my test code above demonstrated, running the "leaky" recurse function in a loop, does not accumulate more memory. It is reused. So , technically, its not a memory leak.

In my certain situation, where at the START of my program i do a deeply nested file glob, storing all filenames, then NEVER CALLING that function again, i end up with a program which runs on less memory, and the possibility of virtual memory disk swaps is great.

To get around this, i will create a seperate perl script which file globs to a text file. I will call this script via a system command, and load the text file it created. That way i have no recursion at the start of my main program, more memory and less disk swaps because of virtual memory.

So to continue my education, does anyone know or can point me to the sourcefile or document which technically explains how PERL deals with memory, global vars, local vars, etc? What technically happens when you do a local() or a my? I know C, C++/, many flavors of asm, so the more low level the better.

thank you again
rob