My Connect 4 game written in Jack! Leaks memory ... FIX'D

[sgaweda]

At first I thought I was just going to skip over chapter 9 and head straight into writing the compiler, but then I thought about it and decided that I would be doing the course disservice if I didn't at least try to use Jack and myself a disservice if I didn't learn it well before trying to write the compiler. Writing the VM to Hack translator was mostly difficult because I found myself returning to past chapters frequently searching for methods to implement simple instructions and to brush up on the rules of the language. By spending the time to learn as much as I could about Jack I know that I've situated myself in a position to have a much easier time in the next two chapters.

My girlfriend and I have been joking about buying a Connect 4 board for some time and I saw an opportunity to kill two birds with one stone by making my own. This forum has been invaluable to me as I've moved through the course and so I'm happy to share the first version of the game here!

Connect_4.zip

This version of the game suffers from a memory leak and so this post holds two purposes. First is to share my working game and the second is to ask for guidance on how to solve the memory issues currently plaguing the game. My experience as a novice programmer has been limited mostly to Java and C# and as such I've never had to do any memory management. I wasn't able to find much on the topic here on the forums, so hopefully this post will help others solve their memory management issues in the future as well.

[cadet1620]

sgaweda wrote

This version of the game suffers from a memory leak...

If you have a massive leak -- your program runs out of memory very quickly while running the game -- you probably are not freeing string constants.

This is a problem specific to the Jack language.  When you write something like

    do Output.printString("Hello world!");

a String object is allocated and never freed. What you need to do is use a String variable to print the constant

    var String str;
    ...
    let str="Hello world!";
    do Output.printString(str);
    do str.dispose();

This is a major pain in the butt for Jack programming, but makes writing the Jack compiler much easier!

I wrote a OutUtil class that has useful printing functions that do this dispose automatically. For instance, instead of "do Output.printString(str);" use "do OutUtil.printStringConst(str);"

If you use search-and-replace to make this change, be careful not to call printStringConst for strings vars that you don't want disposed.

Here's a bit of my OutUtil.jack:

    class OutUtil {

    /**
     *    Print constant 'str' and dispose it.
     */
        function void printStringConst(String str) {
            do Output.printString(str);
            do str.dispose();
            return;
        }

    /**
     *    Print 'str' followed by new-line.
     */
        function void printStringLn(String str) {
            do Output.printString(str);
            do Output.println();
            return;
        }

    /**
     *    Print constant 'str' followed by new-line.
     */
        function void printStringConstLn(String str) {
            do OutUtil.printStringConst(str);
            do Output.println();
            return;
        }

Let me know if you have a more subtle leak -- I'm buried at work and won't get a chance to look at your game until this weekend.

--Mark

[sgaweda]

This may be the key problem I'm facing as the issue is most noticeable when I move back and forth from the instructions page to the main menu.

That being said I'm not sure I understand how your OutUtil class solves this issue. Take the following code as an example:

cadet1620 wrote

    /**
     *    Print constant 'str' and dispose it.
     */
        function void printStringConst(String str) {
            do Output.printString(str);
            do str.dispose();
            return;
        }

When you pass the string to the method doesn't that also create a string constant? Looking at this code I can see three potential ways this is executed:

First is that a string object is created by the compiler and given an address and then str points to that address. Disposing str then frees str but leaves the string constant still pointing to the same location.
Second is that the string object is created by the compiler and given an address and then str points to that address. Disposing str then clears up all references that point to the same object.
Third is that the string constant is never converted into a string object at all which means a string object is created and assigned when the method is called resulting in only one reference to the string.

I'd imagine the first one isn't how it's done, so the second or third must be closer to the truth, but I'm not sure I understand this completely and I'd rather be sure I understand why it works before I start making changes to my code. If you could elaborate a bit I'd really appreciate it.

On the topic of subtle leaks, it's very likely I have some, but I'm confident solving this string issue will tackle the biggest leak I'm currently dealing with.

[cadet1620]

There are no references or reference counting in Jack. That's a very complex concept to implement. The Jack language is extremely simpleminded so that it is easy to write a Jack compiler.

What happens with do OutUtil.printStringConst("whatever") is that a String object that contains "whatever" is allocated and the memory address of that object is passed to printStringConst(). Therefore printStringConst() is working with the exact same String object. When printStringConst() calls str.dispose() it is deallocating the String object that the calling function allocated.

This is why it is critical that you don't call printStringConst() with a String that you want to reuse.

    var String str;
    let str = "Say it twice...";        // Allocates a String
    do OutUtil.printStringConst(str);   // Deallocates the String
    do OutUtil.printStringConst(str);   // Illegal -- str contains pointer to deallocated memory

--Mark

[cadet1620]

Also see this post. It may give you more insight on why String constants need to be explicitly destroyed.

--Mark

[sgaweda]

I think I understand now what's happening. I've started working on the compiler but I will return to this shortly and post an updated version of the game.

[sgaweda]

I've updated the game with a few fixes. I implemented a utility class to help with disposing of strings. This has solved my issues of being able to crash the game just by going back and forth between screens. Also, recalling what I read here, I implemented disposal code for all of the classes that required it in my game. The only object I'm not disposing is the player object that is passed from class to class for player setup and initialization.

The new version can be downloaded here:

Connect_4_v1.zip

I do however have a couple questions.

First: If you look through my source for the HomeScreen class you'll see that I instantiate one object for each of the three screens that can be accessed from the main screen. I only create them once and they're available for the duration of the game. Would it have been better to create them as they're needed and deallocate them after? I have the lines of code required to do this already written into the class but am not currently using them.

Second: In my ConnectFour class, I allocate a Player object named currentPlayer and use it to point to the current player. Does this object get disposed when the class is disposed? I know that if it is pointing to player1, then calling currentPlayer.dispose() disposes of player1, which ultimately breaks my game. I'm aware I could have implemented currentPlayer as an int instead but a similar situation also occurs in the PlayerSetup class and I want to make sure there's no leaks left in my program.

[ivant]

I haven't had the chance to look at your game yet, so I can only give you some general directions. Memory management is hard. Even if you make sure you don't have any leaks, and you don't deallocate memory twice and you don't use the pointer after you've freed the memory, your program can still run out of it.

Suppose you create an object, which needs 10 bytes, then another which needs two, then one more 10 byte object, and one more 2 byte object. Suppose also, that they are allocated next to each other and in the same order. You then free the two 10 bytes objects.

Next you want to allocate 15 bytes. You can't use the "holes," because they are smaller, so it's new memory again.

Then you allocate 9 bytes. They fit in the first hole, so great, right? But then, you're left with a 1-byte hole, which is unusable.

After awhile you may have 100 bytes free, but you may not be able to allocate a continuous 10 byte region. This is called free memory memory fragmentation.

So, to your first question, it's probably better what you're doing now instead of allocating and deallocating these objects.

On Fri, Oct 9, 2015, 08:38 sgaweda [via Nand2Tetris Questions and Answers Forum] <[hidden email]> wrote:

I've updated the game with a few fixes. I implemented a utility class to help with disposing of strings. This has solved my issues of being able to crash the game just by going back and forth between screens. Also, recalling what I read here, I implemented disposal code for all of the classes that required it in my game. The only object I'm not disposing is the player object that is passed from class to class for player setup and initialization.

The new version can be downloaded here:

Connect_4_v1.zip

I do however have a couple questions.

First. If you look through my source for the HomeScreen class you'll see that I instantiate one object for each of the three screens that can be accessed from the main screen. I only create them once and they're available for the duration of the game. Would it have been better to create them as they're needed and deallocate them after? I have the lines of code required to do this already written into the class but am not currently using them.

Second: In my ConnectFour class, I allocate a Player object named currentPlayer and use it to point to the current player. Does this object get disposed when the class is disposed? I know that if it is pointing to player1, then calling currentPlayer.dispose() disposes of player1, which ultimately breaks my game. I'm aware I could have implemented currentPlayer as an int instead but a similar situation also occurs in the PlayerSetup class and I want to make sure there's no leaks left in my program.

---

If you reply to this email, your message will be added to the discussion below:

http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/My-Connect-4-game-written-in-Jack-Leaks-memory-tp4029226p4029238.html

To start a new topic under Chapter 9, email [hidden email]
To unsubscribe from Nand2Tetris Questions and Answers Forum, click here.
NAML

[cadet1620]

sgaweda wrote

Second: In my ConnectFour class, I allocate a Player object named currentPlayer and use it to point to the current player. Does this object get disposed when the class is disposed? I know that if it is pointing to player1, then calling currentPlayer.dispose() disposes of player1, which ultimately breaks my game. I'm aware I could have implemented currentPlayer as an int instead but a similar situation also occurs in the PlayerSetup class and I want to make sure there's no leaks left in my program.

All variables of object type are pointers that require one memory location. The memory required for the pointer is managed automatically exactly like an int type variable. The memory for the object the pointer points to is what is allocated when the constructor is called and freed when the destructor is called.

In cases like the PlayerSetup class where a field holds a copy of a pointer to an object that was allocated somewhere else in the program, I always add comments to the constructor and destructor.

    constructor PlayerSetup new(Player player1)
    {
        let player = player1;   // PlayerSetup does not own this object.
        let selected = 0;
        let token = Token.new(0);
        
        return this;
    }
    
    method void dispose()
    {
        // Do not dispose player.
        do token.dispose();
        do Memory.deAlloc(this);
        return;
    }

Note that I also always place the destructor immediately following the constructor(s). This makes it easier to remember to add appropriate cleanup code when constructors are changed.

--Mark

[cadet1620]

Memory leaks can be tricky to find. Many systems come with debug versions of their memory manager that can help identify when memory leaks occur.  I added a simple heap dump to my Memory.jack that was quite useful when I was developing my Jack Jack Compiler.

If you want to experiment with it, save this file Memory(debug).vm in your program's directory and rename it to Memory.vm.
(If you get System Error 666 using this Memory.vm, that means that a bad pointer of a block that was already deallocated was passed to Memory.deAlloc.)

I put calls to the heap dump at the beginning and end of your Main.main()

    function void main()
    {
        var HomeScreen hs;

do Memory.debugDumpHeap();
do Keyboard.readChar();
        let hs = HomeScreen.new();
        do hs.run();
        do hs.dispose();
do Output.moveCursor(0, 0);
do Memory.debugDumpHeap();

        return;
    }

I ran your program, hitting escape to exit the game on the first screen. Here are the Heap Dumps.

 

The starting dump shows 3 objects allocated by the OS before Main.main() was called. The ending dump shows that there are 8 objects that were allocated by your program and not deallocated.

The lengths displayed by my dump are the actual amount of memory used by the allocated block and include 2 words overhead[1]. Your unfreed blocks are a 2-word object and 7 6-word objects. Stop the VME and you can look in the RAM to see the objects.



The 2 word object is likely the player object you mentioned. The 7 6-word objects are allocated contiguously so it's likely that they were allocated as a group. I searched through your code for 7 and 6 on the same line which led me to the tokenGrid Matrix.

Take a look at Matrix.dispose(). It disposes the columns Array, but what about the individual columns? Array.dispose() doesn't know what the data stored in the array is, so it can't automatically dispose them.

--Mark

[1] You can see these overhead words in the RAM screenshot. The 29554 is a signature for allocated blocks that Memory.deAlloc() checks to make sure that objects aren't double disposed. Freed blocks have a different signature. The signature is followed by the block size.

[sgaweda]

ivant your reply was invaluable, thank you. I hope you get a chance to try out my game and let me know what you think! I'm open to suggestions for improvement.

Mark, I re-wrote Matrix.dispose() to dispose of the individual arrays stored in the array before disposing the array itself. Took a bit of thinking to rationalize whether or not I needed to still dispose columns as well as each variable at columns[i]. Took a little bit more thinking to realize I couldn't just dispose columns[i] and that I needed to assign it to a temporary variable before disposal.

cadet1620 wrote

The 2 word object is likely the player object you mentioned.

I was a bit confused by the Player object not being disposed, but looking over my code I've run into something I didn't quite expect. When I create the ConnectFour class I create a new Player object and assign it to currentPlayer. When the game starts running, currentPlayer is assigned to other player after each player finishes his/her turn. That is to say that the Player object currentPlayer points to is never used. Furthermore, currentPlayer isn't assigned to point to player1 or player2 until one of the players has completed his/her turn. When you started the game and immediately quit that was likely the object that wasn't disposed of. That being said, I now have two questions about the Jack Compiler's behavior in this scenario. First, when I assign currentPlayer to point to player1 or player2 is the unused Player class effectively disposed of? At that point nothing will point to it again. Second, can I make this a non-issue by not initializing currentPlayer before I assign it the first time to either player1 or player2?

PS. I wish I'd had Memory(debug).vm when I was coding this project. It would've probably saved me a number of headaches.

[cadet1620]

sgaweda wrote

I was a bit confused by the Player object not being disposed, but looking over my code I've run into something I didn't quite expect. When I create the ConnectFour class I create a new Player object and assign it to currentPlayer. When the game starts running, currentPlayer is assigned to other player after each player finishes his/her turn. That is to say that the Player object currentPlayer points to is never used.

Yes, that's what is causing the leaked Player object.

I now have two questions about the Jack Compiler's behavior in this scenario. First, when I assign currentPlayer to point to player1 or player2 is the unused Player class effectively disposed of? At that point nothing will point to it again. Second, can I make this a non-issue by not initializing currentPlayer before I assign it the first time to either player1 or player2?

Your analysis is correct.

The thing to remember about pointers is that assigning pointers does not imply any actions regarding the objects they point to. When you say "currentPlayer = player1", nothing happens to the object currentPlayer pointed to before the assignment. If currentPlayer was the only variable that pointed to that object, that object will never be deallocated because the program will never be able to get its address.

Your currentPlayer variable is being used as an alias to player1 or player2. Therefore, in the ConnectFour constructor, it should be initialized to player1 or player2. If your code needs currentPlayer to indicate it is in an unknown state (before swapPlayer() id called?) then you should add a noPlayer field that can be destroyed in ConnectFour's destructor.

Less safe, but very common, is to initialize aliases to 0 if it can be guaranteed that the alias will never be used before it is set to one of its proper set of objects. The danger is that three years after you start selling your program, some customer will find a path through your code that misuses the alias and the program crashes and you have an upset customer!

I like to explicitly comment how aliases are being used:

    field Player player1;
    field Player player2;
    field Player noPlayer;
    field Player currentPlayer;     // Alias to noPlayer, player1 or player2.
    field Board board;

    ...
    
    method void dispose()
    {
        // player1 not owned by ConnectFour.
        do player2.dispose();
        do noPlayer.dispose();
        // currentPlayer is an alias.
        do board.dispose();
        do Memory.deAlloc(this);
        return;
    }

--Mark

[sgaweda]

As always, thank you Mark. Ultimately, I opted to initialize currentPlayer to player1 in the constructor. My rationale was that I wouldn't have to allocate another Player object to memory that way. Interestingly, run() calls a method named playerOrder() which sets currentPlayer to the player who should be going first, so the initialization of currentPlayer to player1 is probably superfluous anyway. I'm actually quite surprised by how poorly I remember my program's design even though I coded it a few weeks ago.

I'm confident that this next version of Connect 4 will run without leaking memory and without error:

Connect_4_v1.zip

This game has been a fun challenge and I look forward to seeing how other people using the site like it.