Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: OOP/Linked List Question

by ambrus (Abbot)
on Feb 07, 2005 at 17:08 UTC ( #428746=note: print w/ replies, xml ) Need Help??


in reply to OOP/Linked List Question

Just two words of caution. If you create a long list-like structure in perl, you have to take care how it is deleted when the reference count drops to zero. For example, this code causes a segfault on my machine:

perl -we '$x = 1; $x = [$x] for 0 .. 0 + $ARGV[0]; $x = ();' 50000
(you might have to increase the numeric argument to reproduce this). This is because as the reference-count garbage-collector deletes $x<code>, it has to delete <code>$$x[0] first, for which it has to delete $$x[0][0] first etc, and it does this thing recursively. This would not normally be a problem, but can cause a problem in two cases. Firstly, stack space is used for this recursion, which is limited, so in the case of such a long list, the stack will be full and that's why you get the error. Indeed, if you look at the backtrace, you'll see a long stream of frames like this:
... #78 0x080bd016 in Perl_sv_free () #79 0x080acd3e in Perl_av_undef () #80 0x080bcd9a in Perl_sv_clear () #81 0x080bd016 in Perl_sv_free () #82 0x080bcad5 in Perl_sv_clear () #83 0x080bd016 in Perl_sv_free () #84 0x080acd3e in Perl_av_undef () #85 0x080bcd9a in Perl_sv_clear () #86 0x080bd016 in Perl_sv_free () #87 0x080bcad5 in Perl_sv_clear () #88 0x080bd016 in Perl_sv_free () #89 0x080acd3e in Perl_av_undef () #90 0x080bcd9a in Perl_sv_clear () #91 0x080bd016 in Perl_sv_free () #92 0x080bcad5 in Perl_sv_clear () ...

The other problem is circular references. A doubly-linked list contains circular references, so if you just undef a reference to it, it will contain circular references, the reference count will never drop to zero, and memory will leak. You can usually avoid this by explicitly undefing some refernces inside the data structure when you want to free the list. The DESTROY method can help you in this. For example, this code leaks memory (again, increase the numeric argument to make it leak more):

perl -we 'for (0 .. $ARGV[0]) { my $y = 1; my $x = \$y; $x = [$x] for +0 .. 1000; $y = $$x[0]; }; system "ps u $$"' 1000

Update: The first problem is not that easy to cure, but it is possible. Doing some quick tests, it seems that the garbage-collector in (newer) pythons, the one in Mathematica, and the one in maple are free from this defect; while the simple one in ruby, -- wierdly -- that of bigloo scheme, and (Update) that of guile too have the same limitation. (This of course doesn't mean anything as those are not refcounting gcs, but mark-and-sweep or some similar.) As for the second one, it's specific to reference counting.


Comment on Re: OOP/Linked List Question
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://428746]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2014-09-02 02:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (18 votes), past polls