Section 11.4. Cyclic References

Use weaken to prevent circular data structures from leaking memory.

Actual circular linked lists are quite rare in most Perl applications, mainly because they're generally not an efficient solution. Nor are they particularly easy to implement. Generally speaking, a standard Perl array with a little added "modulo length" logic is a cleaner, simpler, and more robust solution. For example:


    {
        # Make variables "private" by declaring them in a limited scope
        my @buffer;
        my $next = -1;

        # Get the next element stored in our cyclic buffer...
        sub get_next_cyclic {
            $next++;                   # ...increment cursor
            $next %= @buffer;          # ...wrap around if at end of array
            return $buffer[$next];     # ...return next element
        }

        # Grow the cyclic buffer by inserting new element(s)...
        sub insert_cyclic {
            # At next pos (or start): remove zero elems, then insert args...
            splice @buffer, max(0,$next), 0, @_;

            return;
        }

        # etc.
    }

However, circular data structures are still surprisingly easy to create. The commonest way is to have "owner" back-links in a hierarchical data structure. That is, if container nodes have references to the data nodes they own, and each data node has a reference back to the node that owns it, then you have cyclic references.

Non-hierarchical data can also easily develop circularities. Many kinds of bidirectional data relationships (such as peer/peer, supplier/consumer, client/server, or event callbacks) are modeled with links in both directions, to provide convenient and efficient navigation within the data structure.

Sometimes the cycle may not even be explicitly set up (or even intentional); sometimes it may just "fall out" of a natural arrangement of data^[*]. For example:

^[*] So it's something you need to watch for whenever you're setting up complex data structures.

    
    # Create a new bank account...
    sub new_account {
        my ($customer, $id, $type) = @_;

        # Account details are stored in anonymous hashes...
        my $new_account = {
            customer  => $customer,
            id        => generate_account_num(  ),
            type      => $type,
            user_id   => $id,
            passwd    => generate_initial_passwd(  ),
        };

        # The new account is then added to the customer's list of accounts...
        push @{$customer->{accounts}}, $new_account;

        return $new_account;
    }

In the resulting data structure, each customer ($customer) is really a reference to a hash, in which the "accounts" entry ($customer->{accounts}) is a reference to an array, in which the most recently added element ($customer->{accounts}[-1]) is a reference to a hash, in which the value for the "customer" entry ($customer->{accounts}[-1]{customer}) is a reference back to the original customer hash. The great and mystical Circle Of Banking.

But even if it's stored in a lexical $customer variable, the allocated memory for this data structure will not be reclaimed when that variable goes out of scope. When $customer ceases to exist, the customer's hash will still be referred to by an entry in the hash that is referred to by an element of the array that is referred to by an entry in the customer's hash itself. The reference count of each of these variables is still (at least) one, so none of them is garbage collected.

Fortunately, in Perl 5.6 and later, it's easy to "weaken" references in order to break this chain of mutual dependency:


    use Scalar::Util qw( weaken );

    # Create a new bank account...
    sub new_account {
        my ($customer, $id, $type) = @_;

        # Account details are stored in anonymous hashes...
        my $new_account = {
            customer  => $customer,
            id        => generate_account_num(  ),
            type      => $type,
            user_id   => $id,
            passwd    => generate_initial_passwd(  ),
        };
        
        # The new account is then added to the customer's list of accounts...
        push @{$customer->{accounts}},
             $new_account;

        # Make the backlink in the customer's newest account
        # invisible to the garbage collector...
        weaken $customer->{accounts}[-1]{customer};

        return $new_account;
    }

The weaken function can be exported from Scalar::Util under Perl 5.8 and later (or from the WeakRef CPAN module if you're running under Perl 5.6). You pass weaken one argument, which must be a reference. It marks that reference as no longer contributing to the garbage collector's reference count for whatever referent the reference refers to. In other words, weaken artificially reduces the reference count of a referent by one, but without removing the reference itself.

In the second version of the example, the customer hash originally had a reference count of 2 (one reference to it in the $customer variable itself, and another reference in the nested hash entry $customer->{accounts}[-1]{customer}). Executing the line:


        weaken $customer->{accounts}[-1]{customer};

reduces that reference count from two to one, but leaves the second reference still in the nested hash. It's now as if only $customer referred to the hash, with $customer->{accounts}[-1]{customer} being a kind of "stealth reference", cruising along undetected below the garbage collector's radar.

That means that when $customer goes out of scope, the reference count of the customer hash will be decremented as normal, but now it will decrement to zero, at which point the garbage collector will immediately reclaim the hash. Whereupon each hash reference stored in the array in $customer->{accounts} will also cease to exist, so the reference counts of those hashes will also be decremented, once again, to zero. So they're cleaned up too.

Note also that a weakened reference automatically converts itself to an undef when its referent is garbage-collected, so there is no chance of creating a nasty "dangling pointer" if the weakened reference happens to be in some external variable that isn't garbage-collected along with the data structure.

By weakening any backlinks in your data structures, you keep the advantages of bidirectional navigation, but also retain the benefits of proper garbage collection.

Table of Contents