It's reasonably straightforward. Every time you take a reference to something, Perl increments its reference count by one. Every time you get rid of a reference to something, Perl decrements its reference count by one. When the reference count reaches zero, Perl recycles the item, because nothing else refers to it.

For the purpose of this discussion, read "take a reference to" as meaning "use in a way that you want to keep it around" -- closing over a lexical variable counts, for example.

The problem with that, which your first example shows, is when two items refer to each other. The object referrred to by $top has two references, one from the lexical variable and one from the contained Bottom object. The Bottom object has one reference, from the $top object. Their reference counts will never reach zero and Perl will never reclaim them because they refer to each other.

The solution is to make one of the references a weak reference. A weak reference refers to another item but does not increment its reference count when you first refer to it, nor does it decrement its reference count when the weak reference goes away.

The problem in your second example is that you made both references weak references far too early, so when the reference count to the Bottom object reached zero (that is, when you weakened the reference), Perl cleaned it up.

Your code would work if you made $top a weak reference within the Bottom constructor, as you have other references keeping $top active but nothing else keeping the Bottom object active.

chromatic -

Thank you for taking the time for such a thorough explanation.

I never quite understood it, but now I do.

Weak references "die" as soon as no other reference to the object exists, so you have to weaken something to which initially two references exist (which is class Top, which is referenced in main and and Bottom).

Thanks for the short answer. I did just that, and it worked beautifully.

Final code example:


package Top;

sub new {
  my $class = shift;
  my $s = bless { }, $class;
  $s->{bottom} = Bottom->new( $s );
  return $s;
}

#=====================================

package Bottom;
use Scalar::Util 'weaken';

sub new {
  my ($class, $top) = @_;
  my $s = bless { top => $top }, $class;
  weaken($s->{top});
  return $s;
}

#=====================================

package main;

use strict;
use warnings 'all';
use Devel::Cycle;

my $top = Top->new();
my $bottom = $top->{bottom} or die "NO BOTTOM!";
$top = $bottom->{top} or die "NO TOP!";

find_cycle( $top );
find_cycle( $bottom );
[download]

Expected output: (nothing)

UPDATE: - Now it burns through 52Mb RAM in 26 seconds. Not sure if that's good or bad. I would expect Perl to recycle the RAM. Is that expectation wrong? Sure, 52Mb is better than the original number of 200Mb, but I would like to see no leakage at all.

Is it possible to do this without leaking memory?

Changing the main code to

package main;

use strict;
use warnings 'all';
use Devel::Cycle;

for( 1...1_000_000 )
{
  print "\r$_/1000000";

  my $top = Top->new();
  my $bottom = $top->{bottom} or die "NO BOTTOM!";
  $top = $bottom->{top} or die "NO TOP!";

  find_cycle( $top );
  find_cycle( $bottom );
}
[download]

the memory usage on my box remains steady at 2476 kB, so your memory leak has to be somewhere else. Your code as posted is fine so far.

This is leaking since Change 26530.

http://public.activestate.com/cgi-bin/perlbrowse/p/26530:

Change 26530 by nicholas@nicholas-saigo on 2005/12/30 01:08:46

	RMAGIC on symbol tables is bad, m'kay.
	Allow hashes (and therefore all symbol tables) to store the
	backreference array in the hv_aux structure, and thereby undo the
	performance damage of 24966, which resulted in 60% of all hash lookups
	trying to mg_find tiehash magic.

One instance of this in the RT queue of perl: #56908: DBI memory leak

Dave Mitchell commited a change for this: http://public.activestate.com/cgi-bin/perlbrowse/p/34209:

Change 34209 by davem@davem-pigeon on 2008/08/20 23:15:36

	perl #56908 DBI memory leak in 5.10.0 due to change 26530
	
	A weakref to a HV would leak, because the xhv_backreferences
	array is created with a refcount of 2 (to avoid premature freeing
	during global destruction), but the RC was only decremented once
	when the parent HV was freed.
	Also, when thread cloned, the new array was being created with a
	RC of 1, rather than 2, which coincidentally worked due to the
	first bug.

but testing this change and trying to wrap it in a good test case is still on my todo list.

(Running it with a blead after Change 34209 shows no leak)