Memory leaks in Tetris game - how to dispose of arrays properly

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Memory leaks in Tetris game - how to dispose of arrays properly

kingchoddle
I was first tempted to skip over Chapter 9 and head straight into the compiler. However, I couldn't resist making a Tetris clone, given the name of this entertaining and fascinating book.

If you check out my code so far on GitHub, you'll hopefully see that all is going just about OK, and the game is nearly at the point where it is resembling Tetris.

However, in my TetrisGame.run() method in this file, going round the loops to create new Tetris pieces, have them drop down, stop, and then to generate a new one, quickly consumes the heap.

I know from other posts, including this one, that this is a memory leak problem, caused by not deallocating and disposing objects, arrays, strings, etc. from the heap.

But in the file where I use many arrays (this one, which creates and manipulates blocks), I have tried in different ways to dispose of them (e.g., at the end of methods where they are used), but this often ends up making the game behave in strange ways.

For example, in Block.obstructionCheck() in this file, when I try to dispose of the temp, yCoordinate, and xCoordinate arrays just before returning from the function, this starts to affect the way the blocks respond to user input and are rendered on the screen.

As another thing I tried, I edited the Block.dispose() destructor method for the class, making it dispose of the "type" and "coordinates" field arrays that each Block owns in this version of the game. I called this TetrisGame.run() just after creating a new piece (i.e., to dispose of the one that just fell), but this also did not solve the problem.

To sum, if someone has experienced this problem, and could point me in the right direction here and provide some guidance about disposing of arrays properly to avoid heap overflow (and any other memory management issues) etc., that would be amazing. As a novice programmer, please feel free to let me know your general thoughts - any pointers for improvement would be valuable.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

WBahn
Administrator
Your memory leak could come from two sources. One is not deallocating memory like you need to, but the other is from memory fragmentation. You may have lots of free memory but it might all be in blocks that are individually too small to use.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

ivant
In reply to this post by kingchoddle
In your game loop, (TetrisGame.jack line 98), you are leaking memory. What happens is that before that the currentBlock variable is pointing to "old" current block, which just reached the bottom. On that, it starts pointing to the next block, but the old one isn't disposed.

Another smaller problem is on line 105 in the same file. The string is allocated every time a game ends, as cadet1620 explains in one of the posts you linked to.

There may be other problems, but these are the ones I found by skimming over the code.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

kingchoddle
Thank you WBahn and ivant!

So for ivant's suggestion about disposing of the "old" currentBlock before using it to point to the nextBlock, I have just tried that. However, it doesn't solve the issue ... after examining the heap in the VMEmulator, I think it is freeing up one memory location (the top one) each time the block hits the bottom and a new one is generated (but there are hundreds of memory locations before that, which aren't deallocated by currentBlock.dispose() ... ).

To investigate further, I used Mark's "do Memory.debugDumpHeap()", which you'll find in this file. It shows that, after the program stops running, many objects are being allocated by the program which aren't being deallocated. Do you think these are the arrays I use in Block.jack?

Also, I've found that, whenever any of the methods in Block.jack are run, the heap grows and is never cleared ... I think this is because each of these methods relies on creating arrays and manipulating them. In each case, I'm not sure how to deallocate these arrays in the best way. As I mentioned in my first post, when I do array.dispose() before returning from each of these methods in Block.jack, it starts to affect the program in unexpected ways

All in all, I have a feeling the main problem here is me not disposing of these arrays after I use them? Do you think this is right?

If so, what is the best practice for disposing of these arrays in Jack?
 
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

ivant
Yes, Block seems to leak memory as well. One thing you should do is to call the dispose() method of the arrays you've created. One place where this should be done is in the Block.dispose() method itself. Coordinates seem to be an array of arrays, so you should dispose the inner arrays first.

You also create arrays in getWidhtOrHeight, getMinimum, getMaximum and onstructionCheck, and you don't dispose any of them.

Again, this is not exhaustive analysis. There may be other problems as well.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

kingchoddle
Hi ivant, thanks again for your response.

OK, I've tried your suggestions, to no avail. We know the main memory leak is coming from Block.jack, and we know that not disposing of the arrays I use in all the methods in this class is the culprit.

However ... I have tried many, many different ways to call Array.dispose(array) on the arrays I create as local variables for my methods, none of which work. I really don't understand why. I think when I do the next two chapters, I will have an understanding of how this code is being compiled, and maybe that will tell me why the things I'm trying aren't working ...

(1) For example, in Block.getWidthOrHeight(), I use two arrays, "a" and "temp". My first thought about how to dispose these seems logical enough ...

// Block.jack
method int getWidthOrHeight(arg) {
   ...
   var Array a, temp;
   var int max, min;
   ...
   // calculate max & min and assign these to above-defined local variables
   ...
   do Array.dispose(a);
   do Array.dispose(temp);
   return (max - min);
}

However, disposing of the arrays in this way alters my return value. I'm not sure why this is the case as I have already bound the return values to the local variables, max and min, before disposing of the array. Do you know why this is? Or is this the wrong way to dispose of arrays which have been used as local variables in a class method? Is there a best practice in Jack that I am missing here?

=========

(2) As another example ... I tried making two Array field variables ("temp" and "a"), and then using these as general purpose storage arrays, which I could then use in any of the class methods and finally dispose of in Block.dispose() (given that any method can't access the local variables used in another method).

// Block.jack
method void dispose() {
   // dispose of field arrays an inner arrays in 2d list
   // I also tried Memory.deAlloc(array) for all of the below arrays
   do Array.dispose(coordinates[0]);
   do Array.dispose(coordinates[1]);
   do Array.dispose(coordinates[2]);
   do Array.dispose(coordinates[3]);
   do Array.dispose(coordinates);
   do Array.dispose(type);
   // dispose of new field arrays (general purpose storage arrays)
   do Array.dispose(temp);
   do Array.dispose(a);
   // dispose of instance
   do Memory.deAlloc(this);
   return;
}

=========

(1) seems like it should be the right approach, but maybe my timing of the disposal of these local arrays is wrong? (2) leads to strange results, doesn't work either, and would also add seemingly unnecessary field variables to the class. I've tried several other combinations of things too, but this post is already getting very long so I'll withhold those.

So, all in all, I'm really hoping to learn how my disposal of these arrays is wrong, and how to dispose of these correctly. I'm starting to think Memory.alloc() might be a missing piece of the puzzle here, but I'm not sure.

Thanks for your response again ivant, and I really apologise for all these long messages.

Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

ivant
It's Saturday, so I was able to look into your code a bit more.

You can call Memory.debugHeapStats() (again from the same non-standard Memory.vm file) to show just the stats. I added it to the main game loop, so I can observe the memory on each iteration:
		while (~exit) {

			do Memory.debugHeapStats();

			while (~atBottom) {
				...
			}
			...
		}

When you run it like this, you can see that the amount of free memory is decreasing.

kingchoddle wrote
(1) For example, in Block.getWidthOrHeight(), I use two arrays, "a" and "temp". My first thought about how to dispose these seems logical enough ...

// Block.jack
method int getWidthOrHeight(arg) {
   ...
   var Array a, temp;
   var int max, min;
   ...
   // calculate max & min and assign these to above-defined local variables
   ...
   do Array.dispose(a);
   do Array.dispose(temp);
   return (max - min);
}

However, disposing of the arrays in this way alters my return value. I'm not sure why this is the case as I have already bound the return values to the local variables, max and min, before disposing of the array. Do you know why this is? Or is this the wrong way to dispose of arrays which have been used as local variables in a class method? Is there a best practice in Jack that I am missing here?
You are on the right path here, but you have an error.

You are allocating memory for the a array, so you need to dispose it. A more precise way for saying that is, that 1) you are allocating memory for an 8 element array and 2) you are assigning the variable a to point to it. The actual value of a is some number (let's say 1000), which we treat as an address in memory. b would point to another address (1001), but c would point to the same address 1000.

For the temp variable, the story is different: You are not allocating new memory there, you are just assigning temp to point to an already existing memory. In this case it's one of the coordinates sub-arrays. This means that both temp and the sub-array point to the same place in memory. When you dispose it, you are affecting both of these. The memory then is reused for something else, but the sub-array still points to it and "thinks" of it as if it still owns it.

This type of variables are called pointers, because they are containing the address of, or "point to", the actual data. Assigning two pointers to point to the same address is called aliasing. This isn't a bug by itself, but it might be the cause for some hard-to-find problems, where things seem to change "by themselves". Consider the following code:
    var Array a, b, c;

    let a = Array.new(1);
    let b = Array.new(1);
    let c = a; // c is pointing to the same array as a! That is, they are aliases.

    let a[0] = 0;
    let b[0] = 0;
    do Output.printInt(a[0]); // this prints 0
    do Output.printInt(b[0]); // this still prints 0
    do Output.printInt(c[0]); // prints 0

    let a[0] = 1;
    do Output.printInt(a[0]); // this prints 1
    do Output.printInt(b[0]); // this still prints 0
    do Output.printInt(c[0]); // prints 1, as if changed "by itself"

    do a.dispose();
    do Output.printInt(b[0]); // still prints 0
    do Output.printInt(c[0]); // This would probably still print 1, but is actually an error, because it's using a freed memory. This is called a dangling pointer.
    do c.dispose(); // This creates huge problems, because you may be disposing someone else's memory. This is known as double-free.

    return; // We forgot to dispose b - this is memory leak.
If we had some more allocations and de-allocations between a.dispose() and c.get(), the memory that c is pointing to might be already reused by something else.

The bottom line is: manual memory management is hard. You need to think of who allocates a peace of memory and who is responsible of freeing it. The latter is sometimes referred to as the owner. And ownership can change, but the language does not help you to track this. There are libraries and tools which one can use to find such problems in C/C++ programs. And even with their help it's still hard.

To get back to your code, the temp variable is an alias to an existing array. The getWidthOrHeight() function is not the owner of this memory and therefore it should not dispose it. The same goes for the other functions, that I mentioned in my previous reply. In the end, when I fixed these, I was able to run your code without seeing a decrease in the free memory.

One more thing: You are supposed to call a.dispose() instead of Array.dispose(a), because dispose() is a method. But the compiler generates exactly the same VM code for both variants, so this is not a real problem with your code.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

kingchoddle
ivant, thank you so much for your detailed response. The fact that I was trying to dispose of aliases to an existing array is exactly why my return values were changing in "unexpected" ways. I was disposing of someone else's memory.

Having read your explanation, what is happening is no longer "unexpected", and I have a much clearer understanding of what is going on under the hood in this language. I have also learnt a lot about pointers, dangling pointers, double-free, and how the Jack language compiles in general.

Now, making revisions to my code based on your advice has addressed the memory leak

I'll continue on to finish the rest of the game now. I really can't thank you enough, that was a wonderful explanation!
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

ivant
kingchoddle wrote
ivant, thank you so much for your detailed response. The fact that I was trying to dispose of aliases to an existing array is exactly why my return values were changing in "unexpected" ways. I was disposing of someone else's memory.

Having read your explanation, what is happening is no longer "unexpected", and I have a much clearer understanding of what is going on under the hood in this language. I have also learnt a lot about pointers, dangling pointers, double-free, and how the Jack language compiles in general.

Now, making revisions to my code based on your advice has addressed the memory leak

I'll continue on to finish the rest of the game now. I really can't thank you enough, that was a wonderful explanation!
I'm glad I could help you with this. Back in the day most code was written in Assembly, C and C++, so one had to learn these lessons early. Nowadays most programming languages use managed memory (a.k.a. garbage collection) precisely because manual memory management is hard and error-prone.

This is one of the beauties of this course: it gives you the opportunity to learn a lot of things, which are now mostly under the hood.
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

kingchoddle
Yes, I just finished making the same game in JavaScript and it was a lot more straightforward due to its built-in garbage collection, as well as many other functions.

However, I also agree with you about the beauty of this course, and of using Jack. Using Jack (and soon writing the OS), in particular, brings you into contact with so many important and fascinating aspects of computers that you're generally not exposed to otherwise.

I really appreciate the fact that a course like this exists. Also, I'm really thankful that people like yourself are actively helping many of us through the problems we run into along the way.

So, thank you again!
Reply | Threaded
Open this post in threaded view
|

Re: Memory leaks in Tetris game - how to dispose of arrays properly

ivant
As a nice exercise, you may want to revisit some of the design choices you made for your Jack Tetris.

For example, the Block class (which should actually be renamed to Tetramino) is concerned both with game logic and visualization. This makes it harder to understand and manage. And I couldn't find a model for the board.

I would start with the board: I'd use an array of ints to represent the board: it's 10 by 20, so 200 elements. 0 would mean empty cell and 1 would mean full cell.  I'd create a few methods to allow me to reference the individual cells using the game-world coordinates (0-9, 0-19). I would then decide if the moving tetramino should be part of the board representation, a separate model, or both. In any case, it would use game-world coordinates.

We only need 1 tetramino at a time, the one that's moving, so we can reuse it when it hit the bottom. No need to allocate and free memory in the loop.

You'd need to iron-out the movement, rotation and collision detection logic. But that's much easier to do in game-space coordinates.

And lastly, detect and remove full rows and scroll the upper ones down.

Basically, you should be able to implement the whole game without the need to allocate and de-allocate memory during the game loop.


An alternative board representation would be as a bit-mask. This way you'll need just 20 words to represent the board: one for each line. Things like full line detection would be extremely fast. In this representation the tetramino will have to be external, but that seems to be OK.


When drawing the game, you can just redraw the changed lines, which are fewer (maximum 4 in case of the tetramino being a vertical line).