Adventures in Debugging a Perl/Tk Game

Happy New Year, all!

My current "spare-time" Perl divertisement has been the creation of a puzzle program in Perl/Tk, which mimics a real-life wooden puzzle shown to me by a coworker. Ultimately, the goal is to have the program "solve" the puzzle using recursion, but the first step has been achieved; namely being able to move the various pieces around the board. (If I'm pleased with it, when it's finished I'll post it at Perlmonks).

Recently, while trying to solve the puzzle myself (and failing, thus far), it became clear after a large number of moves that the program had a memory leak somewhere -- it would become less and less responsive, and my initial guess was that one of the Tk Canvas objects was being incorrectly deleted.

That is to say, although the program attempted to $canvas->delete() every object created ($canvas->createLine(), $canvas->createOval(), etc.), there was very likely a location where the delete was not happening, so as to give the sluggish performance one sees when Perl/Tk is overloaded.

To aid me in the search for the offending code, I created the following block:

BEGIN {
    my $p_id_hash = { };

    sub my_create {
        my ($w, $thing, $pparams) = @_;
        my $id = $w->$thing(@$pparams);
        my $pinfo = caller_info();
        $p_id_hash->{$id} = [ $thing, @$pinfo ];
        return $id;
    }

    sub caller_info {
        my $ln  = (caller(1))[2];
        my $sub = (caller(2))[3];
        return [ $ln, $sub ];
    }

    sub my_delete {
        my ($w, $id) = @_;
        my $pinfo = $p_id_hash->{$id} || 0;
        if (!$pinfo) {
            error_msg("Attempt to delete ID '$id' twice!");
        } else {
            $w->delete($id);
            delete $p_id_hash->{$id};
            return $id;
        }
    }

    sub show_id_hash {
        my @keys = sort keys %$p_id_hash;
        my $total = @keys;
        print "=" x 79, "\n";
        for (my $i = 0; $i < $total; $i++) {
            my $key = $keys[$i];
            my $pval = $p_id_hash->{$key};
            my ($thing, $ln, $sub) = @$pval;
            printf "%3d.  %16.16s -- %s[%4d]\n", $i+1, $thing, $sub, $
+ln;
        }
        print "Total keys = $total\n";
        print "=" x 79, "\n";
    }
}
[download]

The subroutine my_create() gets called in place of normal canvas "create" subroutines, so instead of creating (and later deleting) a rectangle with:

my $id = $canvas->createRectangle(@opts);
 ...
$canvas->delete($id);
[download]

the following code does the same thing:

my $id = my_create($canvas, "createRectangle", [ @opts ]);
 ...
my_delete($canvas, $id);
[download]

but also keeps track of all objects created in the Canvas. Additionally, an extra button labelled "Show ID Hash" calls show_id_hash() to dump out the table of currently allocated objects, to see whether if it's growing as suspected.

Perl provides the splendid caller functionality so useful for conjuring up stack traces, and, in this case, providing helpful context as to where my_create() and my_delete were called from. Sure enough, each time a move is made, an extra 20 IDs are in the ID hash:

 ...
 32.        createText -- main::draw_coordinates[ 936]
 33.        createText -- main::draw_coordinates[ 936]
 34.        createText -- main::draw_coordinates[ 936]
 35.        createText -- main::draw_coordinates[ 936]
 36.        createText -- main::draw_coordinates[ 936]
 37.        createText -- main::draw_coordinates[ 936]
 38.        createText -- main::draw_coordinates[ 936]
 39.        createText -- main::draw_coordinates[ 936]
 40.        createText -- main::draw_coordinates[ 936]
 41.        createText -- main::draw_coordinates[ 936]
 42.        createText -- main::draw_coordinates[ 936]
...
[download]

And this makes sense, because in this particular puzzle, there are 20 squares which, when "coordinate mode" is on, each have a string written to them containing the (x,y) coordinate pair (mostly for debugging). And -- no surprise -- the subroutine which writes this string is called draw_coordinates():

sub draw_coordinates {
    my ($pboard) = @_;

    # Delete existing coordinate text
    my $canvas = $pboard->{'canvas'};
    my $ptext  = $pboard->{'text'};
    map { my_delete($canvas, $_) } @$ptext;
    $pboard->{'text'} = [ ];

    for (my $i = 0; $i < $ncols; $i++) {
        my $x = $borderx + $i * $cellx + $i * $linex + $linex / 2;
        for (my $j = 0; $j < $nrows; $j++) {
            my $y = $bordery + $j * $celly + $j * $liney + $liney / 2;
            my @opts = ($x, $y, -text => coor_to_square([$i, $j]));
            push @opts, -anchor => 'nw';
            ($coor_font || 0) and push @opts, -font => $coor_font;
            my $id = my_create($canvas, "createText", [@opts]);
            push @$ptext, $id;
        }
    }
}
[download]

Now what I was trying to do in the above subroutine was get the hash containing the previously created text IDs:

    my $ptext  = $pboard->{'text'};
[download]

... delete all of them:

    map { my_delete($canvas, $_) } @$ptext;
[download]

... reassign to an empty anonymous array:

    $pboard->{'text'} = [ ];
[download]

... and then, in a loop, create the 20 new IDs, and save them for later deletion:

        ...
        my $id = my_create($canvas, "createText", [@opts]);
        push @$ptext, $id;
[download]

But there was a sneaky memory leak here! Can you see it?

This debugging exercise reminded me that when writing Perl programs, half the fun is the "sleuthing" one does to find those latent, lurking bugs.

And Perl sure does give you all the tools to make it fun!

s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/

Comment on Adventures in Debugging a Perl/Tk Game Select or Download Code

Replies are listed 'Best First'.
Re: Adventures in Debugging a Perl/Tk Game by kyle (Abbot) on Jan 16, 2008 at 04:15 UTC
Thanks for sharing your puzzle with us! I take no small pride in saying that I saw the bug before I read the spoiler (to confirm what I thought I saw). My hubris is enhanced. I was suspicious of this for a moment: `map { my_delete($canvas, $_) } @$ptext;` [download] Rather than map in void context, how about this: `my_delete($canvas, $_) for @{$ptext};` [download] ...or even: `for (@{$ptext}) { my_delete($canvas, $_) }` [download]	[reply] [d/l] [select]
Re^2: Adventures in Debugging a Perl/Tk Game by liverpole (Monsignor) on Jan 16, 2008 at 14:52 UTC
Thanks for the feedback. But I'm comfortable using map, and I don't see anything wrong with using it in void context. Here's a node I would refer you to: is the use of map in a void context deprecated ?, which elaborates further. In it, liz says: `...I seem to recall that map was just rewritten to check for void context and avoid the extra work if possible. That is correct. And it's in Perl 5.8.1! From the 5.8.1. perldelta: "map" in void context is no longer expensive. "map" is now context aware, and will not construct a list if called in void context.` [download] And I particularly like Abigail-II's reply: "Think for yourself.", as well as Abigail-II's many successive comments in the thread. Update:: I also have to mention BrowserUk's final word in the thread, which links to this: `Larry Wall (<larry {at} wall.org>) Re: grep/map in void context perl.porters-gw The argument against using an operator for other than its primary purpose strikes me the same as the old argument that you shouldn't have sex for other than procreational purposes. Sometimes side effects are more enjoyable than the originally intended effect.` [download] s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/	[reply] [d/l] [select]
Re^3: Adventures in Debugging a Perl/Tk Game by kyle (Abbot) on Jan 16, 2008 at 17:43 UTC
Thanks for the references. I understand Abigail-II's arguments, but I find that I agree with tilly's reply and demerphq's reply to the reply. When I see map in void context, it makes me wonder if the programmer meant something different than what's written. Was that line an assignment before? Was the returned list being used for something? Did the programmer forget something? Not long ago, I encountered "`(my $x, $y) = f()`", which is equivalent to "`my $x;($x, $y) = f()`". As it turned out, that is what the programmer intended, but I spent quite a while finding that out, because at first glance I wondered if it was supposed to be "`my ($x, $y) = f()`". (Back to `map`.) Given that the equivalent code (with `for`) is just as easy to write, the `map` stands out. If you're using it to get a list context (as mentioned in Re: Think for yourself.), then I think that would make an excellent comment right above. (As a semi-side remark, in Re: Think for yourself., Abigail-II says that a familiarity with map (from experience in other languages) that predates Perl's `map` is some part of the reason for seeing it as just another looping construct. I, too, was using maps in Scheme before I ever saw it in Perl, so I find it interesting that I don't share that view of it.) Thanks again for the references. It really is fascinating reading, and I recommend it to any other monk reading this.	[reply] [d/l] [select]
Re: Adventures in Debugging a Perl/Tk Game (other leak) by tye (Sage) on Jan 16, 2008 at 18:31 UTC
I disagree with some of your analysis. `@$av= ();` vs. `$av= [ ];` only matters if you are leaking references to the original (anonymous) array (such as via circular references). Your "fix" reduces the impact of the leak that makes the unreferenced anonymous array not get destroyed. But I'm not particularly surprised to find unreferenced things not being destroyed when using Tk. When I've used Tk I've had to be careful to not create a lot of anonymous things because it appeared that Tk was prone to preventing things from being destroyed. Part of this may have been due to the problem of closures causing Perl to create its own circular references but I thought there was more to it than that. But having bugs in ref counting and related stuff is almost assured when you have that volume of XS code. - tye	[reply] [d/l] [select]
Re^2: Adventures in Debugging a Perl/Tk Game (other leak) by liverpole (Monsignor) on Jan 16, 2008 at 20:35 UTC
I'm not sure if you misunderstood what I meant, or if I'm not quite following your reply. Just in case, I'll show you a visual representation (and also because I originally thought this would make things more clear): + + Code / Comments Visually ====================================================================== +======== my $ptext = $pboard->{'text'}; pboard->text ====+ \| v ptext ====> [ (some IDs) ] + + + + $pboard->{'text'} = [ ]; pboard->text ===> [ ] # Now they're pointing to ptext ==========> [ (some IDs) ] # different things + + + + my $id = my_create($canvas, ...); pboard->text ===> [ ] push @$ptext, $id; ptext ===========> [ (some IDs), $i +d ] # But my intent was to add $id to # $pboard->{'text'}! [download] Now it's clear that (some IDs) in the picture disappears (when $ptext goes out of scope at the end of the subroutine), and never gets pushed into the intended array $pboard->{'text'} (so the Canvas text is never successfully deleted). I'm quite sure from calling `show_id_hash()` that the Canvas text objects were never getting deleted (even though their numeric IDs were when `$ptext` went out of scope). And it's also clear to me that the same text objects do get deleted when I correctly reassign `$ptext` to point to the anonymous array which was assigned to $pboard->{'text'} (or by emptying out the original array with `@$ptext = ( )`). Does that make my intent any clearer, or do you still find something amiss? s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/	[reply] [d/l] [select]
Re^3: Adventures in Debugging a Perl/Tk Game (other leak) by tye (Sage) on Jan 17, 2008 at 05:04 UTC
Yes, that is clearer. Thanks. If DESTROY doesn't clean up a canvas, then that supports my impression of Tk encouraging memory leaks. If it is too difficult to have DESTROY clean up, then I would rather have DESTROY complain that I forgot to clean up. But in a programming environment with OO and where exceptions can be thrown, I've come to consider any clean up that is not done from within a destructor (DESTROY in Perl) to be a bug. Expecting people to do the equivalent of matching up malloc() and free() calls is just the perfect recipe for bugs. So I still interpret what you described as more you not successfully working around an ugly feature of Tk, even though it wasn't quite the feature I originally thought. I get the impression that it wasn't actually the leaked memory that was the problem. It sounds like the real problem was the number of objects Tk had to sift through more than the memory size of the process. But that wasn't clear to me from your description. - tye	[reply]
Re: Adventures in Debugging a Perl/Tk Game by zentara (Cardinal) on Jan 16, 2008 at 17:56 UTC
I'm sure I'm side-stepping your question, but I did flash on something regarding the "speed of deletion". Find seems to work better sometimes, then delete the array. `#untested my @selected = $canvas->find('withtag', 'in_polygon'); foreach(@selected){ $canvas->delete($_); }` [download] I'm not really a human, but I play one on earth. Cogito ergo sum a bum	[reply] [d/l]
Re: Adventures in Debugging a Perl/Tk Game by Limbic~Region (Chancellor) on Jan 18, 2008 at 00:16 UTC
liverpole, Have you seen Challenge: Setting Sun Puzzle? I had intended to make a GUI out of my unposted solution but that probably won't happen until I win the lottery. Cheers - L~R	[reply]
Re^2: Adventures in Debugging a Perl/Tk Game by liverpole (Monsignor) on Jan 18, 2008 at 02:53 UTC
Hi Limbic~Region, I hadn't read that node before, but from the description, it looks like the same puzzle as mine. I saw that tye provided a solution, but I didn't look too closely as I want the fun of solving it for myself. Ironically, I started the other way around -- I created a gui that would let you play it, and have only now started working on the "auto-solver" mechanism. I didn't know at first even what the name of the puzzle was, but after working on getting the gui running, I've since found descriptions of it (and related puzzles) on the Internet. This particular puzzle has several names -- in French it's "L'ane Rouge" ("Red Donkey") -- it's also called Klotski ("wooden blocks" in Polish). A short while later a friend gave me a book about Perl written in Japanese as a birthday present, which coincidentally discusses the very same puzzle. The Japanese version is called "hakoiri musume" ("Daughter in the box"), and uses Chinese characters for the pieces. I'm still working on solving it (both by hand, and by developing a recursive algorithm), and I'm resisting the temptation to peek at any solutions until then. I'm also thinking to expand the puzzle to incorporate other rules (such as "Rush Hour", which is very similar in nature). Once I'm satisfied with it, I'll post it at Perlmonks. s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/	[reply]