|
|
|
|
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.
|
|
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.
|
|
|
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.
|
|
|
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?
|
|
|
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.
|
|
|
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.
|
|
|
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.
|
|
|
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!
|
|
|
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.
|
|
|
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!
|
|
|
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).
|
|
|
Your comments are very detailed and massively appreciated. I'll outline my thoughts in response to each of the issues you highlighted. I'm interested to hear if you think these implementations would solve some of the issues you raised.
Please note that I may not be returning to Tetris in the Jack programming language in the future, but I am soon going to program a Go board (probably with JavaScript). Many of the issues you raise here have direct relevance for this future project, and so - as mentioned - I really appreciate the detailed feedback you have given, as well as the time you spent last month helping me to diagnose the memory leak issue!
(1) Class Names: "The Block class should be renamed to Tetramino". Thanks for pointing that out! You're right because blocks in my code are actually the names of the little squares that make up the whole tetramino. Those should be differentiated using a suitable class name.
(2) Model for the Board: "I'd use an array of ints to represent the board ... I'd create a few methods to allow me to reference the individual cells using the game-world coordinates (0-9, 0-19)". This is a wonderful approach. Movement, rotation, full line detection, line clearing, and collision detection logic would be greatly simplified due to the ability to manipulate values in the array that represents the board (rather than my current approach of dealing directly with RAM locations through peeking and poking).
For example, a starting point (not using strict Jack syntax) might be:
// board representation
board = new Array(200);
∀e in board(e = 0 | e = 1), where 0 is empty and 1 is occupied;
// access value in board representation with game-world coordinates
method int co(int x, int y) {
return board[x + (y * 10)];
}
// render board at some point (probably in TetrisGame.jack when board is needed)
method void render(Array board) {
∀e in board {
write e to Screen mem map as a block with some size and position;
}
}
(3) Memory Management: "We only need 1 tetramino at a time, the one that's moving ...". My understanding is that this would be a side-effect of the use of a board representation as discussed above. Specifically, as a single tetramino moves about inside the board array, values inside the array will change as per the methods created for movement, rotation, and so on. When it hits the bottom, it will leave an imprint on the board representation, meaning it can be zapped back up to the top with some method in TetrisGame, changed into a different shape, and reused, all the while preserving the imprint it left in board representation at the bottom. In my current approach, those imprints of the tetraminos at the bottom of the screen are actual tetraminos held in memory ... so we build up hundreds by the end of the game. Your approach would be much, much more efficient and - as you say - would avoid the need to allocate and free memory inside the game loop.
(4) Bit-Mask: "An alternative board representation would be as a bit-mask". I have come across the term "mask" before in a related context (used in Noam Nissan's ConvertToBin.jack), but I just had to do a bit of research on the concept of a bit-mask. This is an interesting alternative, and I will look further into the issue before setting out on my Go board project.
(5) Shifting Rows After Line Clears: "Detect and remove full rows and scroll the upper ones down ... you can just redraw the changed lines, which are fewer". In my current approach, I (i) determine how many (and which) lines should be cleared, (ii) eliminate those from the board, (iii) shift the coordinates of every row above the cleared lines down, and (iv) redraw everything, square by square to reflect the "scrolling". I think the point you are raising is that there is certainly a more efficient way to do this, and I agree! I will think about this a little bit and maybe get back to you soon with my findings.
==========
Thanks for your time and advice!
Max
|
|
|
kingchoddle wrote
(2) Model for the Board: "I'd use an array of ints to represent the board ... I'd create a few methods to allow me to reference the individual cells using the game-world coordinates (0-9, 0-19)". This is a wonderful approach. Movement, rotation, full line detection, line clearing, and collision detection logic would be greatly simplified due to the ability to manipulate values in the array that represents the board (rather than my current approach of dealing directly with RAM locations through peeking and poking).
For example, a starting point (not using strict Jack syntax) might be:
// board representation
board = new Array(200);
∀e in board(e = 0 | e = 1), where 0 is empty and 1 is occupied;
// access value in board representation with game-world coordinates
method int co(int x, int y) {
return board[x + (y * 10)];
}
// render board at some point (probably in TetrisGame.jack when board is needed)
method void render(Array board) {
∀e in board {
write e to Screen mem map as a block with some size and position;
}
}
Basically yes. The only thing you might want to optimize, if it turns out to be too slow, is the rendering part, but we are discussing this in (5).
The main idea is, that in anything but the most basic programs, you'd want to separate the model of the world from the presentation. This makes your program easier to understand and modify.
As with most rules, there are exceptions, but you don't need to worry about them at this time. This will come with more experience. I'm only mentioning this here, so you don't take it as an absolute rule.
kingchoddle wrote
(3) Memory Management: "We only need 1 tetramino at a time, the one that's moving ...". My understanding is that this would be a side-effect of the use of a board representation as discussed above. Specifically, as a single tetramino moves about inside the board array, values inside the array will change as per the methods created for movement, rotation, and so on. When it hits the bottom, it will leave an imprint on the board representation, meaning it can be zapped back up to the top with some method in TetrisGame, changed into a different shape, and reused, all the while preserving the imprint it left in board representation at the bottom. In my current approach, those imprints of the tetraminos at the bottom of the screen are actual tetraminos held in memory ... so we build up hundreds by the end of the game. Your approach would be much, much more efficient and - as you say - would avoid the need to allocate and free memory inside the game loop.
We only need one tetramino, because that's how the game plays, not because of the representation. It only has one controllable tetramino on the board at any given time. The ones that are inactive are not tetraminos anymore. When I read your code, I was puzzled why you need 2 of those.
There is one more tetramino displayed, which is the next one. But you don't really need to make an object for it, because it's not controllable. You only need to choose its type to be able to display it.
When the tetramino hits the bottom and you need a new one, you have two approaches. You can dispose the old one and create a new one, or you can modify the existing one. The former is a cleaner approach and you should start with it. The latter is an optimization, and optimizations should be done in a controlled and measured manner.
There are a few maxims, which I find very helpful. The first one is: "make it work; make it right; make it fast". That is, optimizations should come last, and be done on correctly running program, preferably with tests, to make sure you're not breaking it.
Another one is, that "90% of the program is spend in 3% of the code, at least in interactive programs". (I'm quoting by hearth. I couldn't find the original.) This means, that you should only optimize parts of the program that would have an impact. For one, you will spend your time better, and also, optimizations often lead to less readable and more brittle code.
kingchoddle wrote
(4) Bit-Mask: "An alternative board representation would be as a bit-mask". I have come across the term "mask" before in a related context (used in Noam Nissan's ConvertToBin.jack), but I just had to do a bit of research on the concept of a bit-mask. This is an interesting alternative, and I will look further into the issue before setting out on my Go board project.
Actually I used the term "bit-mask" incorrectly here. A better term would be "bitmap", but it is often associated with images only. The idea is, that instead of using a whole int for one block, you can use just one bit. This means that you can put a whole like (10 blocks) in just one 16-bit word. This also makes it very easy to check if the whole line, or to move lines down.
This is again an optimization, so see above for when you should try it.
kingchoddle wrote
(5) Shifting Rows After Line Clears: "Detect and remove full rows and scroll the upper ones down ... you can just redraw the changed lines, which are fewer". In my current approach, I (i) determine how many (and which) lines should be cleared, (ii) eliminate those from the board, (iii) shift the coordinates of every row above the cleared lines down, and (iv) redraw everything, square by square to reflect the "scrolling". I think the point you are raising is that there is certainly a more efficient way to do this, and I agree! I will think about this a little bit and maybe get back to you soon with my findings.
Yes, there are several optimizations that can be done here. Some are quite easy ones: for example, if you see an empty line, then all the lines above it are also empty so you can stop the redrawing.
Others are a bit more involved: for example, you can see which blocks are different between the currently displayed state of the line and its new state and only redraw them.
There are also lower-level optimizations, which take into account the specific hardware that is being used. For example, to display a block (or to remove one) you need to do it row by row. It would be faster, if you only need to access one word per row to do that. That is, the pixels of one block should not cross a word boundary.
To be able to do that, you need to choose the right size of the block. There are 20 rows of blocks and we have 256 rows of pixels, so each block cannot be larger than 12/12 pixels (256/20 = 12.8). To be able to pack blocks in one word, means to split it in equal parts. For 16-bit word, we can choose between 16 1-pixel blocks, 4 4-pixels blocks, 2 8-pixels and 1 16-pixels. The 16-pixels block is too large (because it's larger than 12). The best one looks to be an 8x8 pixel blocks.
So two blocks could look like this:
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
As you can see, the bottom line is always 0, so once initialized it never needs to be updated. For the others you have 4 possible options:
empty, empty: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
empty, full : 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
full , empty: 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
full , full : 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
Using these patterns you can display blocks very fast. Here it's perfectly fine to directly update the video memory (poke at last! :) )
|
|
Locked
